enumoid/
vec.rs

1use crate::EnumIndex;
2use crate::base::EnumArrayHelper;
3use crate::base::EnumSetHelper;
4use crate::base::EnumSize;
5use crate::iter::EnumSliceIter;
6use crate::iter::EnumSliceIterMut;
7use crate::opt_map::EnumOptionMap;
8use crate::sub_base::RawSizeWord;
9use std::convert::TryFrom;
10use std::fmt;
11use std::fmt::Debug;
12use std::hash::Hash;
13use std::iter;
14use std::mem;
15use std::ops::{Index, IndexMut};
16use std::ptr;
17
18/// A vector of values `V` indexed by enumoid `T`.
19pub struct EnumVec<T: EnumArrayHelper<V>, V> {
20  pub(crate) len: T::Word,
21  pub(crate) data: T::PartialArray,
22}
23
24impl<T: EnumArrayHelper<V>, V> EnumVec<T, V> {
25  /// Creates a new vector with no elements.
26  pub fn new() -> Self {
27    EnumVec {
28      len: T::Word::ZERO,
29      data: T::new_partial(),
30    }
31  }
32
33  /// Creates a new vector with a specified number of elements generated by a
34  /// callback function.
35  pub fn new_with<F>(size: EnumSize<T>, mut f: F) -> Self
36  where
37    F: FnMut(T) -> V,
38  {
39    let mut vec = Self::new();
40    for key in size.iter() {
41      let _ = vec.try_push(f(key));
42    }
43    vec
44  }
45
46  /// Returns a slice containing all the values in the vector.
47  #[inline]
48  pub fn as_slice(&self) -> &[V] {
49    unsafe {
50      hint_assert!(
51        self.len <= T::SIZE_WORD,
52        "Length out of bounds: {:?} > {:?}",
53        self.len,
54        T::SIZE
55      );
56      let inited =
57        T::partial_slice(&self.data).get_unchecked(0..self.len.as_());
58      &*(inited as *const [std::mem::MaybeUninit<V>] as *const [V])
59    }
60  }
61
62  /// Returns a mutable slice containing all the values in the vector.
63  #[inline]
64  pub fn as_slice_mut(&mut self) -> &mut [V] {
65    unsafe {
66      hint_assert!(
67        self.len <= T::SIZE_WORD,
68        "Length out of bounds: {:?} > {:?}",
69        self.len,
70        T::SIZE
71      );
72      let inited = T::partial_slice_mut(&mut self.data)
73        .get_unchecked_mut(0..self.len.as_());
74      &mut *(inited as *mut [std::mem::MaybeUninit<V>] as *mut [V])
75    }
76  }
77
78  /// Returns a reference to the value associated with a given index,
79  /// or `None` if the index is beyond the end of the vector.
80  #[inline]
81  pub fn get_by_index(&self, index: EnumIndex<T>) -> Option<&V> {
82    self.as_slice().get(index.into_usize())
83  }
84
85  /// Returns a reference to the value associated with a given key,
86  /// or `None` if the key is beyond the end of the vector.
87  #[inline]
88  pub fn get(&self, key: T) -> Option<&V> {
89    self.get_by_index(key.into())
90  }
91
92  /// Returns a mutable reference to the value associated with a given index,
93  /// or `None` if the index is beyond the end of the vector.
94  #[inline]
95  pub fn get_by_index_mut(&mut self, index: EnumIndex<T>) -> Option<&mut V> {
96    self.as_slice_mut().get_mut(index.into_usize())
97  }
98
99  /// Returns a mutable reference to the value associated with a given key,
100  /// or `None` if the key is beyond the end of the vector.
101  #[inline]
102  pub fn get_mut(&mut self, key: T) -> Option<&mut V> {
103    self.get_by_index_mut(key.into())
104  }
105
106  /// Returns true if the vector is empty.
107  #[inline]
108  pub fn is_empty(&self) -> bool {
109    self.len == T::Word::ZERO
110  }
111
112  /// Returns true if the vector is fully populated.
113  #[inline]
114  pub fn is_full(&self) -> bool {
115    self.len == T::SIZE_WORD
116  }
117
118  /// Returns true if the vector contains the index.
119  #[inline]
120  pub fn contains_index(&self, index: EnumIndex<T>) -> bool {
121    index.into_word() < self.len
122  }
123
124  /// Returns true if the vector contains the key.
125  #[inline]
126  pub fn contains(&self, value: T) -> bool {
127    value.into_word() < self.len
128  }
129
130  /// Returns the size of the vector.
131  #[inline]
132  pub fn size(&self) -> EnumSize<T> {
133    unsafe { EnumSize::from_word_unchecked(self.len) }
134  }
135
136  /// Swaps two elements in the vector by index.
137  ///
138  /// # Panics
139  /// Panics if `a` or `b` are beyond the end of the vector.
140  #[inline]
141  pub fn swap_by_index(&mut self, a: EnumIndex<T>, b: EnumIndex<T>) {
142    self.as_slice_mut().swap(a.into_usize(), b.into_usize())
143  }
144
145  /// Swaps two elements in the vector.
146  ///
147  /// # Panics
148  /// Panics if `a` or `b` are beyond the end of the vector.
149  #[inline]
150  pub fn swap(&mut self, a: T, b: T) {
151    self.swap_by_index(a.into(), b.into())
152  }
153
154  /// Removes an element and returns it, replacing it with the last element.
155  pub fn swap_remove_at_index(&mut self, index: EnumIndex<T>) -> Option<V> {
156    if index.into_word() < self.len {
157      let slice = T::partial_slice_mut(&mut self.data);
158      self.len = self.len.dec();
159      let idx = index.into_usize();
160      unsafe {
161        let value = slice[idx].assume_init_read();
162        if idx != self.len.as_() {
163          slice[idx].write(slice[self.len.as_()].assume_init_read());
164        }
165        Some(value)
166      }
167    } else {
168      None
169    }
170  }
171
172  /// Removes an element and returns it, replacing it with the last element.
173  pub fn swap_remove(&mut self, key: T) -> Option<V> {
174    self.swap_remove_at_index(key.into())
175  }
176
177  /// Removes an element and returns it, moving the following elements down.
178  pub fn remove_at_index(&mut self, index: EnumIndex<T>) -> Option<V> {
179    if index.into_word() < self.len {
180      let slice = T::partial_slice_mut(&mut self.data);
181      let idx = index.into_usize();
182      let value = unsafe {
183        let value = slice[idx].assume_init_read();
184        let ptr = slice.as_mut_ptr().add(idx);
185        ptr::copy(ptr.add(1), ptr, self.len.as_() - idx - 1);
186        value
187      };
188      self.len = self.len.dec();
189      Some(value)
190    } else {
191      None
192    }
193  }
194
195  /// Removes an element and returns it, moving the following elements down.
196  pub fn remove(&mut self, key: T) -> Option<V> {
197    self.remove_at_index(key.into())
198  }
199
200  /// Clears all the elements from the vector.
201  pub fn clear(&mut self) {
202    for cell in
203      T::partial_slice_mut(&mut self.data)[0..self.len.as_()].iter_mut()
204    {
205      unsafe { cell.assume_init_drop() };
206    }
207    self.len = T::Word::ZERO;
208  }
209
210  /// Adds an element to the end of the vector.
211  pub fn try_push(&mut self, value: V) -> Result<(), V> {
212    let len = self.len.as_();
213    if len >= T::SIZE {
214      return Err(value);
215    }
216    T::partial_slice_mut(&mut self.data)[len] =
217      mem::MaybeUninit::<V>::new(value);
218    self.len = self.len.inc();
219    Ok(())
220  }
221
222  /// Removes an element from the end of the vector and returns it,
223  /// or `None` if the vector is empty.
224  pub fn pop(&mut self) -> Option<V> {
225    if self.len == T::Word::ZERO {
226      None
227    } else {
228      let i = self.len.as_() - 1;
229      let cell = &T::partial_slice_mut(&mut self.data)[i];
230      self.len = self.len.dec();
231      Some(unsafe { cell.assume_init_read() })
232    }
233  }
234
235  /// Returns an iterator over the keys and elements.
236  #[inline]
237  pub fn iter(&self) -> EnumSliceIter<'_, T, V> {
238    EnumSliceIter {
239      _phantom: Default::default(),
240      word: T::Word::ZERO,
241      iter: self.as_slice().iter(),
242    }
243  }
244
245  /// Returns a mutable iterator over the keys and elements.
246  #[inline]
247  pub fn iter_mut(&mut self) -> EnumSliceIterMut<'_, T, V> {
248    EnumSliceIterMut {
249      _phantom: Default::default(),
250      word: T::Word::ZERO,
251      iter: self.as_slice_mut().iter_mut(),
252    }
253  }
254}
255
256impl<T: EnumArrayHelper<V> + Debug, V: Debug> Debug for EnumVec<T, V> {
257  fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
258    fmt.debug_map().entries(self.iter()).finish()
259  }
260}
261
262impl<T: EnumArrayHelper<V>, V> Default for EnumVec<T, V> {
263  fn default() -> Self {
264    Self::new()
265  }
266}
267
268impl<T: EnumArrayHelper<V>, V> Drop for EnumVec<T, V> {
269  fn drop(&mut self) {
270    self.clear()
271  }
272}
273
274impl<T: EnumArrayHelper<V>, V: Clone> Clone for EnumVec<T, V> {
275  fn clone(&self) -> Self {
276    let mut clone = Self::new();
277    for value in self.as_slice() {
278      let _ = clone.try_push(value.clone());
279    }
280    clone
281  }
282}
283
284impl<T: EnumArrayHelper<V>, V: PartialEq> PartialEq for EnumVec<T, V> {
285  fn eq(&self, other: &Self) -> bool {
286    self.as_slice() == other.as_slice()
287  }
288}
289
290impl<T: EnumArrayHelper<V>, V: Eq> Eq for EnumVec<T, V> {}
291
292impl<T: EnumArrayHelper<V>, V: Hash> Hash for EnumVec<T, V> {
293  fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
294    self.as_slice().hash(state);
295  }
296}
297
298impl<T: EnumArrayHelper<V>, V> Index<EnumIndex<T>> for EnumVec<T, V> {
299  type Output = V;
300
301  #[inline]
302  fn index(&self, index: EnumIndex<T>) -> &V {
303    &self.as_slice()[index.into_usize()]
304  }
305}
306
307impl<T: EnumArrayHelper<V>, V> Index<T> for EnumVec<T, V> {
308  type Output = V;
309
310  #[inline]
311  fn index(&self, key: T) -> &V {
312    &self[EnumIndex::from_value(key)]
313  }
314}
315
316impl<T: EnumArrayHelper<V>, V> IndexMut<EnumIndex<T>> for EnumVec<T, V> {
317  #[inline]
318  fn index_mut(&mut self, index: EnumIndex<T>) -> &mut V {
319    &mut self.as_slice_mut()[index.into_usize()]
320  }
321}
322
323impl<T: EnumArrayHelper<V>, V> IndexMut<T> for EnumVec<T, V> {
324  #[inline]
325  fn index_mut(&mut self, key: T) -> &mut V {
326    &mut self[EnumIndex::from_value(key)]
327  }
328}
329
330impl<T: EnumArrayHelper<V>, V> iter::FromIterator<V> for EnumVec<T, V> {
331  fn from_iter<I: iter::IntoIterator<Item = V>>(iter: I) -> Self {
332    let mut c = EnumVec::<T, V>::new();
333    for i in iter {
334      if c.try_push(i).is_err() {
335        break;
336      }
337    }
338    c
339  }
340}
341
342impl<T: EnumArrayHelper<V>, V> iter::Extend<V> for EnumVec<T, V> {
343  fn extend<I: iter::IntoIterator<Item = V>>(&mut self, iter: I) {
344    for i in iter {
345      if self.try_push(i).is_err() {
346        break;
347      }
348    }
349  }
350}
351
352impl<'a, T: EnumArrayHelper<V>, V> iter::IntoIterator for &'a EnumVec<T, V> {
353  type Item = (T, &'a V);
354  type IntoIter = EnumSliceIter<'a, T, V>;
355
356  #[inline]
357  fn into_iter(self) -> Self::IntoIter {
358    self.iter()
359  }
360}
361
362impl<'a, T: EnumArrayHelper<V>, V> iter::IntoIterator
363  for &'a mut EnumVec<T, V>
364{
365  type Item = (T, &'a mut V);
366  type IntoIter = EnumSliceIterMut<'a, T, V>;
367
368  #[inline]
369  fn into_iter(self) -> Self::IntoIter {
370    self.iter_mut()
371  }
372}
373
374impl<T: EnumArrayHelper<V>, V> iter::IntoIterator for EnumVec<T, V> {
375  type Item = V;
376  type IntoIter = EnumVecIntoIter<T, V>;
377
378  #[inline]
379  fn into_iter(self) -> Self::IntoIter {
380    // Suppress `EnumVec`'s `Drop` so the elements can be moved out instead.
381    let mut this = mem::ManuallyDrop::new(self);
382    let len = this.len;
383    let data = mem::replace(&mut this.data, T::new_partial());
384    EnumVecIntoIter {
385      data,
386      front: T::Word::ZERO,
387      back: len,
388    }
389  }
390}
391
392/// An owned iterator over the values of a vector.
393///
394/// `front` and `back` delimit the half-open range `front..back` of elements
395/// that have not yet been yielded; `next` advances `front`, `next_back`
396/// retreats `back`, and `Drop` reads out exactly the elements still in that
397/// range.
398pub struct EnumVecIntoIter<T: EnumArrayHelper<V>, V> {
399  data: T::PartialArray,
400  front: T::Word,
401  back: T::Word,
402}
403
404impl<T: EnumArrayHelper<V>, V> Iterator for EnumVecIntoIter<T, V> {
405  type Item = V;
406
407  fn next(&mut self) -> Option<Self::Item> {
408    if self.front == self.back {
409      return None;
410    }
411    let value = unsafe {
412      T::partial_slice_mut(&mut self.data)[self.front.as_()].assume_init_read()
413    };
414    self.front = self.front.inc();
415    Some(value)
416  }
417
418  fn size_hint(&self) -> (usize, Option<usize>) {
419    let remaining = self.back.as_() - self.front.as_();
420    (remaining, Some(remaining))
421  }
422}
423
424impl<T: EnumArrayHelper<V>, V> DoubleEndedIterator for EnumVecIntoIter<T, V> {
425  fn next_back(&mut self) -> Option<Self::Item> {
426    if self.front == self.back {
427      return None;
428    }
429    self.back = self.back.dec();
430    let value = unsafe {
431      T::partial_slice_mut(&mut self.data)[self.back.as_()].assume_init_read()
432    };
433    Some(value)
434  }
435}
436
437impl<T: EnumArrayHelper<V>, V> ExactSizeIterator for EnumVecIntoIter<T, V> {}
438
439impl<T: EnumArrayHelper<V>, V> iter::FusedIterator for EnumVecIntoIter<T, V> {}
440
441impl<T: EnumArrayHelper<V>, V> Drop for EnumVecIntoIter<T, V> {
442  fn drop(&mut self) {
443    let slice = T::partial_slice_mut(&mut self.data);
444    for cell in slice[self.front.as_()..self.back.as_()].iter_mut() {
445      unsafe { cell.assume_init_drop() };
446    }
447  }
448}
449
450impl<T: EnumArrayHelper<V> + EnumSetHelper<u8>, V> TryFrom<EnumOptionMap<T, V>>
451  for EnumVec<T, V>
452{
453  type Error = ();
454  fn try_from(from: EnumOptionMap<T, V>) -> Result<Self, Self::Error> {
455    match from.is_vec() {
456      Some(size) => Ok(EnumVec {
457        len: size.into_word(),
458        data: from.into_partial(),
459      }),
460      None => Err(()),
461    }
462  }
463}
enumoid/vec.rs

enumoid/
vec.rs
