prefix_tree/
set.rs

1use map::{Iter as MapIter, PrefixMap};
2use std::hash::{Hash, Hasher};
3use std::iter::{FromIterator, FusedIterator};
4
5/// A set implemented as a `PrefixMap` where the value is `()`.
6#[derive(Debug, Default)]
7pub struct PrefixSet<T> {
8    map: PrefixMap<T, ()>,
9}
10
11impl<T: Eq + Clone> PrefixSet<T> {
12    /// Creates an empty `PrefixSet`.
13    ///
14    /// # Examples
15    ///
16    /// ```
17    /// use prefix_tree::PrefixSet;
18    ///
19    /// let mut set: PrefixSet<u8> = PrefixSet::new();
20    /// ```
21    pub fn new() -> PrefixSet<T> {
22        PrefixSet {
23            map: PrefixMap::new(),
24        }
25    }
26
27    /// Clears the set, removing all key-value pairs.
28    ///
29    /// # Examples
30    ///
31    /// ```
32    /// use prefix_tree::PrefixSet;
33    ///
34    /// let mut set: PrefixSet<u8> = PrefixSet::new();
35    /// set.insert("foo");
36    /// set.clear();
37    /// assert!(set.is_empty());
38    /// ```
39    pub fn clear(&mut self) {
40        self.map.clear()
41    }
42
43    /// Returns `true` if the set contains a value.
44    ///
45    /// # Examples
46    ///
47    /// ```
48    /// use prefix_tree::PrefixSet;
49    ///
50    /// let mut set: PrefixSet<u8> = PrefixSet::new();
51    /// set.insert("1");
52    /// assert_eq!(set.contains("1"), true);
53    /// assert_eq!(set.contains("2"), false);
54    /// ```
55    pub fn contains<Q>(&self, key: Q) -> bool
56    where
57        Q: AsRef<[T]>,
58    {
59        self.map.get(key).is_some()
60    }
61
62    /// Adds a value to the set.
63    ///
64    /// # Examples
65    ///
66    /// ```
67    /// use prefix_tree::PrefixSet;
68    ///
69    /// let mut set: PrefixSet<u8> = PrefixSet::new();
70    /// assert_eq!(set.insert("1"), true);
71    /// assert_eq!(set.insert("1"), false);
72    /// assert_eq!(set.contains("1"), true);
73    /// ```
74    pub fn insert<Q>(&mut self, key: Q) -> bool
75    where
76        Q: AsRef<[T]>,
77    {
78        self.map.insert(key, ()).is_none()
79    }
80
81    /// Removes a value from the set. Returns whether the value was present in the set.
82    ///
83    /// # Examples
84    ///
85    ///
86    /// ```
87    /// use prefix_tree::PrefixSet;
88    ///
89    /// let mut set: PrefixSet<u8> = PrefixSet::new();
90    /// set.insert("1");
91    /// assert_eq!(set.remove("1"), true);
92    /// assert_eq!(set.remove("1"), false);
93    /// ```
94    pub fn remove<Q>(&mut self, key: Q) -> bool
95    where
96        Q: AsRef<[T]>,
97    {
98        self.map.remove(key).is_some()
99    }
100
101    /// Returns `true` if the set contains no elements.
102    ///
103    /// # Examples
104    ///
105    /// ```
106    /// use prefix_tree::PrefixSet;
107    ///
108    /// let mut set: PrefixSet<u8> = PrefixSet::new();
109    /// assert_eq!(set.is_empty(), true);
110    /// set.insert("foo");
111    /// assert_eq!(set.is_empty(), false);
112    /// ```
113    pub fn is_empty(&self) -> bool {
114        self.map.is_empty()
115    }
116
117    /// Returns the number of elements in the set.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use prefix_tree::PrefixSet;
123    ///
124    /// let mut set: PrefixSet<u8> = PrefixSet::new();
125    /// assert_eq!(set.len(), 0);
126    /// set.insert("foo");
127    /// assert_eq!(set.len(), 1);
128    /// ```
129    pub fn len(&self) -> usize {
130        self.map.len()
131    }
132
133    /// Gets an iterator that visits the values in `PrefixSet`.
134    ///
135    /// # Examples
136    ///
137    /// ```
138    /// use prefix_tree::PrefixSet;
139    ///
140    /// let mut set: PrefixSet<u8> = PrefixSet::new();
141    /// set.insert("1");
142    /// set.insert("2");
143    /// let mut iter = set.iter();
144    /// assert_eq!(iter.next(), Some(vec![b'1']));
145    /// assert_eq!(iter.next(), Some(vec![b'2']));
146    /// ```
147    pub fn iter(&self) -> Iter<T> {
148        Iter {
149            iter: self.map.iter(),
150        }
151    }
152}
153
154impl<'a, T: 'a + Eq + Clone> FromIterator<&'a [T]> for PrefixSet<T> {
155    fn from_iter<I>(iter: I) -> PrefixSet<T>
156    where
157        I: IntoIterator<Item = &'a [T]>,
158    {
159        let mut set = PrefixSet::new();
160        iter.into_iter().for_each(|x| {
161            set.insert(x);
162        });
163        set
164    }
165}
166
167impl<'a, T: 'a + Eq + Clone> IntoIterator for &'a PrefixSet<T> {
168    type Item = Vec<T>;
169
170    type IntoIter = Iter<'a, T>;
171
172    fn into_iter(self) -> Self::IntoIter {
173        self.iter()
174    }
175}
176
177pub struct Iter<'a, T> {
178    iter: MapIter<'a, T, ()>,
179}
180
181impl<'a, T: 'a + Eq + Clone> Iterator for Iter<'a, T> {
182    type Item = Vec<T>;
183
184    fn next(&mut self) -> Option<Self::Item> {
185        self.iter.next().map(|(k, _)| k)
186    }
187}
188
189impl<'a, T: 'a + Eq + Clone> ExactSizeIterator for Iter<'a, T> {
190    fn len(&self) -> usize {
191        self.iter.len()
192    }
193}
194
195impl<'a, T: 'a + Eq + Clone> FusedIterator for Iter<'a, T> {}
196
197impl<T: Eq + Clone> PartialEq<PrefixSet<T>> for PrefixSet<T> {
198    fn eq(&self, other: &PrefixSet<T>) -> bool {
199        self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
200    }
201}
202
203impl<T: Eq + Clone> Eq for PrefixSet<T> {}
204
205impl<T: Eq + Clone + Hash> Hash for PrefixSet<T> {
206    fn hash<H: Hasher>(&self, state: &mut H) {
207        self.iter().for_each(|x| x.hash(state))
208    }
209}
prefix_tree/set.rs

prefix_tree/
set.rs
