Go down a tree without recursion


#1

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);
}

http://is.gd/3BdiYu


#2

This is perfectly fine and safe, the compiler just needs a tiny push to see it: http://stackoverflow.com/a/27083650/1256624

let x = temp;
temp = &mut *x.arr[val].as_mut().unwrap();

#3

I see. Thank you!