1 | #![allow (dead_code)] |
2 | |
3 | use std::borrow::Borrow; |
4 | |
5 | /// Flat (Vec) backed set |
6 | /// |
7 | /// This preserves insertion order |
8 | #[derive (Clone, Debug, PartialEq, Eq)] |
9 | pub(crate) struct FlatSet<T> { |
10 | inner: Vec<T>, |
11 | } |
12 | |
13 | impl<T: PartialEq + Eq> FlatSet<T> { |
14 | pub(crate) fn new() -> Self { |
15 | Default::default() |
16 | } |
17 | |
18 | pub(crate) fn insert(&mut self, value: T) -> bool { |
19 | for existing in &self.inner { |
20 | if *existing == value { |
21 | return false; |
22 | } |
23 | } |
24 | self.inner.push(value); |
25 | true |
26 | } |
27 | |
28 | pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool |
29 | where |
30 | T: Borrow<Q>, |
31 | Q: Eq, |
32 | { |
33 | for existing in &self.inner { |
34 | if existing.borrow() == value { |
35 | return true; |
36 | } |
37 | } |
38 | false |
39 | } |
40 | |
41 | pub fn retain<F>(&mut self, f: F) |
42 | where |
43 | F: FnMut(&T) -> bool, |
44 | { |
45 | self.inner.retain(f); |
46 | } |
47 | |
48 | pub(crate) fn is_empty(&self) -> bool { |
49 | self.inner.is_empty() |
50 | } |
51 | |
52 | pub(crate) fn iter(&self) -> std::slice::Iter<'_, T> { |
53 | self.inner.iter() |
54 | } |
55 | |
56 | pub fn sort_by_key<K, F>(&mut self, f: F) |
57 | where |
58 | F: FnMut(&T) -> K, |
59 | K: Ord, |
60 | { |
61 | self.inner.sort_by_key(f); |
62 | } |
63 | } |
64 | |
65 | impl<T: PartialEq + Eq> Default for FlatSet<T> { |
66 | fn default() -> Self { |
67 | Self { |
68 | inner: Default::default(), |
69 | } |
70 | } |
71 | } |
72 | |
73 | impl<T: PartialEq + Eq> IntoIterator for FlatSet<T> { |
74 | type Item = T; |
75 | type IntoIter = std::vec::IntoIter<T>; |
76 | |
77 | fn into_iter(self) -> Self::IntoIter { |
78 | self.inner.into_iter() |
79 | } |
80 | } |
81 | |
82 | impl<'s, T: PartialEq + Eq> IntoIterator for &'s FlatSet<T> { |
83 | type Item = &'s T; |
84 | type IntoIter = std::slice::Iter<'s, T>; |
85 | |
86 | fn into_iter(self) -> Self::IntoIter { |
87 | self.inner.iter() |
88 | } |
89 | } |
90 | |
91 | impl<T: PartialEq + Eq> Extend<T> for FlatSet<T> { |
92 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { |
93 | for value: T in iter { |
94 | self.insert(value); |
95 | } |
96 | } |
97 | } |
98 | |
99 | impl<T: PartialEq + Eq> FromIterator<T> for FlatSet<T> { |
100 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { |
101 | let mut set: FlatSet = Self::new(); |
102 | for value: T in iter { |
103 | set.insert(value); |
104 | } |
105 | set |
106 | } |
107 | } |
108 | |