Struct dlv_list::VecList

pub struct VecList<T> { /* private fields */ }

A semi-doubly linked list implemented with a vector.

This provides many of the benefits of an actual linked list with a few tradeoffs. First, due to the use of an underlying vector, an individual insert operation may be O(n) due to allocating more space for the vector. However, it is amortized O(1) and it avoids the frequent allocations that traditional linked lists suffer from.

Another tradeoff is that extending a traditional linked list with another list is O(1) but a vector based implementation is O(n). Splicing has a similar disadvantage.

Lastly, the vector based implementation is likely to have better cache locality in general.

Implementations

impl<T> VecList<T>

pub fn back(&self) -> Option<&T>

Returns an immutable reference to the value at the back of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.back(), None);

list.push_back(0);
list.push_back(5);
assert_eq!(list.back(), Some(&5));

pub fn back_index(&self) -> Option<Index<T>>

Returns the index of the value at the back of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.back_index(), None);

list.push_back(0);
let index = list.push_back(5);
assert_eq!(list.back_index(), Some(index));

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

Returns a mutable reference to the value at the back of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.back_mut(), None);

list.push_back(0);
list.push_back(5);

let mut back = list.back_mut().unwrap();
assert_eq!(back, &mut 5);
*back *= 2;

assert_eq!(list.back(), Some(&10));

pub fn capacity(&self) -> usize

Returns the capacity of the list.

Examples

use dlv_list::VecList;

let list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

let list: VecList<u32> = VecList::with_capacity(10);
assert_eq!(list.capacity(), 10);

pub fn clear(&mut self)

Removes all values from the list and invalidates all existing indices.

Complexity: O(n)

Examples

use dlv_list::VecList;

let mut list = VecList::new();

list.push_back(5);
assert!(!list.is_empty());

list.clear();
assert!(list.is_empty());

pub fn contains(&self, value: &T) -> boolwhere T: PartialEq,

Returns whether or not the list contains the given value.

Complexity: O(n)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert!(!list.contains(&0));

list.push_back(0);
assert!(list.contains(&0));

pub fn drain(&mut self) -> Drain<'_, T>

Creates a draining iterator that removes all values from the list and yields them in order.

All values are removed even if the iterator is only partially consumed or not consumed at all.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(5);

{
    let mut iter = list.drain();
    assert_eq!(iter.next(), Some(0));
    assert_eq!(iter.next(), Some(5));
    assert_eq!(iter.next(), None);
}

println!("{}", list.len());
assert!(list.is_empty());

pub fn front(&self) -> Option<&T>

Returns an immutable reference to the value at the front of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.front(), None);

list.push_front(0);
list.push_front(5);
assert_eq!(list.front(), Some(&5));

pub fn front_index(&self) -> Option<Index<T>>

Returns the index of the value at the front of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.front_index(), None);

list.push_front(0);
let index = list.push_front(5);
assert_eq!(list.front_index(), Some(index));

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

Returns a mutable reference to the value at the front of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.front_mut(), None);

list.push_front(0);
list.push_front(5);

let mut front = list.front_mut().unwrap();
assert_eq!(front, &mut 5);
*front *= 2;

assert_eq!(list.front(), Some(&10));

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

Returns an immutable reference to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
assert_eq!(list.get(index), Some(&0));

let index = list.push_front(5);
assert_eq!(list.get(index), Some(&5));

pub unsafe fn get_unchecked(&self, index: Index<T>) -> &T

Returns an immutable reference to the value at the given index.

Complexity: O(1)

Safety

Caller needs to guarantee that the index is in bound, and has never been removed from the list. This function does not perform generation checks. So if an element is removed then a new element is added at the same index, then the returned reference will be to the new element.

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

Returns a mutable reference to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
let value = list.get_mut(index).unwrap();
*value = 100;
assert_eq!(list.get(index), Some(&100));

pub unsafe fn get_unchecked_mut(&mut self, index: Index<T>) -> &mut T

Returns an mutable reference to the value at the given index.

Safety

Caller needs to guarantee that the index is in bound, and has never been removed from the list. See also: VecList::get_unchecked.

Complexity: O(1)

pub fn get_next_index(&self, index: Index<T>) -> Option<Index<T>>

Returns the index of the value next to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();

let index_1 = list.push_back(0);
assert_eq!(list.get_next_index(index_1), None);

let index_2 = list.push_back(5);
assert_eq!(list.get_next_index(index_1), Some(index_2));

pub fn get_previous_index(&self, index: Index<T>) -> Option<Index<T>>

Returns the index of the value previous to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();

let index_1 = list.push_front(0);
assert_eq!(list.get_previous_index(index_1), None);

let index_2 = list.push_front(5);
assert_eq!(list.get_previous_index(index_1), Some(index_2));

