vendor/tinyvec/src-backup/arrayset.rs

   1 #![cfg(feature = "experimental_array_set")]
   2
   3 // This was contributed by user `dhardy`! Big thanks.
   4
   5 use super::{take, Array};
   6 use core::{
   7   borrow::Borrow,
   8   fmt,
   9   mem::swap,
  10   ops::{AddAssign, SubAssign},
  11 };
  12
  13 /// Error resulting from attempting to insert into a full array
  14 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  15 pub struct InsertError;
  16
  17 // TODO(when std): impl std::error::Error for InsertError {}
  18
  19 impl fmt::Display for InsertError {
  20   fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  21     write!(f, "ArraySet: insertion failed")
  22   }
  23 }
  24
  25 /// An array-backed set
  26 ///
  27 /// This set supports `O(n)` operations and has a fixed size, thus may fail to
  28 /// insert items. The potential advantage is a *really* small size.
  29 ///
  30 /// The set is backed by an array of type `A` and indexed by type `L`.
  31 /// The item type must support `Default`.
  32 /// Due to restrictions, `L` may be only `u8` or `u16`.
  33 #[derive(Clone, Debug, Default)]
  34 pub struct ArraySet<A: Array, L> {
  35   arr: A,
  36   len: L,
  37 }
  38
  39 impl<A: Array + Default, L: From<u8>> ArraySet<A, L> {
  40   /// Constructs a new, empty, set
  41   #[inline]
  42   pub fn new() -> Self {
  43     ArraySet { arr: Default::default(), len: 0.into() }
  44   }
  45 }
  46
  47 impl<A: Array, L: Copy + Into<usize>> ArraySet<A, L> {
  48   /// Constructs a new set from given inputs
  49   ///
  50   /// Panics if `len> arr.len()`.
  51   #[inline]
  52   pub fn from(arr: A, len: L) -> Self {
  53     if len.into() > A::CAPACITY {
  54       panic!("ArraySet::from(array, len): len > array.len()");
  55     }
  56     ArraySet { arr, len }
  57   }
  58 }
  59
  60 impl<A: Array, L> ArraySet<A, L>
  61 where
  62   L: Copy + PartialEq + From<u8> + Into<usize>,
  63 {
  64   /// Returns the fixed capacity of the set
  65   #[inline]
  66   pub fn capacity(&self) -> usize {
  67     A::CAPACITY
  68   }
  69
  70   /// Returns the number of elements in the set
  71   #[inline]
  72   pub fn len(&self) -> usize {
  73     self.len.into()
  74   }
  75
  76   /// Returns true when the set contains no elements
  77   #[inline]
  78   pub fn is_empty(&self) -> bool {
  79     self.len == 0.into()
  80   }
  81
  82   /// Removes all elements
  83   #[inline]
  84   pub fn clear(&mut self) {
  85     self.len = 0.into();
  86   }
  87
  88   /// Iterate over all contents
  89   #[inline]
  90   pub fn iter(&self) -> Iter<A::Item> {
  91     Iter { a: self.arr.as_slice(), i: 0 }
  92   }
  93 }
  94
  95 impl<A: Array, L> ArraySet<A, L>
  96 where
  97   L: Copy + PartialOrd + AddAssign + SubAssign + From<u8> + Into<usize>,
  98 {
  99   /// Check whether the set contains `elt`
 100   #[inline]
 101   pub fn contains<Q: Eq + ?Sized>(&self, elt: &Q) -> bool
 102   where
 103     A::Item: Borrow<Q>,
 104   {
 105     self.get(elt).is_some()
 106   }
 107
 108   /// Get a reference to a contained item matching `elt`
 109   pub fn get<Q: Eq + ?Sized>(&self, elt: &Q) -> Option<&A::Item>
 110   where
 111     A::Item: Borrow<Q>,
 112   {
 113     let len: usize = self.len.into();
 114     let arr = self.arr.as_slice();
 115     for i in 0..len {
 116       if arr[i].borrow() == elt {
 117         return Some(&arr[i]);
 118       }
 119     }
 120     None
 121   }
 122
 123   /// Remove an item matching `elt`, if any
 124   pub fn remove<Q: Eq + ?Sized>(&mut self, elt: &Q) -> Option<A::Item>
 125   where
 126     A::Item: Borrow<Q>,
 127   {
 128     let len: usize = self.len.into();
 129     let arr = self.arr.as_slice_mut();
 130     for i in 0..len {
 131       if arr[i].borrow() == elt {
 132         let l1 = len - 1;
 133         if i < l1 {
 134           arr.swap(i, l1);
 135         }
 136         self.len -= L::from(1);
 137         return Some(take(&mut arr[l1]));
 138       }
 139     }
 140     None
 141   }
 142
 143   /// Remove any items for which `f(item) == false`
 144   pub fn retain<F>(&mut self, mut f: F)
 145   where
 146     F: FnMut(&A::Item) -> bool,
 147   {
 148     let mut len = self.len;
 149     let arr = self.arr.as_slice_mut();
 150     let mut i = 0;
 151     while i < len.into() {
 152       if !f(&arr[i]) {
 153         len -= L::from(1);
 154         if i < len.into() {
 155           arr.swap(i, len.into());
 156         }
 157       } else {
 158         i += 1;
 159       }
 160     }
 161     self.len = len;
 162   }
 163 }
 164
 165 impl<A: Array, L> ArraySet<A, L>
 166 where
 167   A::Item: Eq,
 168   L: Copy + PartialOrd + AddAssign + SubAssign + From<u8> + Into<usize>,
 169 {
 170   /// Insert an item
 171   ///
 172   /// Due to the fixed size of the backing array, insertion may fail.
 173   #[inline]
 174   pub fn insert(&mut self, elt: A::Item) -> Result<bool, InsertError> {
 175     if self.contains(&elt) {
 176       return Ok(false);
 177     }
 178
 179     let len = self.len.into();
 180     let arr = self.arr.as_slice_mut();
 181     if len >= arr.len() {
 182       return Err(InsertError);
 183     }
 184     arr[len] = elt;
 185     self.len += L::from(1);
 186     Ok(true)
 187   }
 188
 189   /* Hits borrow checker
 190   pub fn get_or_insert(&mut self, elt: A::Item) -> Result<&A::Item, InsertError> {
 191       if let Some(r) = self.get(&elt) {
 192           return Ok(r);
 193       }
 194       self.insert(elt)?;
 195       let len: usize = self.len.into();
 196       Ok(&self.arr.as_slice()[len - 1])
 197   }
 198   */
 199
 200   /// Replace an item matching `elt` with `elt`, or insert `elt`
 201   ///
 202   /// Returns the replaced item, if any. Fails when there is no matching item
 203   /// and the backing array is full, preventing insertion.
 204   pub fn replace(
 205     &mut self,
 206     mut elt: A::Item,
 207   ) -> Result<Option<A::Item>, InsertError> {
 208     let len: usize = self.len.into();
 209     let arr = self.arr.as_slice_mut();
 210     for i in 0..len {
 211       if arr[i] == elt {
 212         swap(&mut arr[i], &mut elt);
 213         return Ok(Some(elt));
 214       }
 215     }
 216
 217     if len >= arr.len() {
 218       return Err(InsertError);
 219     }
 220     arr[len] = elt;
 221     self.len += L::from(1);
 222     Ok(None)
 223   }
 224 }
 225
 226 /// Type returned by [`ArraySet::iter`]
 227 pub struct Iter<'a, T> {
 228   a: &'a [T],
 229   i: usize,
 230 }
 231
 232 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
 233   #[inline]
 234   fn len(&self) -> usize {
 235     self.a.len() - self.i
 236   }
 237 }
 238
 239 impl<'a, T> Iterator for Iter<'a, T> {
 240   type Item = &'a T;
 241
 242   #[inline]
 243   fn next(&mut self) -> Option<Self::Item> {
 244     if self.i < self.a.len() {
 245       let i = self.i;
 246       self.i += 1;
 247       Some(&self.a[i])
 248     } else {
 249       None
 250     }
 251   }
 252
 253   #[inline]
 254   fn size_hint(&self) -> (usize, Option<usize>) {
 255     let len = self.len();
 256     (len, Some(len))
 257   }
 258 }
 259
 260 #[cfg(test)]
 261 mod test {
 262   use super::*;
 263   use core::mem::size_of;
 264
 265   #[test]
 266   fn test_size() {
 267     assert_eq!(size_of::<ArraySet<[i8; 7], u8>>(), 8);
 268   }
 269
 270   #[test]
 271   fn test() {
 272     let mut set: ArraySet<[i8; 7], u8> = ArraySet::new();
 273     assert_eq!(set.capacity(), 7);
 274
 275     assert_eq!(set.insert(1), Ok(true));
 276     assert_eq!(set.insert(5), Ok(true));
 277     assert_eq!(set.insert(6), Ok(true));
 278     assert_eq!(set.len(), 3);
 279
 280     assert_eq!(set.insert(5), Ok(false));
 281     assert_eq!(set.len(), 3);
 282
 283     assert_eq!(set.replace(1), Ok(Some(1)));
 284     assert_eq!(set.replace(2), Ok(None));
 285     assert_eq!(set.len(), 4);
 286
 287     assert_eq!(set.insert(3), Ok(true));
 288     assert_eq!(set.insert(4), Ok(true));
 289     assert_eq!(set.insert(7), Ok(true));
 290     assert_eq!(set.insert(8), Err(InsertError));
 291     assert_eq!(set.len(), 7);
 292
 293     assert_eq!(set.replace(9), Err(InsertError));
 294
 295     assert_eq!(set.remove(&3), Some(3));
 296     assert_eq!(set.len(), 6);
 297
 298     set.retain(|x| *x == 3 || *x == 6);
 299     assert_eq!(set.len(), 1);
 300     assert!(!set.contains(&3));
 301     assert!(set.contains(&6));
 302   }
 303 }