trie.rs

struct TrieNode { 
    sib: Option<(char, usize)>,
    child: Option<(char, usize)>,
    terminal: bool,
}

pub struct Trie { nodes: Vec<TrieNode> }

impl Trie {
    fn root(&self) -> &TrieNode { &self.nodes[0] }

    fn find_or_insert_child(&mut self, node: usize, c: char) -> usize {
        let next = self.nodes.len();
        let mut where_to_insert = &mut self.nodes[node].child;
        loop {
            match *where_to_insert {
                Some((c2, idx)) if c == c2 => return idx,
                Some((_, idx)) => where_to_insert = &mut self.nodes[idx].sib,
                None => {
                    *where_to_insert = Some((c, next));
                    self.nodes.push(TrieNode { sib: None, child: None, terminal: false });
                    return next
                }
            }
        }
    }

    pub fn insert(&mut self, str: &str) {
        let mut idx = 0; // root
        for char in str.chars() {
            idx = self.find_or_insert_child(idx, char);
        }
        self.nodes[idx].terminal = true;
    }

    fn find_child(&self, node: &TrieNode, c: char) -> Option<&TrieNode> {
        let mut current = &node.child;
        while let Some((c2, idx)) = current {
            let node = &self.nodes[*idx];
            if c == *c2 { return Some(node) }
            current = &node.sib;
        }
        None
    }

    pub fn contains(&self, str: &str) -> bool {
        let node = self.root();
        for char in str.chars() {
            node = match self.find_child(node, char) {
                Some(child) => child,
                None => return false,
            }
        }
        node.terminal
    }
}