trie_alg/
trie.rs

1//! Provides `Trie` and `MultiTrie` implementations space optimized for set of characters in use.
2
3use std::default::Default;
4
5mod member;
6
7#[allow(unused_imports)]
8pub mod charset;
9pub use self::charset::CharSet;
10
11mod internal;
12use self::internal::_Trie;
13
14#[derive(Default)]
15pub struct Trie<C, const SIZE: usize>
16where
17    C: CharSet,
18{
19    internal: _Trie<bool, C, SIZE>,
20}
21
22impl<C, const SIZE: usize> Trie<C, SIZE>
23where
24    C: CharSet,
25{
26    /// Creates new Trie
27    pub fn new() -> Self {
28        Self {
29            internal: _Trie::<_, _, SIZE>::new(),
30        }
31    }
32
33    /// Add a string to Trie
34    /// 
35    /// Returns `true` if Trie didn't contain the string earlier
36    pub fn add(&mut self, s: &str) -> bool {
37        self.internal.add(s)
38    }
39
40    /// Check if trie contains the string
41    pub fn contains(&self, s: &str) -> bool {
42        self.internal.contains(s)
43    }
44}
45
46#[derive(Default)]
47pub struct MultiTrie<C, const SIZE: usize>
48where
49    C: CharSet,
50{
51    internal: _Trie<u32, C, SIZE>,
52}
53
54impl<C, const SIZE: usize> MultiTrie<C, SIZE>
55where
56    C: CharSet,
57{
58    /// Creates a new MultiTrie
59    pub fn new() -> Self {
60        Self {
61            internal: _Trie::<_, _, SIZE>::new(),
62        }
63    }
64
65    /// Adds a new string to the MultiTrie
66    /// 
67    /// Returns `true`` if MultiTrie didn't contain the string earlier
68    pub fn add(&mut self, s: &str) -> bool {
69        self.internal.add(s)
70    }
71
72    /// Check if MultiTrie contains given string
73    pub fn contains(&self, s: &str) -> bool {
74        self.internal.contains(s)
75    }
76
77    /// Retuns number of strings in the MultiTrie
78    pub fn count(&self, s: &str) -> u32 {
79        self.internal.count(s)
80    }
81}
82
83#[macro_export]
84/// Create new `Trie`
85/// 
86/// `trie!(C:CharSet)` creates new trie with given `CharSet`
87/// 
88/// `trie!()` defaults to `LowerCase`,set of lowercase alphabets
89macro_rules! trie {
90    () => {
91        Trie::<
92            self::charset::LowerCase,
93            { <self::charset::LowerCase as self::charset::CharSet>::SIZE },
94        >::new()
95    };
96    ($C:ty) => {
97        Trie::<$C, { <$C as self::charset::CharSet>::SIZE }>::new()
98    };
99}
100
101#[macro_export]
102/// Create new `MultiTrie`
103/// 
104/// `multi_trie!(C:CharSet)` creates new trie with given `CharSet`
105/// 
106/// `multi_trie!()` defaults to `LowerCase`,set of lowercase alphabets
107macro_rules! multi_trie {
108    () => {
109        MultiTrie::<
110            self::charset::LowerCase,
111            { <self::charset::LowerCase as self::charset::CharSet>::SIZE },
112        >::new()
113    };
114    ($C:ty) => {
115        MultiTrie::<$C, { <$C as self::charset::CharSet>::SIZE }>::new()
116    };
117}
118
119#[cfg(test)]
120mod tests {
121    use self::charset::LowerCase;
122    use super::*;
123
124    #[test]
125    fn test_single_add() {
126        let mut trie = trie!();
127        trie.add("string");
128        assert!(trie.contains("string"));
129    }
130
131    #[test]
132    fn test_single_eq() {
133        let mut trie1 = trie!(LowerCase);
134        assert!(trie1.add("string"));
135        assert!(!trie1.add("string"));
136    }
137
138    #[test]
139    fn test_multi_add() {
140        let mut trie = multi_trie!();
141        trie.add("string");
142        assert!(trie.contains("string"));
143    }
144
145    #[test]
146    fn test_multi_eq() {
147        let mut trie = multi_trie!(LowerCase);
148        assert!(trie.add("string"));
149        assert!(!trie.add("string"));
150        assert_eq!(trie.count("string"), 2);
151    }
152}
trie_alg/trie.rs

trie_alg/
trie.rs
