diff options
Diffstat (limited to 'vendor/nonempty/src/lib.rs')
| -rw-r--r-- | vendor/nonempty/src/lib.rs | 1206 |
1 files changed, 1206 insertions, 0 deletions
diff --git a/vendor/nonempty/src/lib.rs b/vendor/nonempty/src/lib.rs new file mode 100644 index 00000000..f95197c7 --- /dev/null +++ b/vendor/nonempty/src/lib.rs @@ -0,0 +1,1206 @@ +//! A Non-empty growable vector. +//! +//! Non-emptiness can be a powerful guarantee. If your main use of `Vec` is as +//! an `Iterator`, then you may not need to distinguish on emptiness. But there +//! are indeed times when the `Vec` you receive as as function argument needs to +//! be non-empty or your function can't proceed. Similarly, there are times when +//! the `Vec` you return to a calling user needs to promise it actually contains +//! something. +//! +//! With `NonEmpty`, you're freed from the boilerplate of constantly needing to +//! check `is_empty()` or pattern matching before proceeding, or erroring if you +//! can't. So overall, code, type signatures, and logic become cleaner. +//! +//! Consider that unlike `Vec`, [`NonEmpty::first`] and [`NonEmpty::last`] don't +//! return in `Option`, they always succeed. +//! +//! # Examples +//! +//! The simplest way to construct a [`NonEmpty`] is via the [`nonempty`] macro: +//! +//! ``` +//! use nonempty::{NonEmpty, nonempty}; +//! +//! let l: NonEmpty<u32> = nonempty![1, 2, 3]; +//! assert_eq!(l.head, 1); +//! ``` +//! +//! Unlike the familiar `vec!` macro, `nonempty!` requires at least one element: +//! +//! ``` +//! use nonempty::nonempty; +//! +//! let l = nonempty![1]; +//! +//! // Doesn't compile! +//! // let l = nonempty![]; +//! ``` +//! +//! Like `Vec`, you can also construct a [`NonEmpty`] the old fashioned way with +//! [`NonEmpty::new`] or its constructor: +//! +//! ``` +//! use nonempty::NonEmpty; +//! +//! let mut l = NonEmpty { head: 42, tail: vec![36, 58] }; +//! assert_eq!(l.head, 42); +//! +//! l.push(9001); +//! assert_eq!(l.last(), &9001); +//! ``` +//! +//! And if necessary, you're free to convert to and from `Vec`: +//! +//! ``` +//! use nonempty::{NonEmpty, nonempty}; +//! +//! let l: NonEmpty<u32> = nonempty![42, 36, 58, 9001]; +//! let v: Vec<u32> = l.into(); +//! assert_eq!(v, vec![42, 36, 58, 9001]); +//! +//! let u: Option<NonEmpty<u32>> = NonEmpty::from_vec(v); +//! assert_eq!(Some(nonempty![42, 36, 58, 9001]), u); +//! ``` +//! +//! # Caveats +//! +//! Since `NonEmpty` must have a least one element, it is not possible to +//! implement the `FromInterator` trait for it. We can't know, in general, if +//! any given `Iterator` actually contains something. +//! +//! # Features +//! +//! * `serialize`: `serde` support. +//! * `arbitrary`: `arbitrary` support. +#[cfg(feature = "arbitrary")] +use arbitrary::Arbitrary; +#[cfg(feature = "serialize")] +use serde::{ + ser::{SerializeSeq, Serializer}, + Deserialize, Serialize, +}; +use std::mem; +use std::{cmp::Ordering, num::NonZeroUsize}; +use std::{iter, vec}; + +pub mod nonzero; + +/// Like the `vec!` macro, but enforces at least one argument. A nice short-hand +/// for constructing [`NonEmpty`] values. +/// +/// ``` +/// use nonempty::{NonEmpty, nonempty}; +/// +/// let v = nonempty![1, 2, 3]; +/// assert_eq!(v, NonEmpty { head: 1, tail: vec![2, 3] }); +/// +/// let v = nonempty![1]; +/// assert_eq!(v, NonEmpty { head: 1, tail: Vec::new() }); +/// +/// // Accepts trailing commas +/// let v = nonempty![1,]; +/// assert_eq!(v, NonEmpty { head: 1, tail: Vec::new() }); +/// +/// // Doesn't compile! +/// // let v = nonempty![]; +/// ``` +#[macro_export] +macro_rules! nonempty { + ($h:expr, $( $x:expr ),* $(,)?) => {{ + let tail = vec![$($x),*]; + $crate::NonEmpty { head: $h, tail } + }}; + ($h:expr) => { + $crate::NonEmpty { + head: $h, + tail: Vec::new(), + } + }; +} + +/// Non-empty vector. +#[cfg_attr(feature = "serialize", derive(Deserialize))] +#[cfg_attr(feature = "arbitrary", derive(Arbitrary))] +#[cfg_attr(feature = "serialize", serde(try_from = "Vec<T>"))] +#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] +pub struct NonEmpty<T> { + pub head: T, + pub tail: Vec<T>, +} + +// Nb. `Serialize` is implemented manually, as serde's `into` container attribute +// requires a `T: Clone` bound which we'd like to avoid. +#[cfg(feature = "serialize")] +impl<T> Serialize for NonEmpty<T> +where + T: Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut seq = serializer.serialize_seq(Some(self.len()))?; + for e in self { + seq.serialize_element(e)?; + } + seq.end() + } +} + +pub struct Iter<'a, T> { + head: Option<&'a T>, + tail: &'a [T], +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + if let Some(value) = self.head.take() { + Some(value) + } else if let Some((first, rest)) = self.tail.split_first() { + self.tail = rest; + Some(first) + } else { + None + } + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option<Self::Item> { + if let Some((last, rest)) = self.tail.split_last() { + self.tail = rest; + Some(last) + } else if let Some(first_value) = self.head.take() { + Some(first_value) + } else { + None + } + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> { + fn len(&self) -> usize { + self.tail.len() + self.head.map_or(0, |_| 1) + } +} + +impl<'a, T> core::iter::FusedIterator for Iter<'a, T> {} + +impl<T> NonEmpty<T> { + /// Alias for [`NonEmpty::singleton`]. + pub const fn new(e: T) -> Self { + Self::singleton(e) + } + + /// Attempt to convert an iterator into a `NonEmpty` vector. + /// Returns `None` if the iterator was empty. + pub fn collect<I>(iter: I) -> Option<NonEmpty<T>> + where + I: IntoIterator<Item = T>, + { + let mut iter = iter.into_iter(); + let head = iter.next()?; + Some(Self { + head, + tail: iter.collect(), + }) + } + + /// Create a new non-empty list with an initial element. + pub const fn singleton(head: T) -> Self { + NonEmpty { + head, + tail: Vec::new(), + } + } + + /// Always returns false. + pub const fn is_empty(&self) -> bool { + false + } + + /// Get the first element. Never fails. + pub const fn first(&self) -> &T { + &self.head + } + + /// Get the mutable reference to the first element. Never fails. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::new(42); + /// let head = non_empty.first_mut(); + /// *head += 1; + /// assert_eq!(non_empty.first(), &43); + /// + /// let mut non_empty = NonEmpty::from((1, vec![4, 2, 3])); + /// let head = non_empty.first_mut(); + /// *head *= 42; + /// assert_eq!(non_empty.first(), &42); + /// ``` + pub fn first_mut(&mut self) -> &mut T { + &mut self.head + } + + /// Get the possibly-empty tail of the list. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.tail(), &[]); + /// + /// let non_empty = NonEmpty::from((1, vec![4, 2, 3])); + /// assert_eq!(non_empty.tail(), &[4, 2, 3]); + /// ``` + pub fn tail(&self) -> &[T] { + &self.tail + } + + /// Push an element to the end of the list. + pub fn push(&mut self, e: T) { + self.tail.push(e) + } + + /// Pop an element from the end of the list. + pub fn pop(&mut self) -> Option<T> { + self.tail.pop() + } + + /// Inserts an element at position index within the vector, shifting all elements after it to the right. + /// + /// # Panics + /// + /// Panics if index > len. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3])); + /// non_empty.insert(1, 4); + /// assert_eq!(non_empty, NonEmpty::from((1, vec![4, 2, 3]))); + /// non_empty.insert(4, 5); + /// assert_eq!(non_empty, NonEmpty::from((1, vec![4, 2, 3, 5]))); + /// non_empty.insert(0, 42); + /// assert_eq!(non_empty, NonEmpty::from((42, vec![1, 4, 2, 3, 5]))); + /// ``` + pub fn insert(&mut self, index: usize, element: T) { + let len = self.len(); + assert!(index <= len); + + if index == 0 { + let head = mem::replace(&mut self.head, element); + self.tail.insert(0, head); + } else { + self.tail.insert(index - 1, element); + } + } + + /// Get the length of the list. + pub fn len(&self) -> usize { + self.tail.len() + 1 + } + + /// Gets the length of the list as a NonZeroUsize. + pub fn len_nonzero(&self) -> NonZeroUsize { + unsafe { NonZeroUsize::new_unchecked(self.tail.len().saturating_add(1)) } + } + + /// Get the capacity of the list. + pub fn capacity(&self) -> usize { + self.tail.capacity() + 1 + } + + /// Get the last element. Never fails. + pub fn last(&self) -> &T { + match self.tail.last() { + None => &self.head, + Some(e) => e, + } + } + + /// Get the last element mutably. + pub fn last_mut(&mut self) -> &mut T { + match self.tail.last_mut() { + None => &mut self.head, + Some(e) => e, + } + } + + /// Check whether an element is contained in the list. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::from((42, vec![36, 58])); + /// + /// assert!(l.contains(&42)); + /// assert!(!l.contains(&101)); + /// ``` + pub fn contains(&self, x: &T) -> bool + where + T: PartialEq, + { + self.iter().any(|e| e == x) + } + + /// Get an element by index. + pub fn get(&self, index: usize) -> Option<&T> { + if index == 0 { + Some(&self.head) + } else { + self.tail.get(index - 1) + } + } + + /// Get an element by index, mutably. + pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { + if index == 0 { + Some(&mut self.head) + } else { + self.tail.get_mut(index - 1) + } + } + + /// Truncate the list to a certain size. Must be greater than `0`. + pub fn truncate(&mut self, len: usize) { + assert!(len >= 1); + self.tail.truncate(len - 1); + } + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::from((42, vec![36, 58])); + /// + /// let mut l_iter = l.iter(); + /// + /// assert_eq!(l_iter.len(), 3); + /// assert_eq!(l_iter.next(), Some(&42)); + /// assert_eq!(l_iter.next(), Some(&36)); + /// assert_eq!(l_iter.next(), Some(&58)); + /// assert_eq!(l_iter.next(), None); + /// ``` + pub fn iter(&self) -> Iter<T> { + Iter { + head: Some(&self.head), + tail: &self.tail, + } + } + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::new(42); + /// l.push(36); + /// l.push(58); + /// + /// for i in l.iter_mut() { + /// *i *= 10; + /// } + /// + /// let mut l_iter = l.iter(); + /// + /// assert_eq!(l_iter.next(), Some(&420)); + /// assert_eq!(l_iter.next(), Some(&360)); + /// assert_eq!(l_iter.next(), Some(&580)); + /// assert_eq!(l_iter.next(), None); + /// ``` + pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> + '_ { + iter::once(&mut self.head).chain(self.tail.iter_mut()) + } + + /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmpty` before + /// proceeding with a computation. Using `from_slice` will give us a proof + /// that we have a `NonEmpty` in the `Some` branch, otherwise it allows + /// the caller to handle the `None` case. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty_vec = NonEmpty::from_slice(&[1, 2, 3, 4, 5]); + /// assert_eq!(non_empty_vec, Some(NonEmpty::from((1, vec![2, 3, 4, 5])))); + /// + /// let empty_vec: Option<NonEmpty<&u32>> = NonEmpty::from_slice(&[]); + /// assert!(empty_vec.is_none()); + /// ``` + pub fn from_slice(slice: &[T]) -> Option<NonEmpty<T>> + where + T: Clone, + { + slice.split_first().map(|(h, t)| NonEmpty { + head: h.clone(), + tail: t.into(), + }) + } + + /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmpty` before + /// proceeding with a computation. Using `from_vec` will give us a proof + /// that we have a `NonEmpty` in the `Some` branch, otherwise it allows + /// the caller to handle the `None` case. + /// + /// This version will consume the `Vec` you pass in. If you would rather pass the data as a + /// slice then use `NonEmpty::from_slice`. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty_vec = NonEmpty::from_vec(vec![1, 2, 3, 4, 5]); + /// assert_eq!(non_empty_vec, Some(NonEmpty::from((1, vec![2, 3, 4, 5])))); + /// + /// let empty_vec: Option<NonEmpty<&u32>> = NonEmpty::from_vec(vec![]); + /// assert!(empty_vec.is_none()); + /// ``` + pub fn from_vec(mut vec: Vec<T>) -> Option<NonEmpty<T>> { + if vec.is_empty() { + None + } else { + let head = vec.remove(0); + Some(NonEmpty { head, tail: vec }) + } + } + + /// Deconstruct a `NonEmpty` into its head and tail. + /// This operation never fails since we are guranteed + /// to have a head element. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// // Guaranteed to have the head and we also get the tail. + /// assert_eq!(non_empty.split_first(), (&1, &[2, 3, 4, 5][..])); + /// + /// let non_empty = NonEmpty::new(1); + /// + /// // Guaranteed to have the head element. + /// assert_eq!(non_empty.split_first(), (&1, &[][..])); + /// ``` + pub fn split_first(&self) -> (&T, &[T]) { + (&self.head, &self.tail) + } + + /// Deconstruct a `NonEmpty` into its first, last, and + /// middle elements, in that order. + /// + /// If there is only one element then first == last. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// // Guaranteed to have the last element and the elements + /// // preceding it. + /// assert_eq!(non_empty.split(), (&1, &[2, 3, 4][..], &5)); + /// + /// let non_empty = NonEmpty::new(1); + /// + /// // Guaranteed to have the last element. + /// assert_eq!(non_empty.split(), (&1, &[][..], &1)); + /// ``` + pub fn split(&self) -> (&T, &[T], &T) { + match self.tail.split_last() { + None => (&self.head, &[], &self.head), + Some((last, middle)) => (&self.head, middle, last), + } + } + + /// Append a `Vec` to the tail of the `NonEmpty`. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::new(1); + /// let mut vec = vec![2, 3, 4, 5]; + /// non_empty.append(&mut vec); + /// + /// let mut expected = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(non_empty, expected); + /// ``` + pub fn append(&mut self, other: &mut Vec<T>) { + self.tail.append(other) + } + + /// A structure preserving `map`. This is useful for when + /// we wish to keep the `NonEmpty` structure guaranteeing + /// that there is at least one element. Otherwise, we can + /// use `nonempty.iter().map(f)`. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// let squares = non_empty.map(|i| i * i); + /// + /// let expected = NonEmpty::from((1, vec![4, 9, 16, 25])); + /// + /// assert_eq!(squares, expected); + /// ``` + pub fn map<U, F>(self, mut f: F) -> NonEmpty<U> + where + F: FnMut(T) -> U, + { + NonEmpty { + head: f(self.head), + tail: self.tail.into_iter().map(f).collect(), + } + } + + /// A structure preserving, fallible mapping function. + pub fn try_map<E, U, F>(self, mut f: F) -> Result<NonEmpty<U>, E> + where + F: FnMut(T) -> Result<U, E>, + { + Ok(NonEmpty { + head: f(self.head)?, + tail: self.tail.into_iter().map(f).collect::<Result<_, _>>()?, + }) + } + + /// When we have a function that goes from some `T` to a `NonEmpty<U>`, + /// we may want to apply it to a `NonEmpty<T>` but keep the structure flat. + /// This is where `flat_map` shines. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// let windows = non_empty.flat_map(|i| { + /// let mut next = NonEmpty::new(i + 5); + /// next.push(i + 6); + /// next + /// }); + /// + /// let expected = NonEmpty::from((6, vec![7, 7, 8, 8, 9, 9, 10, 10, 11])); + /// + /// assert_eq!(windows, expected); + /// ``` + pub fn flat_map<U, F>(self, mut f: F) -> NonEmpty<U> + where + F: FnMut(T) -> NonEmpty<U>, + { + let mut heads = f(self.head); + let mut tails = self + .tail + .into_iter() + .flat_map(|t| f(t).into_iter()) + .collect(); + heads.append(&mut tails); + heads + } + + /// Flatten nested `NonEmpty`s into a single one. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from(( + /// NonEmpty::from((1, vec![2, 3])), + /// vec![NonEmpty::from((4, vec![5]))], + /// )); + /// + /// let expected = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(NonEmpty::flatten(non_empty), expected); + /// ``` + pub fn flatten(full: NonEmpty<NonEmpty<T>>) -> Self { + full.flat_map(|n| n) + } + + /// Binary searches this sorted non-empty vector for a given element. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. + /// If there are multiple matches, then any one of the matches could be returned. + /// + /// If the value is not found then Result::Err is returned, containing the index where a + /// matching element could be inserted while maintaining sorted order. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// assert_eq!(non_empty.binary_search(&0), Ok(0)); + /// assert_eq!(non_empty.binary_search(&13), Ok(9)); + /// assert_eq!(non_empty.binary_search(&4), Err(7)); + /// assert_eq!(non_empty.binary_search(&100), Err(13)); + /// let r = non_empty.binary_search(&1); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + /// + /// If you want to insert an item to a sorted non-empty vector, while maintaining sort order: + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// let num = 42; + /// let idx = non_empty.binary_search(&num).unwrap_or_else(|x| x); + /// non_empty.insert(idx, num); + /// assert_eq!(non_empty, NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]))); + /// ``` + pub fn binary_search(&self, x: &T) -> Result<usize, usize> + where + T: Ord, + { + self.binary_search_by(|p| p.cmp(x)) + } + + /// Binary searches this sorted non-empty with a comparator function. + /// + /// The comparator function should implement an order consistent with the sort order of the underlying slice, + /// returning an order code that indicates whether its argument is Less, Equal or Greater the desired target. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. + /// If there are multiple matches, then any one of the matches could be returned. + /// If the value is not found then Result::Err is returned, containing the index where a matching element could be + /// inserted while maintaining sorted order. + /// + /// # Examples + /// + /// Looks up a series of four elements. The first is found, with a uniquely determined + /// position; the second and third are not found; the fourth could match any position in [1,4]. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// let seek = 0; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Ok(0)); + /// let seek = 13; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Ok(9)); + /// let seek = 4; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Err(7)); + /// let seek = 100; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Err(13)); + /// let seek = 1; + /// let r = non_empty.binary_search_by(|probe| probe.cmp(&seek)); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a T) -> Ordering, + { + match f(&self.head) { + Ordering::Equal => Ok(0), + Ordering::Greater => Err(0), + Ordering::Less => self + .tail + .binary_search_by(f) + .map(|index| index + 1) + .map_err(|index| index + 1), + } + } + + /// Binary searches this sorted non-empty vector with a key extraction function. + /// + /// Assumes that the vector is sorted by the key. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, + /// then any one of the matches could be returned. If the value is not found then Result::Err is returned, + /// containing the index where a matching element could be inserted while maintaining sorted order. + /// + /// # Examples + /// + /// Looks up a series of four elements in a non-empty vector of pairs sorted by their second elements. + /// The first is found, with a uniquely determined position; the second and third are not found; + /// the fourth could match any position in [1, 4]. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from(( + /// (0, 0), + /// vec![(2, 1), (4, 1), (5, 1), (3, 1), + /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13), + /// (1, 21), (2, 34), (4, 55)] + /// )); + /// + /// assert_eq!(non_empty.binary_search_by_key(&0, |&(a,b)| b), Ok(0)); + /// assert_eq!(non_empty.binary_search_by_key(&13, |&(a,b)| b), Ok(9)); + /// assert_eq!(non_empty.binary_search_by_key(&4, |&(a,b)| b), Err(7)); + /// assert_eq!(non_empty.binary_search_by_key(&100, |&(a,b)| b), Err(13)); + /// let r = non_empty.binary_search_by_key(&1, |&(a,b)| b); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize> + where + B: Ord, + F: FnMut(&'a T) -> B, + { + self.binary_search_by(|k| f(k).cmp(b)) + } + + /// Returns the maximum element in the non-empty vector. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.maximum(), &42); + /// + /// let non_empty = NonEmpty::from((1, vec![-34, 42, 76, 4, 5])); + /// assert_eq!(non_empty.maximum(), &76); + /// ``` + pub fn maximum(&self) -> &T + where + T: Ord, + { + self.maximum_by(|i, j| i.cmp(j)) + } + + /// Returns the minimum element in the non-empty vector. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.minimum(), &42); + /// + /// let non_empty = NonEmpty::from((1, vec![-34, 42, 76, 4, 5])); + /// assert_eq!(non_empty.minimum(), &-34); + /// ``` + pub fn minimum(&self) -> &T + where + T: Ord, + { + self.minimum_by(|i, j| i.cmp(j)) + } + + /// Returns the element that gives the maximum value with respect to the specified comparison function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.maximum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.maximum_by(|(k, _), (l, _)| k.cmp(l)), &(4, 42)); + /// ``` + pub fn maximum_by<'a, F>(&'a self, mut compare: F) -> &T + where + F: FnMut(&'a T, &'a T) -> Ordering, + { + let mut max = &self.head; + for i in self.tail.iter() { + max = match compare(max, i) { + Ordering::Equal => max, + Ordering::Less => i, + Ordering::Greater => max, + }; + } + max + } + + /// Returns the element that gives the minimum value with respect to the specified comparison function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.minimum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.minimum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 76)); + /// ``` + pub fn minimum_by<'a, F>(&'a self, mut compare: F) -> &T + where + F: FnMut(&'a T, &'a T) -> Ordering, + { + self.maximum_by(|a, b| compare(a, b).reverse()) + } + + /// Returns the element that gives the maximum value with respect to the specified function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| k), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| k), &(4, 42)); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| -k), &(0, 76)); + /// ``` + pub fn maximum_by_key<'a, U, F>(&'a self, mut f: F) -> &T + where + U: Ord, + F: FnMut(&'a T) -> U, + { + self.maximum_by(|i, j| f(i).cmp(&f(j))) + } + + /// Returns the element that gives the minimum value with respect to the specified function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| k), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| k), &(0, 76)); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| -k), &(4, 42)); + /// ``` + pub fn minimum_by_key<'a, U, F>(&'a self, mut f: F) -> &T + where + U: Ord, + F: FnMut(&'a T) -> U, + { + self.minimum_by(|i, j| f(i).cmp(&f(j))) + } +} + +impl<T: Default> Default for NonEmpty<T> { + fn default() -> Self { + Self::new(T::default()) + } +} + +impl<T> From<NonEmpty<T>> for Vec<T> { + /// Turns a non-empty list into a Vec. + fn from(nonempty: NonEmpty<T>) -> Vec<T> { + iter::once(nonempty.head).chain(nonempty.tail).collect() + } +} + +impl<T> From<NonEmpty<T>> for (T, Vec<T>) { + /// Turns a non-empty list into a Vec. + fn from(nonempty: NonEmpty<T>) -> (T, Vec<T>) { + (nonempty.head, nonempty.tail) + } +} + +impl<T> From<(T, Vec<T>)> for NonEmpty<T> { + /// Turns a pair of an element and a Vec into + /// a NonEmpty. + fn from((head, tail): (T, Vec<T>)) -> Self { + NonEmpty { head, tail } + } +} + +impl<T> IntoIterator for NonEmpty<T> { + type Item = T; + type IntoIter = iter::Chain<iter::Once<T>, vec::IntoIter<Self::Item>>; + + fn into_iter(self) -> Self::IntoIter { + iter::once(self.head).chain(self.tail) + } +} + +impl<'a, T> IntoIterator for &'a NonEmpty<T> { + type Item = &'a T; + type IntoIter = iter::Chain<iter::Once<&'a T>, std::slice::Iter<'a, T>>; + + fn into_iter(self) -> Self::IntoIter { + iter::once(&self.head).chain(self.tail.iter()) + } +} + +impl<T> std::ops::Index<usize> for NonEmpty<T> { + type Output = T; + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(non_empty[0], 1); + /// assert_eq!(non_empty[1], 2); + /// assert_eq!(non_empty[3], 4); + /// ``` + fn index(&self, index: usize) -> &T { + if index > 0 { + &self.tail[index - 1] + } else { + &self.head + } + } +} + +impl<T> std::ops::IndexMut<usize> for NonEmpty<T> { + fn index_mut(&mut self, index: usize) -> &mut T { + if index > 0 { + &mut self.tail[index - 1] + } else { + &mut self.head + } + } +} + +impl<A> Extend<A> for NonEmpty<A> { + fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) { + self.tail.extend(iter) + } +} + +#[cfg(feature = "serialize")] +pub mod serialize { + use std::{convert::TryFrom, fmt}; + + use super::NonEmpty; + + #[derive(Debug)] + pub enum Error { + Empty, + } + + impl fmt::Display for Error { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::Empty => f.write_str( + "the vector provided was empty, NonEmpty needs at least one element", + ), + } + } + } + + impl<T> TryFrom<Vec<T>> for NonEmpty<T> { + type Error = Error; + + fn try_from(vec: Vec<T>) -> Result<Self, Self::Error> { + NonEmpty::from_vec(vec).ok_or(Error::Empty) + } + } +} + +#[cfg(test)] +mod tests { + use crate::NonEmpty; + + #[test] + fn test_from_conversion() { + let result = NonEmpty::from((1, vec![2, 3, 4, 5])); + let expected = NonEmpty { + head: 1, + tail: vec![2, 3, 4, 5], + }; + assert_eq!(result, expected); + } + + #[test] + fn test_into_iter() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + for (i, n) in nonempty.into_iter().enumerate() { + assert_eq!(i as i32, n); + } + } + + #[test] + fn test_iter_syntax() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + for n in &nonempty { + let _ = *n; // Prove that we're dealing with references. + } + for _ in nonempty {} + } + + #[test] + fn test_iter_both_directions() { + let mut nonempty = NonEmpty::from((0, vec![1, 2, 3])); + assert_eq!(nonempty.iter().cloned().collect::<Vec<_>>(), [0, 1, 2, 3]); + assert_eq!( + nonempty.iter().rev().cloned().collect::<Vec<_>>(), + [3, 2, 1, 0] + ); + assert_eq!( + nonempty.iter_mut().rev().collect::<Vec<_>>(), + [&mut 3, &mut 2, &mut 1, &mut 0] + ); + } + + #[test] + fn test_iter_both_directions_at_once() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + let mut i = nonempty.iter(); + assert_eq!(i.next(), Some(&0)); + assert_eq!(i.next_back(), Some(&3)); + assert_eq!(i.next(), Some(&1)); + assert_eq!(i.next_back(), Some(&2)); + assert_eq!(i.next(), None); + assert_eq!(i.next_back(), None); + } + + #[test] + fn test_mutate_head() { + let mut non_empty = NonEmpty::new(42); + non_empty.head += 1; + assert_eq!(non_empty.head, 43); + + let mut non_empty = NonEmpty::from((1, vec![4, 2, 3])); + non_empty.head *= 42; + assert_eq!(non_empty.head, 42); + } + + #[test] + fn test_to_nonempty() { + use std::iter::{empty, once}; + + assert_eq!(NonEmpty::<()>::collect(empty()), None); + assert_eq!(NonEmpty::<()>::collect(once(())), Some(NonEmpty::new(()))); + assert_eq!( + NonEmpty::<u8>::collect(once(1).chain(once(2))), + Some(nonempty!(1, 2)) + ); + } + + #[test] + fn test_try_map() { + assert_eq!( + nonempty!(1, 2, 3, 4).try_map(Ok::<_, String>), + Ok(nonempty!(1, 2, 3, 4)) + ); + assert_eq!( + nonempty!(1, 2, 3, 4).try_map(|i| if i % 2 == 0 { Ok(i) } else { Err("not even") }), + Err("not even") + ); + } + + #[test] + fn test_nontrivial_minimum_by_key() { + #[derive(Debug, Clone, Copy, PartialEq, Eq)] + struct Position { + x: i32, + y: i32, + } + impl Position { + pub fn distance_squared(&self, other: Position) -> u32 { + let dx = self.x - other.x; + let dy = self.y - other.y; + (dx * dx + dy * dy) as u32 + } + } + let positions = nonempty![ + Position { x: 1, y: 1 }, + Position { x: 0, y: 0 }, + Position { x: 3, y: 4 } + ]; + let target = Position { x: 1, y: 2 }; + let closest = positions.minimum_by_key(|position| position.distance_squared(target)); + assert_eq!(closest, &Position { x: 1, y: 1 }); + } + + #[cfg(feature = "serialize")] + mod serialize { + use crate::NonEmpty; + use serde::{Deserialize, Serialize}; + + #[derive(Debug, Deserialize, Eq, PartialEq, Serialize)] + pub struct SimpleSerializable(pub i32); + + #[test] + fn test_simple_round_trip() -> Result<(), Box<dyn std::error::Error>> { + // Given + let mut non_empty = NonEmpty::new(SimpleSerializable(42)); + non_empty.push(SimpleSerializable(777)); + + // When + let res = serde_json::from_str::<'_, NonEmpty<SimpleSerializable>>( + &serde_json::to_string(&non_empty)?, + )?; + + // Then + assert_eq!(res, non_empty); + + Ok(()) + } + + #[test] + fn test_serialization() -> Result<(), Box<dyn std::error::Error>> { + let ne = nonempty![1, 2, 3, 4, 5]; + let ve = vec![1, 2, 3, 4, 5]; + + assert_eq!(serde_json::to_string(&ne)?, serde_json::to_string(&ve)?); + + Ok(()) + } + } + + #[cfg(feature = "arbitrary")] + mod arbitrary { + use crate::NonEmpty; + use arbitrary::{Arbitrary, Unstructured}; + + #[test] + fn test_arbitrary_empty_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4]); + let ne = NonEmpty::<i32>::arbitrary(&mut u)?; + assert!(!ne.is_empty()); + assert_eq!( + ne, + NonEmpty { + head: 67305985, + tail: vec![], + } + ); + Ok(()) + } + + #[test] + fn test_arbitrary_with_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8]); + let ne = NonEmpty::<i32>::arbitrary(&mut u)?; + assert!(!ne.is_empty()); + assert_eq!( + ne, + NonEmpty { + head: 67305985, + tail: vec![526086], + } + ); + Ok(()) + } + } +} |