Skip to content

Instantly share code, notes, and snippets.

@kbob
Created February 20, 2016 21:53
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save kbob/c167bf4eb0eb855e0dfc to your computer and use it in GitHub Desktop.
Trie insertion and query
struct TrieNode {
is_terminal: bool,
children: [Option<Box<TrieNode>>; 256],
}
impl TrieNode {
fn new() -> TrieNode {
let mem : TrieNode = unsafe { std::mem::zeroed() };
mem
}
fn find_word(&self, word: &str) -> bool {
self.find_bytes(word.as_bytes())
}
fn append_word(&mut self, word: &str) {
self.append_bytes(word.as_bytes());
}
fn find_bytes(&self, word: &[u8]) -> bool {
let len = word.len();
if len == 0 {
return self.is_terminal;
}
let c = word[0];
let index = c as usize;
let child = &self.children[index];
match *child {
None => false,
Some(ref p) => { (*p).find_bytes(&word[1 .. len]) }
}
}
fn append_bytes(&mut self, word: &[u8]) {
let len = word.len();
if len == 0 {
self.is_terminal = true;
} else {
let c = word[0];
let index = c as usize;
let mut child = &mut self.children[index];
if child.is_none() {
*child = Some(Box::new(TrieNode::new()));
}
match *child {
None => { panic!("???"); }
Some(ref mut p) => { (*p).append_bytes(&word[1 .. len]); }
}
}
}
}
fn main() {
let mut root = TrieNode::new();
root.append_word("ad");
println!("a => {}", root.find_word("a"));
println!("ad => {}", root.find_word("ad"));
println!("an => {}", root.find_word("an"));
println!("by => {}", root.find_word("by"));
println!("");
root.append_word("an");
println!("a => {}", root.find_word("a"));
println!("ad => {}", root.find_word("ad"));
println!("an => {}", root.find_word("an"));
println!("by => {}", root.find_word("by"));
println!("");
root.append_word("a");
println!("a => {}", root.find_word("a"));
println!("ad => {}", root.find_word("ad"));
println!("an => {}", root.find_word("an"));
println!("by => {}", root.find_word("by"));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment