Struct dlv_list::VecList

pub struct VecList<EntryData> { /* 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 allocation 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<EntryData> VecList<EntryData>

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

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_mut(&mut self) -> Option<&mut EntryData>

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: &EntryData) -> boolwhere
    EntryData: 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<'_, EntryData>

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<&EntryData>

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_mut(&mut self) -> Option<&mut EntryData>

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<EntryData>) -> Option<&EntryData>

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 fn get_mut(&mut self, index: Index<EntryData>) -> Option<&mut EntryData>

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 fn get_next_index(&self, index: Index<EntryData>) -> Option<Index<EntryData>>

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<EntryData>
) -> Option<Index<EntryData>>

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 indices(&self) -> Indices<'_, EntryData>

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<EntryData>,
    value: EntryData
) -> Index<EntryData>

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<EntryData>,
    value: EntryData
) -> Index<EntryData>

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<'_, EntryData>

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<'_, EntryData>

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<EntryData>, Index<EntryData>>

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<EntryData>, Index<EntryData>>

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<EntryData>

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<EntryData>

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: EntryData) -> Index<EntryData>

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: EntryData) -> Index<EntryData>

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<EntryData>) -> Option<EntryData>

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 unsafe fn remove_sync(&mut self, index: Index<EntryData>) -> EntryData

Removes the value at the given index.

This function is highly unsafe in the sense that it will break logical invariants for this type, but it does not expose any undefined behavior. Any further use of this type after calling this function is highly likely to cause a panic (but no memory unsafety). It should only be used when both of the following conditions apply:

1. You only want to remove values from the list; no iteration, insertion or retrieval is to be done afterwards. This is the only removal function that can be used after at least one invocation of it (i.e., do not use VecList::remove, it will probably panic).
2. For some reason, you require the ability to parallelize independent removals from the list without locking. This is the primary reason this function is unsafe, as it does not try to maintain logical invariants since that would require accessing shared memory.

Panics

Panics if there is no value at the given index or if the generation does not match.

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 EntryData) -> 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<EntryData: Clone> Clone for VecList<EntryData>

fn clone(&self) -> VecList<EntryData>

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<EntryData> Default for VecList<EntryData>

fn default() -> Self

Returns the “default value” for a type.

impl<'entries, EntryData> Extend<&'entries EntryData> for VecList<EntryData>where
    EntryData: 'entries + Copy,

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

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<EntryData> Extend<EntryData> for VecList<EntryData>

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

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<EntryData> FromIterator<EntryData> for VecList<EntryData>

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

Creates a value from an iterator.

impl<EntryData> Hash for VecList<EntryData>where
    EntryData: 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<EntryData> Index<Index<EntryData>> for VecList<EntryData>

type Output = EntryData

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<EntryData> IndexMut<Index<EntryData>> for VecList<EntryData>

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

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

impl<'entries, EntryData> IntoIterator for &'entries VecList<EntryData>

type IntoIter = Iter<'entries, EntryData>

Which kind of iterator are we turning this into?

type Item = &'entries EntryData

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'entries, EntryData> IntoIterator for &'entries mut VecList<EntryData>

type IntoIter = IterMut<'entries, EntryData>

Which kind of iterator are we turning this into?

type Item = &'entries mut EntryData

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<EntryData> IntoIterator for VecList<EntryData>

type IntoIter = IntoIter<EntryData>

Which kind of iterator are we turning this into?

type Item = EntryData

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<EntryData> Ord for VecList<EntryData>where
    EntryData: 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<Self>,

Restrict a value to a certain interval.

impl<'slice, EntryData> PartialEq<&'slice [EntryData]> for VecList<EntryData>where
    EntryData: PartialEq,

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

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

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

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<EntryData> Eq for VecList<EntryData>where
    EntryData: Eq,