Struct nonempty_collections::vector::NEVec

pub struct NEVec<T> {
    pub head: T,
    pub tail: Vec<T>,
}

A non-empty, growable Vector.

The first element can always be accessed in constant time. Similarly, certain functions like NEVec::first and NEVec::last always succeed:

use nonempty_collections::nev;

let s = nev!["Fëanor", "Fingolfin", "Finarfin"];
assert_eq!("Fëanor", s.head);      // There is always a first element.
assert_eq!(&"Finarfin", s.last()); // There is always a last element.

Fields

head: T

The element of the non-empty Vector. Always exists.

tail: Vec<T>

The remaining elements of the non-empty Vector, perhaps empty.

Implementations

impl<T> NEVec<T>

pub const fn new(head: T) -> Self

Create a new non-empty list with an initial element.

pub fn with_capacity(capacity: usize, head: T) -> Self

Creates a new NEVec with a single element and specified capacity.

pub const fn first(&self) -> &T

Get the first element. Never fails.

pub fn first_mut(&mut self) -> &mut T

Get the mutable reference to the first element. Never fails.

Examples

use nonempty_collections::nev;

let mut v = nev![42];
let head = v.first_mut();
*head += 1;
assert_eq!(v.first(), &43);

let mut v = nev![1, 4, 2, 3];
let head = v.first_mut();
*head *= 42;
assert_eq!(v.first(), &42);

pub fn tail(&self) -> &[T]

Get the possibly-empty tail of the list.

use nonempty_collections::nev;

let v = nev![42];
assert_eq!(v.tail(), &[]);

let v = nev![1, 4, 2, 3];
assert_eq!(v.tail(), &[4, 2, 3]);

pub fn push(&mut self, e: T)

Push an element to the end of the list.

pub fn pop(&mut self) -> Option<T>

Pop an element from the end of the list. Will never pop the head value.

use nonempty_collections::nev;

let mut v = nev![1, 2];
assert_eq!(Some(2), v.pop());
assert_eq!(None, v.pop());

pub fn insert(&mut self, index: usize, element: T)

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_collections::nev;

let mut v = nev![1, 2, 3];
v.insert(1, 4);
assert_eq!(v, nev![1, 4, 2, 3]);
v.insert(4, 5);
assert_eq!(v, nev![1, 4, 2, 3, 5]);
v.insert(0, 42);
assert_eq!(v, nev![42, 1, 4, 2, 3, 5]);

pub fn len(&self) -> NonZeroUsize

Get the length of the list.

pub const fn is_empty(&self) -> bool

👎Deprecated since 0.1.0: A NEVec is never empty.

A NEVec is never empty.

pub fn capacity(&self) -> usize

Get the capacity of the list.

pub fn last(&self) -> &T

Get the last element. Never fails.

pub fn last_mut(&mut self) -> &mut T

Get the last element mutably.

pub fn contains(&self, x: &T) -> bool

where T: PartialEq,

Check whether an element is contained in the list.

use nonempty_collections::nev;

let mut l = nev![42, 36, 58];

assert!(l.contains(&42));
assert!(!l.contains(&101));

pub fn get(&self, index: usize) -> Option<&T>

Get an element by index.

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Get an element by index, mutably.

pub fn truncate(&mut self, len: usize)

Truncate the list to a certain size. Must be greater than 0.

pub fn iter(&self) -> Iter<'_, T>

use nonempty_collections::*;

let mut l = nev![42, 36, 58];

let mut l_iter = l.iter();

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_mut(&mut self) -> IterMut<'_, T>

use nonempty_collections::*;

let mut l = nev![42, 36, 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);

Panics

If you manually advance this iterator and then call NonEmptyIterator::first, then you’re in for a surprise.

pub fn from_slice(slice: &[T]) -> Option<NEVec<T>>

where T: Clone,

Often we have a Vec (or slice &[T]) but want to ensure that it is NEVec before proceeding with a computation. Using from_slice will give us a proof that we have a NEVec in the Some branch, otherwise it allows the caller to handle the None case.

Example Use

use nonempty_collections::{nev, NEVec};

let v_vec = NEVec::from_slice(&[1, 2, 3, 4, 5]);
assert_eq!(v_vec, Some(nev![1, 2, 3, 4, 5]));

let empty_vec: Option<NEVec<&u32>> = NEVec::from_slice(&[]);
assert!(empty_vec.is_none());

pub fn from_vec(vec: Vec<T>) -> Option<NEVec<T>>

Often we have a Vec (or slice &[T]) but want to ensure that it is NEVec before proceeding with a computation. Using from_vec will give us a proof that we have a NEVec 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 NEVec::from_slice.

Example Use

use nonempty_collections::{nev, NEVec};

let v_vec = NEVec::from_vec(vec![1, 2, 3, 4, 5]);
assert_eq!(v_vec, Some(nev![1, 2, 3, 4, 5]));

let empty_vec: Option<NEVec<&u32>> = NEVec::from_vec(vec![]);
assert!(empty_vec.is_none());

