Struct LinkedVector

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

A doubly-linked list that uses handles to refer to elements that exist within a vector. This allows for O(1) insertion and removal of elements from the list, and O(1) access to elements by handle.

Implementations

impl<T> LinkedVector<T>

pub fn new() -> Self

Creates a new, empty LinkedVector.

pub fn with_capacity(size: usize) -> Self

Creates a new, empty LinkedVector with the specified capacity.

pub fn append(&mut self, other: &mut Self)

Moves all elements from other into self, leaving other empty. This operation completes in O(n) time where n is the length of other.

use linked_vector::*;
let mut lv1 = LinkedVector::new();
let mut lv2 = LinkedVector::from([1, 2, 3]);
 
lv1.append(&mut lv2);
 
assert_eq!(lv1.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
assert_eq!(lv2.len(), 0);

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

Gives a reference to the back element, or None if the list is empty. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
assert_eq!(lv.back(), Some(&3));

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

Gives a mutable reference to the element back element, or None if the list is empty. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
 
*lv.back_mut().unwrap() = 42;
 
assert_eq!(lv.back_mut(), Some(&mut 42));

pub fn capacity(&self) -> usize

Returns the total number of elements the vector can hold without reallocating.

pub fn clear(&mut self)

Removes all elements from the list.

pub fn compact(self) -> Self

Consumes the LinkedVector and produces a new one that has all its nodes placed contiguously in sequential order at the front of the internal vector. Where performance is critical and the cost of a compacting operation is infrequent and acceptible, compacting the vector may give a gain in performance for certain use cases. All handles from the old vector will not be native to the new compacted vector. compact() completes in O(n) time.

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

where T: PartialEq,

Returns true if the list contains an element with the given value. This operation completes in O(n) time where n is the length of the list.

pub fn cursor(&self, node: HNode) -> Cursor<'_, T>

Creates a cursor that can be used to traverse the list starting at the given node. This operation completes in O(1) time.

use linked_vector::*;
let lv = LinkedVector::from([1, 2, 3, 4, 5, 6, 7, 8, 9]);
let h3 = lv.handle(2).unwrap();
let mut cursor = lv.cursor(h3);
 
cursor.forward(3);
 
assert_eq!(*cursor, 6);

pub fn cursor_mut(&mut self, node: HNode) -> CursorMut<'_, T>

Creates a cursor that holds a mutable reference to the LinkedVector that can be used to traverse the list starting at the given node. If the vector is empty, None is returned. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3, 4, 5, 6]);
let mut cursor = lv.cursor_mut(lv.front_node().unwrap());
 
cursor.forward(3);
 
assert_eq!(*cursor, 4);
 
*cursor = 42;
 
assert_eq!(lv.to_vec(), vec![1, 2, 3, 42, 5, 6]);

pub fn cursor_back(&self) -> Option<Cursor<'_, T>>

Returns a Cursor starting at the front element, or None if the list is empty. If the vector is empty, None is returned. This operation completes in O(1) time.

pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, T>>

Returns a Cursor starting at the back element, or None if the list is empty. This operation completes in O(1) time.

pub fn cursor_front(&self) -> Option<Cursor<'_, T>>

Gives a reference to the element at the front of the vector, or None if the list is empty. This operation completes in O(1) time.

pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, T>>

Gives a mutable Cursor starting at the front of the vector, or None if the list is empty. This operation completes in O(1) time.

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

Gives a reference to the element at the front of the vector, or None if the list is empty. This operation completes in O(1) time.

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

Gives a mutable reference to the element at the front of the vector, or None if the list is empty. This operation completes in O(1) time.

pub fn front_node(&self) -> Option<HNode>

Returns a handle to the first node in the list, or None if the list is empty. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
let hnode = lv.push_front(42);
 
assert_eq!(lv.front_node(), Some(hnode));
assert_eq!(lv.front(), Some(&42));

pub fn back_node(&self) -> Option<HNode>

Returns a handle to the last node in the list, or None if the list is empty. This operation completes in O(1) time.

pub fn get(&self, node: HNode) -> Option<&T>

Provides a reference to the element indicated by the given handle, or None if the handle is invalid. With the “optionless-accesors” feature, this method returns its reference directly - no Option, see usage notes. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
let hnode = lv.push_front(42);
 
assert_eq!(lv.get(hnode), Some(&42));

pub fn get_mut(&mut self, node: HNode) -> Option<&mut T>

Provides a mutable reference to the element indicated by the given handle, or None if the handle is invalid. With the “optionless-accessors” feature enabled, this method returns its reference directly - no Option, see usage notes. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
let hnode = lv.push_front(0);
 
*lv.get_mut(hnode).unwrap() = 42;
 
assert_eq!(lv[hnode], 42);

pub fn handle(&self, index: usize) -> Option<HNode>

Returns the handle to the node at the given index, or None if the index is out of bounds. If index > self.len / 2, the search starts from the end of the list. This operation performs in O(n / 2) time worst case.

use linked_vector::*;
let mut lv = LinkedVector::new();
let h1 = lv.push_front(1);
let h2 = lv.push_front(2);
let h3 = lv.push_front(3);
 
assert_eq!(lv.handle(1), Some(h2));
assert_eq!(lv.handle(3), None);
assert_eq!(lv.handle(2), Some(h1));

pub fn handles(&self) -> Handles<'_, T>

Returns an iterator over the handles of the vector. The handles will reflect the order of the linked list. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.push_back(43);
let h3 = lv.push_back(44);
 
let iter = lv.handles();
 
assert_eq!(iter.collect::<Vec<_>>(), vec![h1, h2, h3]);

pub fn insert(&mut self, node: HNode, value: T) -> HNode

Inserts a new element at the position indicated by the handle, node. Returns a handle to the newly inserted element. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.insert(h1, 43);
 
assert_eq!(lv.next_node(h2), Some(h1));
assert_eq!(lv[h1], 42);

pub fn insert_after(&mut self, node: HNode, value: T) -> HNode

Inserts a new element after the one indicated by the handle, node. Returns a handle to the newly inserted element. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.insert_after(h1, 43);
 
assert_eq!(lv.next_node(h1), Some(h2));
assert_eq!(lv[h2], 43);

pub fn is_empty(&self) -> bool

Returns true if the list contains no elements.

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

Returns an iterator over the elements of the list.

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

Returns an iterator over the elements of the list. Renders mutable references to the elements.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
 
lv.iter_mut().for_each(|x| *x += 1);
 
assert_eq!(lv, LinkedVector::from([2, 3, 4]));

pub fn len(&self) -> usize

Returns the length of the list.

pub fn next_node(&self, node: HNode) -> Option<HNode>

Returns a handle to the next node in the list, or None if the given handle is the last node in the list. This operation completes in O(1)

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.push_back(43);
 
assert_eq!(lv.next_node(h1), Some(h2));

pub fn next_value(&self, node: HNode) -> Option<&T>

Returns a reference to the next element’s value in the list, or None if the given handle is the last node in the list. This operation completes in O(1) time.

pub fn next_value_mut(&mut self, node: HNode) -> Option<&mut T>

Returns a mutable reference to the next element’s value in the list, or None if the given handle is the last node in the list. This operation completes in O(1) time.

pub fn prev_node(&self, node: HNode) -> Option<HNode>

Returns a handle to the previous node in the list, or None if the given handle is the first node in the list. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.push_back(43);
 
assert_eq!(lv.prev_node(h2), Some(h1));

pub fn prev_value(&self, node: HNode) -> Option<&T>

Returns a reference to the previous element’s value in the list, or None if the given handle is the first node in the list. This operation completes in O(1) time.

pub fn prev_value_mut(&mut self, node: HNode) -> Option<&mut T>

Returns a mutable reference to the previous element’s value in the list, or None if the given handle is the first node in the list. This operation completes in O(1) time.

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

Pops the last element of the vector. Returns None if the vector is empty. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
 
assert_eq!(lv.pop_back(), Some(3));

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

Pops the first element of the vector. Returns None if the vector is empty. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
 
assert_eq!(lv.pop_front(), Some(1));

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

Pushes a new element to the back of the list. Returns a handle to the newly inserted element. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::new();
 
let h1 = lv.push_back(42);
let h2 = lv.push_back(43);
 
assert_eq!(lv.next_node(h1), Some(h2));

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

Pushes a new element to the front of the list. Returns a handle to the newly inserted element. This operation completes in O(1) time.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
 
