non_empty_collections/index_set/
mod.rs

1//! Non-empty hash set implementation.
2
3#[cfg(feature = "serde_support")]
4mod deserialize;
5mod into_iter;
6#[cfg(feature = "serde_support")]
7mod serialize;
8
9pub use self::into_iter::IntoIter;
10use indexmap::IndexSet;
11use std::collections::hash_map::RandomState;
12use std::hash::{BuildHasher, Hash};
13use std::iter::Extend;
14use std::mem::replace;
15use std::{borrow, fmt, iter};
16use {estimated_size, Error};
17
18/// A wrapper around [`::indexmap::IndexSet`] that is guaranteed to have at least one element by the
19/// Rust's type system: it consists of a **first** element and an indexed set (which could be
20/// empty) **rest** elements.
21#[derive(Clone)]
22pub struct NonEmptyIndexSet<K, S = RandomState> {
23    first: K,
24    rest: IndexSet<K, S>,
25}
26
27impl<K> NonEmptyIndexSet<K, RandomState> {
28    /// Creates a set with a default hasher.
29    pub fn new(first: K) -> Self {
30        NonEmptyIndexSet {
31            first,
32            rest: IndexSet::new(),
33        }
34    }
35
36    /// Creates a set with a given capacity.
37    pub fn with_capacity(first: K, capacity: usize) -> Self {
38        NonEmptyIndexSet {
39            first,
40            rest: IndexSet::with_capacity(if capacity == 0 { 0 } else { capacity - 1 }),
41        }
42    }
43
44    /// Creates a set from a given iterator with a default hasher.
45    pub fn from_iterator(i: impl IntoIterator<Item = K>) -> Result<Self, Error>
46    where
47        K: Hash + Eq,
48    {
49        let mut iter = i.into_iter();
50        let first = iter.next().ok_or(Error::EmptyCollection)?;
51        Ok(NonEmptyIndexSet {
52            first,
53            rest: iter.collect(),
54        })
55    }
56}
57
58impl<K, S1, S2> PartialEq<NonEmptyIndexSet<K, S1>> for NonEmptyIndexSet<K, S2>
59where
60    K: Hash + Eq,
61    S1: BuildHasher,
62    S2: BuildHasher,
63{
64    fn eq(&self, other: &NonEmptyIndexSet<K, S1>) -> bool {
65        self.rest.len() == other.rest.len() && self.first == other.first && self.rest == other.rest
66    }
67}
68
69impl<K, S> Eq for NonEmptyIndexSet<K, S>
70where
71    K: Hash + Eq,
72    S: BuildHasher,
73{
74}
75
76impl<K, S> NonEmptyIndexSet<K, S>
77where
78    K: Eq + Hash,
79    S: BuildHasher,
80{
81    /// Creates a set with a given hasher.
82    pub fn with_hasher(first: K, hash_builder: S) -> Self {
83        NonEmptyIndexSet {
84            first,
85            rest: IndexSet::with_hasher(hash_builder),
86        }
87    }
88
89    /// Creates a set with a given capacity.
90    pub fn with_capacity_and_hasher(first: K, capacity: usize, hash_builder: S) -> Self {
91        NonEmptyIndexSet {
92            first,
93            rest: IndexSet::with_capacity_and_hasher(
94                if capacity == 0 { 0 } else { capacity - 1 },
95                hash_builder,
96            ),
97        }
98    }
99
100    /// Iterates over key-value paris of the set in an immutable way.
101    pub fn iter(&self) -> impl Iterator<Item = &K> {
102        iter::once(&self.first).chain(self.rest.iter())
103    }
104
105    /// Creates a set from a given iterator with a given hasher.
106    pub fn from_iter_with_hasher(i: impl IntoIterator<Item = K>, hasher: S) -> Result<Self, Error> {
107        let mut iter = i.into_iter();
108        let first = iter.next().ok_or(Error::EmptyCollection)?;
109        let mut rest = match estimated_size(&iter) {
110            None => IndexSet::with_hasher(hasher),
111            Some(len) => IndexSet::with_capacity_and_hasher(len, hasher),
112        };
113        rest.extend(iter);
114        Ok(NonEmptyIndexSet { first, rest })
115    }
116
117    /// Gets a stored key from the set.
118    pub fn get<Q>(&self, key: &Q) -> Option<&K>
119    where
120        K: borrow::Borrow<Q>,
121        Q: Eq + Hash + ?Sized,
122    {
123        if self.first.borrow() == key {
124            Some(&self.first)
125        } else {
126            self.rest.get(key)
127        }
128    }
129
130    /// Checks whether a given key exists in the set.
131    pub fn contains<Q>(&self, key: &Q) -> bool
132    where
133        K: borrow::Borrow<Q>,
134        Q: Eq + Hash + ?Sized,
135    {
136        if self.first.borrow() == key {
137            true
138        } else {
139            self.rest.contains(key)
140        }
141    }
142
143    /// Removes and returns a value from the set that is equal to a given key, if any.
144    ///
145    /// An attempt to remove the last element will cause an [`Error`] to be returned.
146    pub fn take<Q>(&mut self, key: &Q) -> Result<Option<K>, Error>
147    where
148        K: borrow::Borrow<Q>,
149        Q: Eq + Hash + ?Sized,
150    {
151        if self.first.borrow() == key {
152            let intermediate_element = self.rest.pop().ok_or(Error::EmptyCollection)?;
153            Ok(Some(replace(&mut self.first, intermediate_element)))
154        } else {
155            Ok(self.rest.swap_take(key))
156        }
157    }
158
159    /// Removes a value from the set that is equal to a given key, if any. Returns `true` if the
160    /// value was present in the set.
161    ///
162    /// An attempt to remove the last element will cause an [`Error`] to be returned.
163    pub fn remove<Q>(&mut self, key: &Q) -> Result<bool, Error>
164    where
165        K: borrow::Borrow<Q>,
166        Q: Eq + Hash + ?Sized,
167    {
168        self.take(key).map(|x| x.is_some())
169    }
170
171    /// Adds a value to the set.
172    ///
173    /// If there was no such a value in the set before, `true` is returned.
174    ///
175    /// If the value is in the set already, it remains unchaged and `false` is returned.
176    pub fn insert(&mut self, key: K) -> bool {
177        if self.first == key {
178            false
179        } else {
180            self.rest.insert(key)
181        }
182    }
183
184    /// Replaces a value in the set with a given one. An old value is returned, if any.
185    pub fn replace(&mut self, key: K) -> Option<K> {
186        if self.first == key {
187            Some(replace(&mut self.first, key))
188        } else {
189            self.rest.replace(key)
190        }
191    }
192
193    /// Returns the number of elements in the set.
194    pub fn len(&self) -> usize {
195        self.rest.len() + 1
196    }
197
198    /// Checks whether or not the set is empty.
199    ///
200    /// As one would expect it always evaluates to `false` :)
201    ///
202    /// ```
203    /// # extern crate non_empty_collections;
204    /// # use non_empty_collections::NonEmptyIndexSet;
205    /// # fn main() {
206    /// assert!(!NonEmptyIndexSet::new("key").is_empty());
207    /// # }
208    /// ```
209    pub fn is_empty(&self) -> bool {
210        false
211    }
212
213    /// Gets an immutable reference to the **first** element.
214    pub fn get_first(&self) -> &K {
215        &self.first
216    }
217
218    /// Gets a mutable reference to the **first** element.
219    pub fn get_first_mut(&mut self) -> &mut K {
220        &mut self.first
221    }
222
223    /// Gets an immutable reference to the **rest** indexed set of elements.
224    pub fn get_rest(&self) -> &IndexSet<K, S> {
225        &self.rest
226    }
227
228    /// Gets a mutable reference to the **rest** indexed set of elements.
229    pub fn get_rest_mut(&mut self) -> &mut IndexSet<K, S> {
230        &mut self.rest
231    }
232
233    /// Attempts to remove the first element. Will fail if it is the only one element in the set.
234    pub fn remove_first(&mut self) -> Result<(), Error> {
235        let item = self.rest.pop().ok_or(Error::EmptyCollection)?;
236        self.first = item;
237        Ok(())
238    }
239
240    /// Scans the collection and keeps only the items on which the provided `keep` function
241    /// returns `true`. Will fail if in the end only one element will remain.
242    pub fn retain<F>(&mut self, mut keep: F) -> Result<(), Error>
243    where
244        F: FnMut(&K) -> bool,
245    {
246        while !(keep)(&self.first) {
247            self.remove_first()?;
248        }
249        self.rest.retain(keep);
250        Ok(())
251    }
252}
253
254impl<K: Eq + Hash, S: BuildHasher> Into<IndexSet<K, S>> for NonEmptyIndexSet<K, S> {
255    fn into(self) -> IndexSet<K, S> {
256        let mut set = self.rest;
257        set.insert(self.first);
258        set
259    }
260}
261
262impl<K, S> fmt::Debug for NonEmptyIndexSet<K, S>
263where
264    K: Eq + Hash + fmt::Debug,
265    S: BuildHasher,
266{
267    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
268        f.debug_set().entries(self.iter()).finish()
269    }
270}
271
272impl<K, S> Extend<(K)> for NonEmptyIndexSet<K, S>
273where
274    K: Eq + Hash,
275    S: BuildHasher,
276{
277    fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T) {
278        self.rest.extend(iter)
279    }
280}
281
282impl<K, S> IntoIterator for NonEmptyIndexSet<K, S>
283where
284    K: Eq + Hash,
285    S: BuildHasher,
286{
287    type IntoIter = IntoIter<K>;
288    type Item = K;
289
290    fn into_iter(self) -> Self::IntoIter {
291        IntoIter {
292            iter: iter::once(self.first).chain(self.rest),
293        }
294    }
295}
296
297#[cfg(test)]
298mod tests {
299    use super::*;
300
301    #[test]
302    fn new_and_get() {
303        let set = NonEmptyIndexSet::new(123);
304        assert_eq!(Some(&123), set.get(&123));
305        assert_eq!(None, set.get(&1234));
306        assert_eq!(1, set.len());
307    }
308
309    #[test]
310    fn new_and_contains() {
311        let set = NonEmptyIndexSet::new(123);
312        assert!(set.contains(&123));
313        assert!(!set.contains(&1234));
314        assert_eq!(1, set.len());
315    }
316
317    #[test]
318    fn from_iterator() {
319        assert!(NonEmptyIndexSet::from_iterator(iter::empty::<u8>()).is_err());
320        let set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
321        assert_eq!(Some(&1), set.get(&1));
322        assert_eq!(Some(&2), set.get(&2));
323        assert_eq!(Some(&3), set.get(&3));
324        assert_eq!(Some(&4), set.get(&4));
325        assert_eq!(4, set.len());
326    }
327
328    #[test]
329    fn take() {
330        let mut set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
331        assert_eq!(Ok(Some(3)), set.take(&3));
332        assert_eq!(Ok(None), set.take(&3));
333        assert_eq!(Ok(Some(2)), set.take(&2));
334        assert_eq!(Ok(Some(4)), set.take(&4));
335
336        assert_eq!(Some(&1), set.get(&1));
337        assert_eq!(Err(Error::EmptyCollection), set.take(&1));
338    }
339
340    #[test]
341    fn remove() {
342        let mut set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
343        assert_eq!(Ok(true), set.remove(&3));
344        assert_eq!(Ok(false), set.remove(&3));
345        assert_eq!(Ok(true), set.remove(&2));
346        assert_eq!(Ok(true), set.remove(&4));
347
348        assert_eq!(Some(&1), set.get(&1));
349        assert_eq!(Err(Error::EmptyCollection), set.remove(&1));
350    }
351
352    #[test]
353    fn remove_first() {
354        let mut set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
355        assert_eq!(Ok(()), set.remove_first());
356        assert_eq!(Ok(()), set.remove_first());
357        assert_eq!(Ok(()), set.remove_first());
358        assert_eq!(Err(Error::EmptyCollection), set.remove_first());
359    }
360
361    #[test]
362    fn insert() {
363        let mut set = NonEmptyIndexSet::new(1);
364        assert!(!set.insert(1));
365        assert!(set.insert(2));
366        assert_eq!(Some(&2), set.get(&2));
367        assert!(!set.insert(2));
368    }
369
370    #[test]
371    fn len() {
372        let set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
373        assert_eq!(4, set.len());
374
375        let set = NonEmptyIndexSet::new(10);
376        assert_eq!(1, set.len());
377    }
378
379    #[test]
380    fn get_unsized() {
381        let map = NonEmptyIndexSet::new("Lol");
382        assert_eq!(Some(&"Lol"), map.get(&"Lol"));
383        assert_eq!(Some(&"Lol"), map.get("Lol"));
384    }
385
386    #[test]
387    fn retain() {
388        let original_set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
389        let mut set = original_set.clone();
390        assert_eq!(Ok(()), set.retain(|key| *key < 2));
391        assert_eq!(1, set.len());
392        assert_eq!(Some(&1), set.get(&1));
393        assert_eq!(Err(Error::EmptyCollection), set.retain(|_| false));
394
395        let mut set = original_set.clone();
396        assert_eq!(Ok(()), set.retain(|key| *key > 3));
397        assert_eq!(1, set.len());
398        assert_eq!(Some(&4), set.get(&4));
399        assert_eq!(Err(Error::EmptyCollection), set.retain(|_| false));
400    }
401
402    #[test]
403    fn comparison() {
404        let original_set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
405        assert_eq!(original_set, original_set);
406        for &key in original_set.iter() {
407            let modified_set =
408                NonEmptyIndexSet::from_iterator(original_set.clone().into_iter().map(|key2| {
409                    if key2 == key {
410                        100
411                    } else {
412                        key2
413                    }
414                }))
415                .unwrap();
416            assert_ne!(modified_set, original_set);
417        }
418    }
419}
non_empty_collections/index_set/mod.rs

non_empty_collections/index_set/
mod.rs
