trie_alg/
lib.rs

1//! # `trie-alg`
2//! Implement a trie space optimized for character set in use
3//! ```
4//! let mut t = trie!();
5//! t.add("abc");           // true
6//! t.add("abc");           // false
7//! t.contains("abc");      // true
8//! t.contains("a");        // false
9//! 
10//! let mut t = multi_trie!();
11//! t.add("abc");           // true
12//! t.count("abc")          // 1
13//! t.add("abc");           // false
14//! t.count("abc")          // 2
15//! t.contains("abc")       // true
16//! t.contains("a")         // false
17//! t.count("a")            // 0
18//! 
19//! struct LowerCaseWithHash();
20//! impl CharSet for LowerCaseWithHash {
21//!     const SIZE: usize = 27;
22//!     fn map(ch: char) -> usize {
23//!         if ch.is_ascii_lowercase() {
24//!            ch as usize - 'a' as usize 
25//!         } else {
26//!             26
27//!         }
28//!     }
29//!
30//!     fn unmap(hash: usize) -> char {
31//!         if hash < 26 {
32//!             (b'a'+hash as u8) as char
33//!         }else {
34//!             '#'
35//!         }
36//!     }
37//! }
38//! 
39//! let mut t = multi_trie!(LowerCaseWithHash);
40//! ```
41//! 
42//! ## Todo
43//! - [ ] Implement error handling for `CharSet` trait
44//! - [ ] Implement iterators to iterate over trie
45//! - [ ] Implement `delete` method to remove string from trie
46//! - [ ] Implement `TrieMap` to store information at the trie node -> MultiTrie will derive from this
47//! - [ ] Implement function to count string with given prefix in the trie
48
49#[macro_use]
50pub mod trie;
51
52#[cfg(test)]
53mod tests {
54
55    use crate::trie::*;
56
57    #[test]
58    fn trie_works() {
59        let mut t = trie!();
60        t.add("abc");
61        assert!(t.contains("abc"));
62        assert!(!t.contains("a"));
63    }
64
65    #[test]
66    fn multi_trie_works() {
67        let mut t = multi_trie!();
68        t.add("abc");
69        assert_eq!(t.count("abc"), 1);
70        t.add("abc");
71        assert_eq!(t.count("abc"), 2);
72        assert!(t.contains("abc"));
73        assert!(!t.contains("a"));
74        assert_eq!(t.count("a"), 0);
75    }
76
77    struct LowerCaseWithHash();
78    impl CharSet for LowerCaseWithHash {
79        const SIZE: usize = 27;
80        fn map(ch: char) -> usize {
81            if ch.is_ascii_lowercase() {
82               ch as usize - 'a' as usize 
83            } else {
84                26
85            }
86        }
87
88        fn unmap(hash: usize) -> char {
89            if hash < 26 {
90                (b'a'+hash as u8) as char
91            }else {
92                '#'
93            }
94        }
95    }
96
97    #[test]
98    fn custom_charset_works(){
99        let mut t = multi_trie!(LowerCaseWithHash);
100        t.add("abc");
101        assert_eq!(t.count("abc"), 1);
102        t.add("abc");
103        assert_eq!(t.count("abc"), 2);
104        t.add("ab#c");
105        t.add("ab#c");
106        assert_eq!(t.count("ab#c"), 2);
107        assert!(t.contains("abc"));
108        assert!(!t.contains("a"));
109        assert_eq!(t.count("a"), 0);
110    }
111
112    #[test]
113    fn multi_trie_works_uppercase() {
114        let mut t = multi_trie!(charset::UpperCase);
115        t.add("ABC");
116        assert_eq!(t.count("ABC"), 1);
117        t.add("ABC");
118        assert_eq!(t.count("ABC"), 2);
119        assert!(t.contains("ABC"));
120        assert!(!t.contains("A"));
121        assert_eq!(t.count("A"), 0);
122    }
123}
trie_alg/lib.rs

trie_alg/
lib.rs