let h1 = lv.front_node().unwrap();
let h2 = lv.push_front(42);
 
assert_eq!(lv.next_node(h2), Some(h1));

pub fn remove(&mut self, node: HNode) -> Option<T>

Removes the element indicated by the handle, node. Returns the element if the handle is valid, or None otherwise. This operation completes in O(1) time. With the "optionless-accessors" feature enabled, this method returns its value directly, not wrapped in an Option, see usage notes.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3]);
let handles = lv.handles().collect::<Vec<_>>();
 
lv.remove(handles[1]);
 
assert_eq!(lv, LinkedVector::from([1, 3]));

pub fn sort(&mut self)

where T: Ord,

Sorts the elemements in place in ascending order. Previously held handles will still be valid and reference the same elements (with the same values) as before. Only the next and prev fields of the nodes are modified in the list. Uses Rust’s stable sort internally and requires some auxiliary memory for a temporary handle list.

use linked_vector::*;
let mut lv = LinkedVector::new();
let h1 = lv.push_back(3);
let h2 = lv.push_back(2);
let h3 = lv.push_back(1);
 
lv.extend([7, 11, 4, 6, 8, 13, 12, 9, 14, 5, 10]);
 
lv.sort();
 
assert_eq!(lv.to_vec(), (1..15).collect::<Vec<_>>());
assert_eq!(lv[h1], 3);
assert_eq!(lv[h2], 2);
assert_eq!(lv[h3], 1);

pub fn sort_by<F>(&mut self, compare: F)

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

Sorts the elemements in place using the provided comparison function. See sort() for more details.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
 
lv.sort_by(|a, b| b.cmp(a));
 
assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);

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

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

Sorts the elemements in place in using the provided key extraction function. See sort() for more details.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
 
lv.sort_by_key(|k| -k);
 
assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);

pub fn sort_unstable(&mut self)

where T: Ord,

Sorts the elemements in place in ascending order. Previously held handles will still be valid and reference the same elements (with the same values) as before. Only the next and prev fields of the nodes are modified in the list. Uses Rust’s unstable sort internally and requires some auxiliary memory for a temporary handle list.

use linked_vector::*;
let mut lv = LinkedVector::from([5, 4, 3, 2, 1, 0]);
 
lv.sort_unstable();
 
assert_eq!(lv.to_vec(), vec![0, 1, 2, 3, 4, 5]);

pub fn sort_unstable_by<F>(&mut self, compare: F)

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

Sorts the elemements in place using the provided comparison function. See sort_unstable() for more details.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
 
lv.sort_unstable_by(|a, b| b.cmp(a));
 
assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);

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

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

Sorts the elemements in place in using the provided key extraction function. See sort_unstable() for more details.

use linked_vector::*;
let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
 
lv.sort_unstable_by_key(|k| -k);
 
assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Returns a vector containing the elements of the list. This operation completes in O(n) time.

use linked_vector::*;
let lv = LinkedVector::from([1, 2, 3]);
 
assert_eq!(lv.to_vec(), vec![1, 2, 3]);

Trait Implementations

impl<T> Clone for LinkedVector<T>

where T: Clone,

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 LinkedVector<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for LinkedVector<T>

fn default() -> Self

Renders the default value for an HNode. This will internally be set to BAD_HANDLE which is a handle that is invalid.

impl<'a, T> Extend<&'a T> for LinkedVector<T>

where T: Clone,

fn extend<I>(&mut self, iter: I)

where I: 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 LinkedVector<T>

fn extend<I>(&mut self, iter: I)

where I: 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, const N: usize> From<[T; N]> for LinkedVector<T>

fn from(arr: [T; N]) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for LinkedVector<T>

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

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T> Hash for LinkedVector<T>

where T: Hash,

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<HNode> for LinkedVector<T>

type Output = T

The returned type after indexing.

fn index(&self, handle: HNode) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> Index<usize> for LinkedVector<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<HNode> for LinkedVector<T>

fn index_mut(&mut self, handle: HNode) -> &mut Self::Output

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

impl<T> IndexMut<usize> for LinkedVector<T>

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

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

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

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = 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<'a, T> IntoIterator for &'a mut LinkedVector<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'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 LinkedVector<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> PartialEq for LinkedVector<T>

where T: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<T: Eq> Eq for LinkedVector<T>