pub fn split_first(&self) -> (&T, &[T])

Deconstruct a NEVec into its head and tail. This operation never fails since we are guranteed to have a head element.

Example Use

use nonempty_collections::nev;

let mut v = nev![1, 2, 3, 4, 5];

// Guaranteed to have the head and we also get the tail.
assert_eq!(v.split_first(), (&1, &[2, 3, 4, 5][..]));

let v = nev![1];

// Guaranteed to have the head element.
assert_eq!(v.split_first(), (&1, &[][..]));

pub fn split(&self) -> (&T, &[T], &T)

Deconstruct a NEVec into its first, last, and middle elements, in that order.

If there is only one element then first == last.

Example Use

use nonempty_collections::nev;

let mut v = nev![1, 2, 3, 4, 5];

// Guaranteed to have the last element and the elements
// preceding it.
assert_eq!(v.split(), (&1, &[2, 3, 4][..], &5));

let v = nev![1];

// Guaranteed to have the last element.
assert_eq!(v.split(), (&1, &[][..], &1));

pub fn append(&mut self, other: &mut Vec<T>)

Append a Vec to the tail of the NEVec.

Example Use

use nonempty_collections::nev;

let mut v = nev![1];
let mut vec = vec![2, 3, 4, 5];
v.append(&mut vec);

let mut expected = nev![1, 2, 3, 4, 5];
assert_eq!(v, expected);

pub fn binary_search(&self, x: &T) -> Result<usize, usize>

where T: Ord,

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_collections::nev;

let v = nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
assert_eq!(v.binary_search(&0),   Ok(0));
assert_eq!(v.binary_search(&13),  Ok(9));
assert_eq!(v.binary_search(&4),   Err(7));
assert_eq!(v.binary_search(&100), Err(13));
let r = v.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_collections::nev;

