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