ptrie 0.7.2

Generic trie data structure implementation (prefix tree) with support for different key and value types, and functions to search for common prefixes or postfixes.
Documentation 
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#[cfg(test)]
mod tests {
    use ptrie::Trie;

    #[test]
    fn new_trie_is_is_empty() {
        assert!(Trie::<char, String>::new().is_empty());
    }

    #[test]
    fn add_word_to_trie() {
        let mut t = Trie::new();
        t.insert("test".bytes(), String::from("test"));
        assert!(!t.is_empty());
    }

    #[test]
    fn contains_key_test() {
        let mut t = Trie::new();
        let test = "test".bytes();
        let tes = "tes".bytes();
        let notintest = "notintest".bytes();

        t.insert(test.clone(), String::from("test"));
        assert!(!t.is_empty());
        assert!(t.contains_key(test));
        assert!(!t.contains_key(tes));
        assert!(!t.contains_key(notintest));
    }

    #[test]
    fn contains_key_sub_path_test() {
        let mut t = Trie::new();
        let test = "test".bytes();
        let tes = "tes".bytes();
        let notintest = "notintest".bytes();

        t.insert(test.clone(), String::from("test"));
        t.insert(tes.clone(), String::from("tes"));
        assert!(!t.is_empty());
        assert!(t.contains_key(test));
        assert!(t.contains_key(tes));
        assert!(!t.contains_key(notintest));
    }

    #[test]
    fn clear_test() {
        let mut t = Trie::new();
        let data = "test".bytes();

        t.insert(data.clone(), String::from("test"));
        assert!(!t.is_empty());
        assert!(t.contains_key(data.clone()));

        t.clear();
        assert!(t.is_empty());
        assert!(!t.contains_key(data));
    }

    #[test]
    fn find_prefixes() {
        let mut trie = Trie::new();
        trie.insert("abc".bytes(), "ABC");
        trie.insert("abcd".bytes(), "ABCD");
        trie.insert("abcde".bytes(), "ABCDE");
        let prefixes = trie.find_prefixes("abcd".bytes());
        assert_eq!(prefixes, vec![&"ABC", &"ABCD"]);
        assert_eq!(trie.find_prefixes("efghij".bytes()), Vec::<&&str>::new());
        assert_eq!(trie.find_prefixes("abz".bytes()), Vec::<&&str>::new());
    }

    #[test]
    fn iterator() {
        let mut t = Trie::new();
        let test = "test".bytes();
        let tes = "tes".bytes();

        t.insert(test.clone(), String::from("test"));
        t.insert(tes.clone(), String::from("tes"));
        for (k, v) in &t {
            assert!(std::str::from_utf8(&k).unwrap().starts_with("tes"));
            assert!(v.starts_with("tes"));
        }
    }

    #[test]
    fn test_remove() {
        let mut trie = Trie::new();
        trie.insert("hello".bytes(), 1);
        trie.insert("hell".bytes(), 2);
        trie.insert("h".bytes(), 3);

        assert_eq!(trie.remove("hello".bytes()), Some(1));
        assert_eq!(trie.get("hello".bytes()), None);
        assert_eq!(trie.get("hell".bytes()), Some(&2));
        assert_eq!(trie.get("h".bytes()), Some(&3));

        assert_eq!(trie.remove("h".bytes()), Some(3));
        assert_eq!(trie.get("h".bytes()), None);
        assert_eq!(trie.get("hell".bytes()), Some(&2));

        assert_eq!(trie.remove("nonexistent".bytes()), None);
    }

    #[cfg(feature = "serde")]
    #[test]
    fn serde_serialize() {
        use serde_json;
        let mut trie = Trie::new();
        trie.insert("key".bytes(), 42);
        let serialized = serde_json::to_string(&trie).expect("Failed to serialize");
        // println!("serialized! {}", serialized);
        let deserialized: Trie<u8, i32> =
            serde_json::from_str(&serialized).expect("Failed to deserialize");
        assert_eq!(deserialized.get("key".bytes()), Some(42).as_ref());
    }
}