pub fn move_after(&mut self, index: Index<T>, target: Index<T>)

Move the node at index to after the node at target.

Panics

Panics if either index or target is invalidated. Also panics if index is the same as target.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(0);
let index_2 = list.push_back(1);
let index_3 = list.push_back(2);
let index_4 = list.push_back(3);

list.move_after(index_1, index_3);
assert_eq!(list.iter().copied().collect::<Vec<_>>(), vec![1, 2, 0, 3]);
assert_eq!(list.iter().rev().copied().collect::<Vec<_>>(), vec![3, 0, 2, 1]);

pub fn move_before(&mut self, index: Index<T>, target: Index<T>)

Move the node at index to before the node at target.

Panics

Panics if either index or target is invalidated. Also panics if index is the same as target.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(0);
let index_2 = list.push_back(1);
let index_3 = list.push_back(2);
let index_4 = list.push_back(3);

list.move_before(index_1, index_3);
assert_eq!(list.iter().copied().collect::<Vec<_>>(), vec![1, 0, 2, 3]);
assert_eq!(list.iter().rev().copied().collect::<Vec<_>>(), vec![3, 2, 0, 1]);

pub fn indices(&self) -> Indices<'_, T>

Creates an indices iterator which will yield all indices of the list in order.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
list.push_front(5);

let mut indices = list.indices();
let index = indices.next().unwrap();
assert_eq!(list.get(index), Some(&5));

let index = indices.next().unwrap();
assert_eq!(list.get(index), Some(&0));

assert_eq!(indices.next(), None);

pub fn insert_after(&mut self, index: Index<T>, value: T) -> Index<T>

Inserts the given value after the value at the given index.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the index refers to an index not in the list anymore or if the index has been invalidated. This is enforced because this function will consume the value to be inserted, and if it cannot be inserted (due to the index not being valid), then it will be lost.

Also panics if the new capacity overflows usize.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
let index_1 = list.push_front(5);
list.push_front(10);

let index_2 = list.insert_after(index_1, 1000);
assert_eq!(list.get_next_index(index_1), Some(index_2));

pub fn insert_before(&mut self, index: Index<T>, value: T) -> Index<T>

Inserts the given value before the value at the given index.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the index refers to an index not in the list anymore or if the index has been invalidated. This is enforced because this function will consume the value to be inserted, and if it cannot be inserted (due to the index not being valid), then it will be lost.

Also panics if the new capacity overflows usize.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
let index_1 = list.push_front(5);
list.push_front(10);

let index_2 = list.insert_before(index_1, 1000);
assert_eq!(list.get_previous_index(index_1), Some(index_2));

pub fn is_empty(&self) -> bool

Returns whether or not the list is empty.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert!(list.is_empty());

list.push_back(0);
assert!(!list.is_empty());

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

Creates an iterator that yields immutable references to values in the list in order.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(10);
list.push_back(200);
list.push_back(-10);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&200));
assert_eq!(iter.next(), Some(&-10));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Creates an iterator that yields mutable references to values in the list in order.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(10);
list.push_back(200);
list.push_back(-10);

let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 0));
assert_eq!(iter.next(), Some(&mut 10));
assert_eq!(iter.next(), Some(&mut 200));
assert_eq!(iter.next(), Some(&mut -10));
assert_eq!(iter.next(), None);

pub fn len(&self) -> usize

Returns the number of values in the list.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.len(), 0);

list.push_back(0);
list.push_back(1);
list.push_back(2);
assert_eq!(list.len(), 3);

pub fn new() -> Self

Creates a new list with no initial capacity.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.get(index), Some(&0));

pub fn pack_to( &mut self, minimum_capacity: usize ) -> HashMap<Index<T>, Index<T>>

Reorganizes the existing values to ensure maximum cache locality and shrinks the list such that the capacity is exactly [minimum_capacity].

This function can be used to actually increase the capacity of the list.

Complexity: O(n)

Panics

Panics if the given minimum capacity is less than the current length of the list.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(5);
let index_2 = list.push_back(10);
let index_3 = list.push_front(100);
list.remove(index_1);

assert!(list.capacity() >= 3);

let mut map = list.pack_to(list.len() + 5);
assert_eq!(list.capacity(), 7);
assert_eq!(map.len(), 2);

let index_2 = map.remove(&index_2).unwrap();
let index_3 = map.remove(&index_3).unwrap();

assert_eq!(list.get(index_2), Some(&10));
assert_eq!(list.get(index_3), Some(&100));

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), None);

pub fn pack_to_fit(&mut self) -> HashMap<Index<T>, Index<T>>

Reorganizes the existing values to ensure maximum cache locality and shrinks the list such that no additional capacity exists.

This is equivalent to calling VecList::pack_to with the current length.

