I'm trying to implement insertion for a trie without using recursion or RefCell
which has runtime overhead. Do I have to resort to unsafe code here?
#![feature(num_bits_bytes)]
struct TrieNode {
value: Option<usize>,
arr: [Option<Box<TrieNode>>; 2],
}
impl TrieNode {
fn new(value: Option<usize>) -> TrieNode {
TrieNode {
value: value,
arr: [None, None],
}
}
}
struct Trie {
root: Box<TrieNode>,
}
impl Trie {
fn new() -> Trie {
Trie { root: Box::new(TrieNode::new(Some(0))) }
}
fn insert(&mut self, pre_xor: usize) {
let mut temp = &mut *self.root;
let mut i = std::isize::BITS as isize - 1;
while i >= 0 {
let val = (pre_xor & (1 << i) != 0) as usize;
if !temp.arr[val].is_some() {
temp.arr[val] = Some(Box::new(TrieNode::new(None)));
}
temp = &mut *temp.arr[val].as_mut().unwrap();
i = i - 1;
}
temp.value = Some(pre_xor);
}
}
fn main() {
let mut trie = Trie::new();
trie.insert(7);
}