No comment. Just wanted to log it somewhere. It's my silly implementation for a Trie in Rust. Just so I can have a laugh at myself in ten years ;)
This Trie assumes to be accepting strings of numbers and dashes. It was meant to encode a very particular kind of string. Ultimately it wasn't worth it so I bailed and used something else.
This is very "just learning Rust" stage coding. Don't copy this for production code. You've been warned. Stop laughing.
use std::fmt;
const TRIE_PANIC: i8 = 0;
const TRIE_OVERWRITE: i8 = 1;
const TRIE_IGNORE: i8 = 2;
#[derive(Debug)]
pub enum Base {
Octal = 8,
Decimal = 10,
Hex = 16,
}
const BASE: Base = Base::Octal;
// A node has 11 positions as a jump table (10 digits and a dash) and one "value" position.
// The value position is 0 if "not found" (etc), and non-zero if known (TBD)
// In hex mode, there are six more positions (a-f)
pub type TrieNode = [usize; BASE as usize + 2];
pub struct Trie {
pub nodes: Vec,
}
impl Trie {
pub fn new() -> Trie {
return Trie {
nodes: vec!(
[0 as usize; BASE as usize + 2],
),
};
}
pub fn read(&mut self, trail: &str, trace: bool) -> usize {
return self.walk(trail, false, 0, false, trace);
}
pub fn write(&mut self, trail: &str, value: usize, clobber: bool, trace: bool) {
self.walk(trail, true, value, clobber, trace);
}
// A walker that can optionally update the trie if the value is not found
fn walk(&mut self, trail: &str, write: bool, value: usize, clobber: bool, trace: bool) -> usize {
// let mut t: [u32; 12] = trie[0];
let mut t: TrieNode = self.nodes[0];
let mut ti: usize = 0;
let mut step: u32 = 0;
let mut writing: bool = false;
let mut len: usize = self.nodes.len();
for (i, c) in trail.bytes().enumerate() {
if !writing {
let next_ti: usize = t[match c {
// - (dash)
45 => 1,
// 0-9
48 => 2,
49 => 3,
50 => 4,
51 => 5,
52 => 6,
53 => 7,
54 => 8,
55 => 9,
56 => 10,
57 => 11,
// a-f
97 => 12,
98 => 13,
99 => 14,
100 => 15,
101 => 16,
102 => 17,
_x => panic!("Encoded string should only contain digits and dashes, got {}", _x),
}];
if trace { println!("Step: {}, path index: {}, c: {}, node index: {}, next node index: {}", step, i, c, ti, next_ti); }
step = step + 1;
if next_ti != 0 {
ti = next_ti;
t = self.nodes[ti];
continue;
}
if !write {
// "Not found"
return 0;
}
writing = true
}
if writing {
if trace { println!("Writing {} to index {} on node {}", len, c, ti); }
self.nodes[ti][match c {
// Note: index 0 is the value
// - (dash)
45 => 1,
// 0-9
48 => 2,
49 => 3,
50 => 4,
51 => 5,
52 => 6,
53 => 7,
54 => 8,
55 => 9,
56 => 10,
57 => 11,
// a-f
97 => 12,
98 => 13,
99 => 14,
100 => 15,
101 => 16,
102 => 17,
_x => panic!("Encoded string should only contain digits and dashes, got {}", _x),
}] = len;
ti = len;
t = [0; BASE as usize + 2];
self.nodes.push(t);
len = len + 1;
}
}
if write {
if !clobber && t[0] != 0 {
panic!("Not expecting to clobber value.");
}
if trace { println!("Now writing {} to node {}", value, ti); }
self.nodes[ti][0] = value;
return value;
}
return t[0];
}
pub fn path_to_trail(&self, path: &Vec<(i32, i32)>, trace: bool) -> String {
let mut hash = String::new();
for (x, y) in path {
match BASE {
Base::Octal => hash.push_str(&format!("{:o}", x)),
Base::Decimal => hash.push_str(&x.to_string()),
Base::Hex => hash.push_str(&format!("{:x}", x)),
}
hash.push_str("-");
match BASE {
Base::Octal => hash.push_str(&format!("{:o}", y)),
Base::Decimal => hash.push_str(&y.to_string()),
Base::Hex => hash.push_str(&format!("{:x}", x)),
}
hash.push_str("-");
}
if trace { println!("{}", hash); }
return hash;
}
pub fn print_stats(&self, added: i32, total: i32) {
println!("Trie is in {:?} mode. It has {} nodes. It contains {} unique paths out of {} total. Each node takes up 4x{} bytes so naive encoding totals {} bytes", BASE, self.nodes.len(), added, total, BASE as usize + 2, BASE as usize + 2 * 4 * self.nodes.len());
}
}
impl fmt::Display for Trie {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Trie[ {} :\n", self.nodes.len());
for node in self.nodes.iter() {
write!(f, " {:?},\n", node);
}
write!(f, "]")
}
}