Complexity: O(n)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(5);
let index_2 = list.push_back(10);
let index_3 = list.push_front(100);
list.remove(index_1);

assert!(list.capacity() >= 3);

let mut map = list.pack_to_fit();
assert_eq!(list.capacity(), 2);
assert_eq!(map.len(), 2);

let index_2 = map.remove(&index_2).unwrap();
let index_3 = map.remove(&index_3).unwrap();

assert_eq!(list.get(index_2), Some(&10));
assert_eq!(list.get(index_3), Some(&100));

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), None);

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

Removes and returns the value at the back of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.pop_back(), None);

list.push_back(0);
list.push_back(1);
list.push_back(2);
assert_eq!(list.len(), 3);

assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.len(), 2);

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

Removes and returns the value at the front of the list, if it exists.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.pop_front(), None);

list.push_front(0);
list.push_front(1);
list.push_front(2);
assert_eq!(list.len(), 3);

assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.len(), 2);

pub fn push_back(&mut self, value: T) -> Index<T>

Inserts the given value to the back of the list.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the new capacity overflows usize.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.get(index), Some(&0));

pub fn push_front(&mut self, value: T) -> Index<T>

Inserts the given value to the front of the list.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the new capacity overflows usize.

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
assert_eq!(list.get(index), Some(&0));

pub fn remove(&mut self, index: Index<T>) -> Option<T>

Removes and returns the value at the given index, if it exists.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned and the list will be unaffected.

Complexity: O(1)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.remove(index), Some(0));
assert_eq!(list.remove(index), None);

pub fn reserve(&mut self, additional_capacity: usize)

Reserves capacity for the given expected size increase.

The collection may reserve more space to avoid frequent reallocations. After calling this function, capacity will be greater than or equal to self.len() + additional_capacity. Does nothing if the current capacity is already sufficient.

Panics

Panics if the new capacity overflows usize.

Examples

use dlv_list::VecList;

let mut list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

list.reserve(10);
assert!(list.capacity() >= 10);

pub fn retain<Predicate>(&mut self, predicate: Predicate)where Predicate: FnMut(&mut T) -> bool,

Removes all elements from the list not satisfying the given predicate.

Complexity: O(n)

Examples

use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(-1);
list.push_back(1);
list.push_back(-2);
list.retain(|&mut value| value >= 0);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), None);

pub fn with_capacity(capacity: usize) -> Self

Creates a new list with the given capacity.

Examples

use dlv_list::VecList;

let mut list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

let mut list: VecList<u32> = VecList::with_capacity(10);
assert_eq!(list.capacity(), 10);

Trait Implementations

impl<T: Clone> Clone for VecList<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for VecList<T>where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for VecList<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T> Extend<&'a T> for VecList<T>where T: 'a + Copy,

fn extend<Iter>(&mut self, iter: Iter)where Iter: IntoIterator<Item = &'a T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> Extend<T> for VecList<T>

fn extend<Iter>(&mut self, iter: Iter)where Iter: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for VecList<T>

fn from_iter<Iter>(iter: Iter) -> Selfwhere Iter: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T> Hash for VecList<T>where T: Hash,

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

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<Index<T>> for VecList<T>

type Output = T

The returned type after indexing.

fn index(&self, index: Index<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<Index<T>> for VecList<T>

fn index_mut(&mut self, index: Index<T>) -> &mut Self::Output

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

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

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut VecList<T>

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a mut T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for VecList<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Ord for VecList<T>where T: Ord,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl<'a, T> PartialEq<&'a [T]> for VecList<T>where T: PartialEq,

fn eq(&self, other: &&'a [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, const N: usize> PartialEq<[T; N]> for VecList<T>where T: PartialEq,

fn eq(&self, other: &[T; N]) -> 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> PartialEq<LinkedList<T>> for VecList<T>where T: PartialEq,

fn eq(&self, other: &LinkedList<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> PartialEq<Vec<T>> for VecList<T>where T: PartialEq,

fn eq(&self, other: &Vec<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> PartialEq<VecList<T>> for &[T]where T: PartialEq,

fn eq(&self, other: &VecList<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, const N: usize> PartialEq<VecList<T>> for [T; N]where T: PartialEq,

fn eq(&self, other: &VecList<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> PartialEq<VecList<T>> for LinkedList<T>where T: PartialEq,

fn eq(&self, other: &VecList<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> PartialEq<VecList<T>> for Vec<T>where T: PartialEq,

fn eq(&self, other: &VecList<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> PartialEq for VecList<T>where T: PartialEq,

fn eq(&self, other: &Self) -> 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 for VecList<T>where T: PartialOrd<T>,

fn partial_cmp(&self, other: &Self) -> 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> Eq for VecList<T>where T: Eq,