let mut v = nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
let num = 42;
let idx = v.binary_search(&num).unwrap_or_else(|x| x);
v.insert(idx, num);
assert_eq!(v, nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>

where F: FnMut(&'a T) -> Ordering,

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 from 1 to 4.

use nonempty_collections::nev;

let v = nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
let seek = 0;
assert_eq!(v.binary_search_by(|probe| probe.cmp(&seek)), Ok(0));
let seek = 13;
assert_eq!(v.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
let seek = 4;
assert_eq!(v.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
let seek = 100;
assert_eq!(v.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
let seek = 1;
let r = v.binary_search_by(|probe| probe.cmp(&seek));
assert!(match r { Ok(1..=4) => true, _ => false, });

pub fn binary_search_by_key<'a, B, F>( &'a self, b: &B, f: F ) -> Result<usize, usize>

where B: Ord, F: FnMut(&'a T) -> B,

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_collections::nev;

let v = nev![
    (0, 0), (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!(v.binary_search_by_key(&0, |&(a,b)| b),  Ok(0));
assert_eq!(v.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
assert_eq!(v.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
assert_eq!(v.binary_search_by_key(&100, |&(a,b)| b), Err(13));
let r = v.binary_search_by_key(&1, |&(a,b)| b);
assert!(match r { Ok(1..=4) => true, _ => false, });

pub fn sort(&mut self)

where T: Ord,

Sorts the NEVec in place.

See also slice::sort.

use nonempty_collections::nev;

let mut n = nev![5,4,3,2,1];
n.sort();
assert_eq!(nev![1,2,3,4,5], n);

// Naturally, sorting a sorted result should be the same.
n.sort();
assert_eq!(nev![1,2,3,4,5], n);

pub fn as_nonempty_slice(&self) -> NESlice<'_, T>

Yields a NESlice.

pub fn dedup_by_key<F, K>(&mut self, key: F)

where F: FnMut(&mut T) -> K, K: PartialEq,

Removes all but the first of consecutive elements in the vector that resolve to the same key.

If the vector is sorted, this removes all duplicates.

Examples

use nonempty_collections::nev;
let mut v = nev![10, 20, 21, 30, 20];

v.dedup_by_key(|i| *i / 10);

assert_eq!(nev![10, 20, 30, 20], v);

pub fn dedup_by<F>(&mut self, same_bucket: F)

where F: FnMut(&mut T, &mut T) -> bool,

Removes all but the first of consecutive elements in the vector satisfying a given equality relation.

The same_bucket function is passed references to two elements from the vector and must determine if the elements compare equal. The elements are passed in opposite order from their order in the slice, so if same_bucket(a, b) returns true, a is removed.

If the vector is sorted, this removes all duplicates.

Examples

use nonempty_collections::nev;
let mut v = nev!["foo", "Foo", "foo", "bar", "Bar", "baz", "bar"];

v.dedup_by(|a, b| a.eq_ignore_ascii_case(b));

assert_eq!(nev!["foo", "bar", "baz", "bar"], v);

pub fn nonempty_chunks(&self, chunk_size: NonZeroUsize) -> NEChunks<'_, T>

Returns a non-empty iterator over chunk_size elements of the NEVec at a time, starting at the beginning of the NEVec.

use nonempty_collections::*;
use std::num::NonZeroUsize;

let v = nev![1,2,3,4,5,6];
let n = NonZeroUsize::new(2).unwrap();
let r = v.nonempty_chunks(n).collect::<NEVec<_>>();

let a = nev![1,2];
let b = nev![3,4];
let c = nev![5,6];

assert_eq!(r, nev![a.as_nonempty_slice(), b.as_nonempty_slice(), c.as_nonempty_slice()]);

pub fn partition_point<P>(&self, pred: P) -> usize

where P: FnMut(&T) -> bool,

Returns the index of the partition point according to the given predicate (the index of the first element of the second partition).

The vector is assumed to be partitioned according to the given predicate. This means that all elements for which the predicate returns true are at the start of the vector and all elements for which the predicate returns false are at the end. For example, [7, 15, 3, 5, 4, 12, 6] is partitioned under the predicate x % 2 != 0 (all odd numbers are at the start, all even at the end).

If this vector is not partitioned, the returned result is unspecified and meaningless, as this method performs a kind of binary search.

See also NEVec::binary_search, NEVec::binary_search_by, and NEVec::binary_search_by_key.

Examples

let v = nev![1, 2, 3, 3, 5, 6, 7];
let i = v.partition_point(|&x| x < 5);

assert_eq!(i, 4);

If all elements of the non-empty vector match the predicate, then the length of the vector will be returned:

let a = nev![2, 4, 8];
assert_eq!(a.partition_point(|&x| x < 100), a.len().get());

If you want to insert an item to a sorted vector, while maintaining sort order:

let mut s = nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
let num = 42;
let idx = s.partition_point(|&x| x < num);
s.insert(idx, num);
assert_eq!(s, nev![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

impl<T: PartialEq> NEVec<T>

pub fn dedup(&mut self)

Removes consecutive repeated elements in the vector according to the PartialEq trait implementation.

If the vector is sorted, this removes all duplicates.

Examples

use nonempty_collections::nev;
let mut v = nev![1, 1, 1, 2, 3, 2, 2, 1];
v.dedup();
assert_eq!(nev![1, 2, 3, 2, 1], v);

Trait Implementations

impl<T: Clone> Clone for NEVec<T>

fn clone(&self) -> NEVec<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for NEVec<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, T> Deserialize<'de> for NEVec<T>

where T: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T> From<(T, Vec<T>)> for NEVec<T>

fn from((head, tail): (T, Vec<T>)) -> Self

Turns a pair of an element and a Vec into a NEVec.

impl<T> From<NEVec<T>> for (T, Vec<T>)

fn from(nonempty: NEVec<T>) -> (T, Vec<T>)

Turns a non-empty list into a Vec.

impl<T> From<NEVec<T>> for Vec<T>

fn from(nonempty: NEVec<T>) -> Vec<T>

Turns a non-empty list into a Vec.

impl<T> FromNonEmptyIterator<T> for NEVec<T>

use nonempty_collections::*;

let v0 = nev![1, 2, 3];
let v1: NEVec<_> = v0.iter().cloned().collect();
assert_eq!(v0, v1);

fn from_nonempty_iter<I>(iter: I) -> Self

where I: IntoNonEmptyIterator<Item = T>,

Creates a value from a NonEmptyIterator.

impl<T: Hash> Hash for NEVec<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for NEVec<T>

fn index(&self, index: usize) -> &T

use nonempty_collections::nev;

let v = nev![1, 2, 3, 4, 5];

assert_eq!(v[0], 1);
assert_eq!(v[1], 2);
assert_eq!(v[3], 4);

type Output = T

The returned type after indexing.

impl<T> IndexMut<usize> for NEVec<T>

fn index_mut(&mut self, index: usize) -> &mut T

Performs the mutable indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a NEVec<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Chain<Once<&'a T>, Iter<'a, T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for NEVec<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = Chain<Once<T>, IntoIter<<NEVec<T> as IntoIterator>::Item>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoNonEmptyIterator for NEVec<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = Chain<Once<T>, IntoIter<<NEVec<T> as IntoNonEmptyIterator>::Item>>

Which kind of NonEmptyIterator are we turning this into?

fn into_nonempty_iter(self) -> Self::IntoIter

Creates a NonEmptyIterator from a value.

impl<T: Ord> Ord for NEVec<T>

fn cmp(&self, other: &NEVec<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq for NEVec<T>

fn eq(&self, other: &NEVec<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialOrd> PartialOrd for NEVec<T>

fn partial_cmp(&self, other: &NEVec<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Serialize for NEVec<T>

where T: Clone + Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<T> TryFrom<Vec<T>> for NEVec<T>

type Error = Error

The type returned in the event of a conversion error.

fn try_from(vec: Vec<T>) -> Result<Self, Self::Error>

Performs the conversion.

impl<T: Eq> Eq for NEVec<T>

impl<T> StructuralPartialEq for NEVec<T>