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> { new() -> Self14 pub(crate) fn new() -> Self { 15 Default::default() 16 } 17 insert(&mut self, value: T) -> bool18 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 contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Eq,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 retain<F>(&mut self, f: F) where F: FnMut(&T) -> bool,41 pub fn retain<F>(&mut self, f: F) 42 where 43 F: FnMut(&T) -> bool, 44 { 45 self.inner.retain(f); 46 } 47 is_empty(&self) -> bool48 pub(crate) fn is_empty(&self) -> bool { 49 self.inner.is_empty() 50 } 51 iter(&self) -> std::slice::Iter<'_, T>52 pub(crate) fn iter(&self) -> std::slice::Iter<'_, T> { 53 self.inner.iter() 54 } 55 sort_by_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord,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> { default() -> Self66 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 into_iter(self) -> Self::IntoIter77 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 into_iter(self) -> Self::IntoIter86 fn into_iter(self) -> Self::IntoIter { 87 self.inner.iter() 88 } 89 } 90 91 impl<T: PartialEq + Eq> Extend<T> for FlatSet<T> { extend<I: IntoIterator<Item = T>>(&mut self, iter: I)92 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { 93 for value in iter { 94 self.insert(value); 95 } 96 } 97 } 98 99 impl<T: PartialEq + Eq> FromIterator<T> for FlatSet<T> { from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self100 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { 101 let mut set = Self::new(); 102 for value in iter { 103 set.insert(value); 104 } 105 set 106 } 107 } 108