1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
use std::collections::HashMap;

#[derive(Debug, Clone)]
pub struct PrefixTree<T> {
    tab: HashMap<(u32,u32,char),(u32,bool,Option<T>)>
}

impl<T: Clone> PrefixTree<T> {
    pub fn new(sorted_word_list_with_payload: &[(&str,T)]) -> PrefixTree<T> {
        let mut tab: HashMap<(u32,u32,char),(u32,bool,Option<T>)> = HashMap::new();
        let word_list_len = sorted_word_list_with_payload.len();
        for i in 0..word_list_len {
            let (ref word, ref payload) = sorted_word_list_with_payload[i];
            let char_vec: Vec<char> = word.chars().collect();
            let word_len = char_vec.len();
            
            let mut row_no: u32 = 0;
            for j in 0..word_len {
                let is_terminal = j + 1 == word_len;
                let ch = char_vec[j];
                let child = tab.entry((row_no as u32,j as u32,ch))
                    .or_insert((i as u32, is_terminal,
                                if is_terminal {
                                    Some(payload.clone())
                                } else {
                                    None
                                }));
                let &mut (_row_no, _, _) = child;
                row_no = _row_no;
            }            
        }
        PrefixTree{tab: tab}
    }

    pub fn seek(&self, key: &(u32,u32,char)) -> Option<&(u32,bool,Option<T>)> {
        self.tab.get(key)
    }
}