rama_utils/collections/
non_empty_small_vec.rs

1use serde::{
2    Deserialize, Serialize,
3    de::Error,
4    ser::{SerializeSeq, Serializer},
5};
6use smallvec::SmallVec;
7
8use core::convert::TryFrom;
9use core::iter;
10use core::mem;
11use core::{cmp::Ordering, num::NonZeroUsize};
12
13/// Like the `vec!` macro, but enforces at least one argument. A nice short-hand
14/// for constructing [`NonEmptySmallVec`] values.
15#[macro_export]
16#[doc(hidden)]
17macro_rules! __non_empty_smallvec {
18    ($h:expr, $( $x:expr ),* $(,)?) => {{
19        let tail = $crate::collections::smallvec::smallvec![$($x),*];
20        $crate::collections::NonEmptySmallVec { head: $h, tail }
21    }};
22    ($h:expr, $( $x:expr ),* ; _) => {{
23        let tail = $crate::collections::smallvec::smallvec![$($x),*];
24        const N: usize = $crate::macros::count!($($x)*);
25        $crate::collections::NonEmptySmallVec::<N, _> { head: $h, tail }
26    }};
27    ($h:expr, $( $x:expr ),* ; $N:literal) => {{
28        let tail = $crate::collections::smallvec::smallvec![$($x),*];
29        $crate::collections::NonEmptySmallVec::<$N, _> { head: $h, tail }
30    }};
31    ($h:expr) => {
32        $crate::collections::NonEmptySmallVec {
33            head: $h,
34            tail: $crate::collections::smallvec::smallvec![],
35        }
36    };
37    ($h:expr; _) => {
38        $crate::collections::NonEmptySmallVec {
39            head: $h,
40            tail: $crate::collections::smallvec::SmallVec::<[_; 0]>::new(),
41        }
42    };
43}
44
45/// A Non-empty stack vector which can grow to the heap.
46///
47/// See [`crate::collections::NonEmptyVec`] for more inforamtion,
48/// as it's identical to it except that we make use of a [`SmallVec`]
49/// instead of a [`Vec`] for tail storage.
50///
51/// Note that the total storage is N+1, as N is the size of the tail,
52/// but there's also the head.
53#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
54pub struct NonEmptySmallVec<const N: usize, T> {
55    pub head: T,
56    pub tail: SmallVec<[T; N]>,
57}
58
59impl<const N: usize, T: Serialize> Serialize for NonEmptySmallVec<N, T> {
60    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
61    where
62        S: Serializer,
63    {
64        let mut seq = serializer.serialize_seq(Some(self.len()))?;
65        for e in self {
66            seq.serialize_element(e)?;
67        }
68        seq.end()
69    }
70}
71
72impl<'de, const N: usize, T: Deserialize<'de>> Deserialize<'de> for NonEmptySmallVec<N, T> {
73    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
74    where
75        D: serde::Deserializer<'de>,
76    {
77        <SmallVec<[T; N]>>::deserialize(deserializer)?
78            .try_into()
79            .map_err(D::Error::custom)
80    }
81}
82
83/// Iterator for [`NonEmptySmallVec`].
84pub struct NonEmptySmallVecIter<'a, T> {
85    head: Option<&'a T>,
86    tail: &'a [T],
87}
88
89impl<'a, T> Iterator for NonEmptySmallVecIter<'a, T> {
90    type Item = &'a T;
91
92    fn next(&mut self) -> Option<Self::Item> {
93        if let Some(value) = self.head.take() {
94            Some(value)
95        } else if let Some((first, rest)) = self.tail.split_first() {
96            self.tail = rest;
97            Some(first)
98        } else {
99            None
100        }
101    }
102}
103
104impl<T> DoubleEndedIterator for NonEmptySmallVecIter<'_, T> {
105    fn next_back(&mut self) -> Option<Self::Item> {
106        if let Some((last, rest)) = self.tail.split_last() {
107            self.tail = rest;
108            Some(last)
109        } else if let Some(first_value) = self.head.take() {
110            Some(first_value)
111        } else {
112            None
113        }
114    }
115}
116
117impl<T> ExactSizeIterator for NonEmptySmallVecIter<'_, T> {
118    fn len(&self) -> usize {
119        self.tail.len() + self.head.map_or(0, |_| 1)
120    }
121}
122
123impl<T> core::iter::FusedIterator for NonEmptySmallVecIter<'_, T> {}
124
125impl<const N: usize, T> NonEmptySmallVec<N, T> {
126    /// Alias for [`NonEmptySmallVec::singleton`].
127    pub fn new(e: T) -> Self {
128        Self::singleton(e)
129    }
130
131    /// Converts from `&NonEmptySmallVec<N, T>` to `NonEmptySmallVec<N, &T>`,
132    /// allocating a new tail of borrows. Named `to_` (not `as_`) because it is
133    /// not a free view.
134    pub fn to_ref(&self) -> NonEmptySmallVec<N, &T> {
135        NonEmptySmallVec {
136            head: &self.head,
137            tail: self.tail.iter().collect(),
138        }
139    }
140
141    /// Attempt to convert an iterator into a `NonEmptySmallVec` vector.
142    /// Returns `None` if the iterator was empty.
143    pub fn collect<I>(iter: I) -> Option<Self>
144    where
145        I: IntoIterator<Item = T>,
146    {
147        let mut iter = iter.into_iter();
148        let head = iter.next()?;
149        Some(Self {
150            head,
151            tail: iter.collect(),
152        })
153    }
154
155    /// Create a new non-empty list with an initial element.
156    pub fn singleton(head: T) -> Self {
157        Self {
158            head,
159            tail: SmallVec::new(),
160        }
161    }
162
163    /// Always returns false.
164    pub const fn is_empty(&self) -> bool {
165        false
166    }
167
168    /// Get the first element. Never fails.
169    pub const fn first(&self) -> &T {
170        &self.head
171    }
172
173    /// Get the mutable reference to the first element. Never fails.
174    pub fn first_mut(&mut self) -> &mut T {
175        &mut self.head
176    }
177
178    /// Get the possibly-empty tail of the list.
179    pub fn tail(&self) -> &[T] {
180        &self.tail
181    }
182
183    /// Push an element to the end of the list.
184    pub fn push(&mut self, e: T) {
185        self.tail.push(e)
186    }
187
188    /// Pop an element from the end of the list.
189    pub fn pop(&mut self) -> Option<T> {
190        self.tail.pop()
191    }
192
193    /// Inserts an element at position index within the vector, shifting all elements after it to the right.
194    ///
195    /// # Panics
196    ///
197    /// Panics if index > len.
198    pub fn insert(&mut self, index: usize, element: T) {
199        let len = self.len();
200        assert!(index <= len);
201
202        if index == 0 {
203            let head = mem::replace(&mut self.head, element);
204            self.tail.insert(0, head);
205        } else {
206            self.tail.insert(index - 1, element);
207        }
208    }
209
210    /// Get the length of the list.
211    pub fn len(&self) -> usize {
212        self.tail.len() + 1
213    }
214
215    /// Gets the length of the list as a NonZeroUsize.
216    pub fn len_nonzero(&self) -> NonZeroUsize {
217        unsafe { NonZeroUsize::new_unchecked(self.tail.len().saturating_add(1)) }
218    }
219
220    /// Get the capacity of the list.
221    pub fn capacity(&self) -> NonZeroUsize {
222        NonZeroUsize::MIN.saturating_add(self.tail.capacity())
223    }
224
225    /// Get the last element. Never fails.
226    pub fn last(&self) -> &T {
227        match self.tail.last() {
228            None => &self.head,
229            Some(e) => e,
230        }
231    }
232
233    /// Get the last element mutably.
234    pub fn last_mut(&mut self) -> &mut T {
235        match self.tail.last_mut() {
236            None => &mut self.head,
237            Some(e) => e,
238        }
239    }
240
241    /// Check whether an element is contained in the list.
242    pub fn contains(&self, x: &T) -> bool
243    where
244        T: PartialEq,
245    {
246        self.iter().any(|e| e == x)
247    }
248
249    /// Get an element by index.
250    pub fn get(&self, index: usize) -> Option<&T> {
251        if index == 0 {
252            Some(&self.head)
253        } else {
254            self.tail.get(index - 1)
255        }
256    }
257
258    /// Get an element by index, mutably.
259    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
260        if index == 0 {
261            Some(&mut self.head)
262        } else {
263            self.tail.get_mut(index - 1)
264        }
265    }
266
267    /// Truncate the list to a certain size. Must be greater than `0`.
268    pub fn truncate(&mut self, len: NonZeroUsize) {
269        self.tail.truncate(len.get() - 1);
270    }
271
272    pub fn iter(&self) -> NonEmptySmallVecIter<'_, T> {
273        NonEmptySmallVecIter {
274            head: Some(&self.head),
275            tail: &self.tail,
276        }
277    }
278
279    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> + '_ {
280        iter::once(&mut self.head).chain(self.tail.iter_mut())
281    }
282
283    /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmptySmallVec` before
284    /// proceeding with a computation. Using `from_slice` will give us a proof
285    /// that we have a `NonEmptySmallVec` in the `Some` branch, otherwise it allows
286    /// the caller to handle the `None` case.
287    pub fn from_slice(slice: &[T]) -> Option<Self>
288    where
289        T: Clone,
290    {
291        slice.split_first().map(|(h, t)| Self {
292            head: h.clone(),
293            tail: t.into(),
294        })
295    }
296
297    /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmptySmallVec` before
298    /// proceeding with a computation. Using `from_smallvec` will give us a proof
299    /// that we have a `NonEmptySmallVec` in the `Some` branch, otherwise it allows
300    /// the caller to handle the `None` case.
301    ///
302    /// This version will consume the `Vec` you pass in. If you would rather pass the data as a
303    /// slice then use `NonEmptySmallVec::from_slice`.
304    #[must_use]
305    pub fn from_smallvec(mut vec: SmallVec<[T; N]>) -> Option<Self> {
306        if vec.is_empty() {
307            None
308        } else {
309            let head = vec.remove(0);
310            Some(Self { head, tail: vec })
311        }
312    }
313
314    /// Deconstruct a `NonEmptySmallVec` into its head and tail.
315    /// This operation never fails since we are guaranteed
316    /// to have a head element.
317    pub fn split_first(&self) -> (&T, &[T]) {
318        (&self.head, &self.tail)
319    }
320
321    /// Deconstruct a `NonEmptySmallVec` into its first, last, and
322    /// middle elements, in that order.
323    ///
324    /// If there is only one element then last is `None`.
325    pub fn split(&self) -> (&T, &[T], Option<&T>) {
326        match self.tail.split_last() {
327            None => (&self.head, &[], None),
328            Some((last, middle)) => (&self.head, middle, Some(last)),
329        }
330    }
331
332    /// Append a `Vec` to the tail of the `NonEmptySmallVec`.
333    pub fn append(&mut self, other: &mut SmallVec<[T; N]>) {
334        self.tail.append(other)
335    }
336
337    /// A structure preserving `map`. This is useful for when
338    /// we wish to keep the `NonEmptySmallVec` structure guaranteeing
339    /// that there is at least one element. Otherwise, we can
340    /// use `non_empty_smallvec.iter().map(f)`.
341    pub fn map<U, F>(self, mut f: F) -> NonEmptySmallVec<N, U>
342    where
343        F: FnMut(T) -> U,
344    {
345        NonEmptySmallVec {
346            head: f(self.head),
347            tail: self.tail.into_iter().map(f).collect(),
348        }
349    }
350
351    /// A structure preserving, fallible mapping function.
352    pub fn try_map<E, U, F>(self, mut f: F) -> Result<NonEmptySmallVec<N, U>, E>
353    where
354        F: FnMut(T) -> Result<U, E>,
355    {
356        Ok(NonEmptySmallVec {
357            head: f(self.head)?,
358            tail: self.tail.into_iter().map(f).collect::<Result<_, _>>()?,
359        })
360    }
361
362    /// When we have a function that goes from some `T` to a `NonEmptySmallVec<U>`,
363    /// we may want to apply it to a `NonEmptySmallVec<T>` but keep the structure flat.
364    /// This is where `flat_map` shines.
365    pub fn flat_map<U, F>(self, mut f: F) -> NonEmptySmallVec<N, U>
366    where
367        F: FnMut(T) -> NonEmptySmallVec<N, U>,
368    {
369        let mut heads = f(self.head);
370        let mut tails = self
371            .tail
372            .into_iter()
373            .flat_map(|t| f(t).into_iter())
374            .collect();
375        heads.append(&mut tails);
376        heads
377    }
378
379    /// Flatten nested `NonEmptySmallVec`s into a single one.
380    pub fn flatten(full: NonEmptySmallVec<N, Self>) -> Self {
381        full.flat_map(|n| n)
382    }
383
384    /// Binary searches this sorted non-empty vector for a given element.
385    ///
386    /// If the value is found then Result::Ok is returned, containing the index of the matching element.
387    /// If there are multiple matches, then any one of the matches could be returned.
388    ///
389    /// If the value is not found then Result::Err is returned, containing the index where a
390    /// matching element could be inserted while maintaining sorted order.
391    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
392    where
393        T: Ord,
394    {
395        self.binary_search_by(|p| p.cmp(x))
396    }
397
398    /// Binary searches this sorted non-empty with a comparator function.
399    ///
400    /// The comparator function should implement an order consistent with the sort order of the underlying slice,
401    /// returning an order code that indicates whether its argument is Less, Equal or Greater the desired target.
402    ///
403    /// If the value is found then Result::Ok is returned, containing the index of the matching element.
404    /// If there are multiple matches, then any one of the matches could be returned.
405    /// If the value is not found then Result::Err is returned, containing the index where a matching element could be
406    /// inserted while maintaining sorted order.
407    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
408    where
409        F: FnMut(&'a T) -> Ordering,
410    {
411        match f(&self.head) {
412            Ordering::Equal => Ok(0),
413            Ordering::Greater => Err(0),
414            Ordering::Less => self
415                .tail
416                .binary_search_by(f)
417                .map(|index| index + 1)
418                .map_err(|index| index + 1),
419        }
420    }
421
422    /// Binary searches this sorted non-empty vector with a key extraction function.
423    ///
424    /// Assumes that the vector is sorted by the key.
425    ///
426    /// If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches,
427    /// then any one of the matches could be returned. If the value is not found then Result::Err is returned,
428    /// containing the index where a matching element could be inserted while maintaining sorted order.
429    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
430    where
431        B: Ord,
432        F: FnMut(&'a T) -> B,
433    {
434        self.binary_search_by(|k| f(k).cmp(b))
435    }
436
437    /// Returns the maximum element in the non-empty vector.
438    ///
439    /// This will return the first item in the vector if the tail is empty.
440    pub fn maximum(&self) -> &T
441    where
442        T: Ord,
443    {
444        self.maximum_by(|i, j| i.cmp(j))
445    }
446
447    /// Returns the minimum element in the non-empty vector.
448    ///
449    /// This will return the first item in the vector if the tail is empty.
450    pub fn minimum(&self) -> &T
451    where
452        T: Ord,
453    {
454        self.minimum_by(|i, j| i.cmp(j))
455    }
456
457    /// Returns the element that gives the maximum value with respect to the specified comparison function.
458    ///
459    /// This will return the first item in the vector if the tail is empty.
460    pub fn maximum_by<F>(&self, mut compare: F) -> &T
461    where
462        F: FnMut(&T, &T) -> Ordering,
463    {
464        let mut max = &self.head;
465        for i in self.tail.iter() {
466            max = match compare(max, i) {
467                Ordering::Equal | Ordering::Greater => max,
468                Ordering::Less => i,
469            };
470        }
471        max
472    }
473
474    /// Returns the element that gives the minimum value with respect to the specified comparison function.
475    ///
476    /// This will return the first item in the vector if the tail is empty.
477    pub fn minimum_by<F>(&self, mut compare: F) -> &T
478    where
479        F: FnMut(&T, &T) -> Ordering,
480    {
481        self.maximum_by(|a, b| compare(a, b).reverse())
482    }
483
484    /// Returns the element that gives the maximum value with respect to the specified function.
485    ///
486    /// This will return the first item in the vector if the tail is empty.
487    pub fn maximum_by_key<U, F>(&self, mut f: F) -> &T
488    where
489        U: Ord,
490        F: FnMut(&T) -> U,
491    {
492        self.maximum_by(|i, j| f(i).cmp(&f(j)))
493    }
494
495    /// Returns the element that gives the minimum value with respect to the specified function.
496    ///
497    /// This will return the first item in the vector if the tail is empty.
498    pub fn minimum_by_key<U, F>(&self, mut f: F) -> &T
499    where
500        U: Ord,
501        F: FnMut(&T) -> U,
502    {
503        self.minimum_by(|i, j| f(i).cmp(&f(j)))
504    }
505
506    /// Sorts the [`NonEmptySmallVec`].
507    ///
508    /// The implementation uses [`slice::sort`](slice::sort) for the tail and then checks where the
509    /// head belongs. If the head is already the smallest element, this should be as fast as sorting a
510    /// slice. However, if the head needs to be inserted, then it incurs extra cost for removing
511    /// the new head from the tail and adding the old head at the correct index.
512    pub fn sort(&mut self)
513    where
514        T: Ord,
515    {
516        self.tail.sort();
517        place_sorted_head!(self, self.tail.partition_point(|x| x < &self.head));
518    }
519
520    /// Sorts the [`NonEmptySmallVec`] with a comparator function.
521    ///
522    /// The implementation uses [`slice::sort_by`](slice::sort_by) for the tail and then checks where
523    /// the head belongs. If the head is already the smallest element, this should be as fast as sorting
524    /// a slice. However, if the head needs to be inserted, then it incurs extra cost for removing the
525    /// new head from the tail and adding the old head at the correct index.
526    pub fn sort_by<F>(&mut self, mut compare: F)
527    where
528        F: FnMut(&T, &T) -> Ordering,
529    {
530        self.tail.sort_by(&mut compare);
531
532        place_sorted_head!(
533            self,
534            self.tail
535                .partition_point(|x| compare(x, &self.head) == Ordering::Less)
536        );
537    }
538
539    /// Sorts the [`NonEmptySmallVec`] with a key extraction function.
540    pub fn sort_by_key<K, F>(&mut self, mut f: F)
541    where
542        F: FnMut(&T) -> K,
543        K: Ord,
544    {
545        self.tail.sort_by_key(&mut f);
546
547        let head_key = f(&self.head);
548        place_sorted_head!(self, self.tail.partition_point(|x| f(x) < head_key));
549    }
550
551    /// Sorts the [`NonEmptySmallVec`] with a key extraction function, caching the keys.
552    ///
553    /// The implementation uses [`slice::sort_by_cached_key`](slice::sort_by_cached_key)
554    /// for the tail and then determines where the head belongs using the cached head key.
555    pub fn sort_by_cached_key<K, F>(&mut self, mut f: F)
556    where
557        F: FnMut(&T) -> K,
558        K: Ord,
559    {
560        self.tail.sort_by_cached_key(&mut f);
561
562        let head_key = f(&self.head);
563        place_sorted_head!(self, self.tail.partition_point(|x| f(x) < head_key));
564    }
565}
566
567impl<const N: usize, T: Default> Default for NonEmptySmallVec<N, T> {
568    fn default() -> Self {
569        Self::new(T::default())
570    }
571}
572
573impl<const N: usize, T> From<NonEmptySmallVec<N, T>> for SmallVec<[T; N]> {
574    /// Turns a non-empty list into a Vec.
575    fn from(non_empty_smallvec: NonEmptySmallVec<N, T>) -> Self {
576        let NonEmptySmallVec { head, mut tail } = non_empty_smallvec;
577        tail.insert(0, head);
578        tail
579    }
580}
581
582impl<const N: usize, T> From<NonEmptySmallVec<N, T>> for (T, SmallVec<[T; N]>) {
583    /// Turns a non-empty list into a SmallVec.
584    fn from(non_empty_smallvec: NonEmptySmallVec<N, T>) -> (T, SmallVec<[T; N]>) {
585        (non_empty_smallvec.head, non_empty_smallvec.tail)
586    }
587}
588
589impl<const N: usize, T> From<(T, SmallVec<[T; N]>)> for NonEmptySmallVec<N, T> {
590    /// Turns a pair of an element and a Vec into
591    /// a NonEmptySmallVec.
592    fn from((head, tail): (T, SmallVec<[T; N]>)) -> Self {
593        Self { head, tail }
594    }
595}
596
597impl<const N: usize, T> IntoIterator for NonEmptySmallVec<N, T> {
598    type Item = T;
599    type IntoIter = iter::Chain<iter::Once<T>, smallvec::IntoIter<[Self::Item; N]>>;
600
601    fn into_iter(self) -> Self::IntoIter {
602        iter::once(self.head).chain(self.tail)
603    }
604}
605
606impl<'a, const N: usize, T> IntoIterator for &'a NonEmptySmallVec<N, T> {
607    type Item = &'a T;
608    type IntoIter = iter::Chain<iter::Once<&'a T>, core::slice::Iter<'a, T>>;
609
610    fn into_iter(self) -> Self::IntoIter {
611        iter::once(&self.head).chain(self.tail.iter())
612    }
613}
614
615impl<const N: usize, T> core::ops::Index<usize> for NonEmptySmallVec<N, T> {
616    type Output = T;
617
618    fn index(&self, index: usize) -> &T {
619        if index > 0 {
620            &self.tail[index - 1]
621        } else {
622            &self.head
623        }
624    }
625}
626
627impl<const N: usize, T> core::ops::IndexMut<usize> for NonEmptySmallVec<N, T> {
628    fn index_mut(&mut self, index: usize) -> &mut T {
629        if index > 0 {
630            &mut self.tail[index - 1]
631        } else {
632            &mut self.head
633        }
634    }
635}
636
637impl<const N: usize, A> Extend<A> for NonEmptySmallVec<N, A> {
638    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
639        self.tail.extend(iter)
640    }
641}
642
643impl<const N: usize, T> TryFrom<SmallVec<[T; N]>> for NonEmptySmallVec<N, T> {
644    type Error = NonEmptySmallVecEmptyError;
645
646    fn try_from(vec: SmallVec<[T; N]>) -> Result<Self, Self::Error> {
647        Self::from_smallvec(vec).ok_or(NonEmptySmallVecEmptyError)
648    }
649}
650
651crate::macros::error::static_str_error! {
652    #[doc = "empty value cannot be turned into a NonEmptySmallVec"]
653    pub struct NonEmptySmallVecEmptyError;
654}
655
656#[cfg(test)]
657mod tests {
658    use super::*;
659    use crate::collections::non_empty_smallvec;
660    use smallvec::smallvec;
661
662    #[test]
663    fn test_from_conversion() {
664        let result: NonEmptySmallVec<4, _> = NonEmptySmallVec::from((1, smallvec![2, 3, 4, 5]));
665        let expected: NonEmptySmallVec<4, _> = NonEmptySmallVec {
666            head: 1,
667            tail: smallvec![2, 3, 4, 5],
668        };
669        assert_eq!(result, expected);
670    }
671
672    #[test]
673    fn test_into_iter() {
674        let non_empty_smallvec: NonEmptySmallVec<3, _> =
675            NonEmptySmallVec::from((0, smallvec![1, 2, 3]));
676        for (i, n) in non_empty_smallvec.into_iter().enumerate() {
677            assert_eq!(i as i32, n);
678        }
679    }
680
681    #[test]
682    fn test_iter_syntax() {
683        let non_empty_smallvec: NonEmptySmallVec<3, _> =
684            NonEmptySmallVec::from((0, smallvec![1, 2, 3]));
685        for n in &non_empty_smallvec {
686            _ = *n; // Prove that we're dealing with references.
687        }
688        for _ in non_empty_smallvec {}
689    }
690
691    #[test]
692    fn test_iter_both_directions() {
693        let mut non_empty_smallvec: NonEmptySmallVec<3, _> =
694            NonEmptySmallVec::from((0, smallvec![1, 2, 3]));
695        assert_eq!(
696            non_empty_smallvec.iter().cloned().collect::<Vec<_>>(),
697            [0, 1, 2, 3]
698        );
699        assert_eq!(
700            non_empty_smallvec.iter().rev().cloned().collect::<Vec<_>>(),
701            [3, 2, 1, 0]
702        );
703        assert_eq!(
704            non_empty_smallvec.iter_mut().rev().collect::<Vec<_>>(),
705            [&mut 3, &mut 2, &mut 1, &mut 0]
706        );
707    }
708
709    #[test]
710    fn test_iter_both_directions_at_once() {
711        let non_empty_smallvec: NonEmptySmallVec<3, _> =
712            NonEmptySmallVec::from((0, smallvec![1, 2, 3]));
713        let mut i = non_empty_smallvec.iter();
714        assert_eq!(i.next(), Some(&0));
715        assert_eq!(i.next_back(), Some(&3));
716        assert_eq!(i.next(), Some(&1));
717        assert_eq!(i.next_back(), Some(&2));
718        assert_eq!(i.next(), None);
719        assert_eq!(i.next_back(), None);
720    }
721
722    #[test]
723    fn test_mutate_head() {
724        let mut non_empty: NonEmptySmallVec<0, _> = NonEmptySmallVec::new(42);
725        non_empty.head += 1;
726        assert_eq!(non_empty.head, 43);
727
728        let mut non_empty: NonEmptySmallVec<3, _> = NonEmptySmallVec::from((1, smallvec![4, 2, 3]));
729        non_empty.head *= 42;
730        assert_eq!(non_empty.head, 42);
731    }
732
733    #[test]
734    fn test_to_nonempty() {
735        use std::iter::{empty, once};
736
737        assert_eq!(NonEmptySmallVec::<0, ()>::collect(empty()), None);
738        assert_eq!(
739            NonEmptySmallVec::<0, ()>::collect(once(())),
740            Some(NonEmptySmallVec::new(()))
741        );
742        assert_eq!(
743            NonEmptySmallVec::<1, u8>::collect(once(1).chain(once(2))),
744            Some(non_empty_smallvec!(1, 2))
745        );
746    }
747
748    #[test]
749    fn test_try_map() {
750        assert_eq!(
751            non_empty_smallvec!(1, 2, 3, 4; 4).try_map(Ok::<_, String>),
752            Ok(non_empty_smallvec!(1, 2, 3, 4; 4))
753        );
754        assert_eq!(
755            non_empty_smallvec!(1, 2, 3, 4; 4).try_map(|i| if i % 2 == 0 {
756                Ok(i)
757            } else {
758                Err("not even")
759            }),
760            Err("not even")
761        );
762    }
763
764    #[test]
765    fn test_nontrivial_minimum_by_key() {
766        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
767        struct Position {
768            x: i32,
769            y: i32,
770        }
771        impl Position {
772            pub(super) fn distance_squared(self, other: Self) -> u32 {
773                let dx = self.x - other.x;
774                let dy = self.y - other.y;
775                (dx * dx + dy * dy) as u32
776            }
777        }
778        let positions = non_empty_smallvec![
779            Position { x: 1, y: 1 },
780            Position { x: 0, y: 0 },
781            Position { x: 3, y: 4 }
782            ; _
783        ];
784        let target = Position { x: 1, y: 2 };
785        let closest = positions.minimum_by_key(|position| position.distance_squared(target));
786        assert_eq!(closest, &Position { x: 1, y: 1 });
787    }
788
789    #[test]
790    fn test_sort() {
791        let mut numbers = non_empty_smallvec![1; _];
792        numbers.sort();
793        assert_eq!(numbers, non_empty_smallvec![1; _]);
794
795        let mut numbers = non_empty_smallvec![2, 1, 3; _];
796        numbers.sort();
797        assert_eq!(numbers, non_empty_smallvec![1, 2, 3; _]);
798
799        let mut numbers = non_empty_smallvec![1, 3, 2; _];
800        numbers.sort();
801        assert_eq!(numbers, non_empty_smallvec![1, 2, 3; _]);
802
803        let mut numbers = non_empty_smallvec![3, 2, 1; _];
804        numbers.sort();
805        assert_eq!(numbers, non_empty_smallvec![1, 2, 3; _]);
806    }
807
808    #[derive(Debug, Deserialize, Eq, PartialEq, Serialize)]
809    struct SimpleSerializable(pub i32);
810
811    #[test]
812    fn test_simple_round_trip() -> Result<(), Box<dyn std::error::Error>> {
813        // Given
814        let mut non_empty = NonEmptySmallVec::new(SimpleSerializable(42));
815        non_empty.push(SimpleSerializable(777));
816
817        // When
818        let res = serde_json::from_str::<'_, NonEmptySmallVec<8, SimpleSerializable>>(
819            &serde_json::to_string(&non_empty)?,
820        )?;
821
822        // Then
823        assert_eq!(res, non_empty);
824
825        Ok(())
826    }
827
828    #[test]
829    fn test_serialization() -> Result<(), Box<dyn std::error::Error>> {
830        let ne = non_empty_smallvec![1, 2, 3, 4, 5; _];
831        let ve: SmallVec<[_; 5]> = smallvec![1, 2, 3, 4, 5];
832
833        assert_eq!(serde_json::to_string(&ne)?, serde_json::to_string(&ve)?);
834
835        Ok(())
836    }
837}
rama_utils/collections/non_empty_small_vec.rs

rama_utils/collections/
non_empty_small_vec.rs
