Struct linked_vector::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 contains(&self, value: &T) -> boolwhere
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) -> Cursor<'_, T>

Creates a cursor that can be used to traverse the list.

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

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

Creates a cursor that holds a mutable reference to the LinkedVector that can be used to traverse the list.

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

pub fn cursor_at(&self, hnode: 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 h  = lv.find_node(&3).unwrap();
let mut cursor = lv.cursor_at(h);
 
cursor.forward(3);
 
assert_eq!(cursor.get(), Some(&6));

pub fn cursor_at_mut(&mut self, hnode: 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.

pub fn find_node(&self, value: &T) -> Option<HNode>where
T: PartialEq,

Returns the handle to the first node with the given value. If no such node exists, None is returned. This operation completes in O(n) time.

use linked_vector::*;
let lv = LinkedVector::from([1, 2, 3, 4, 5, 6]);
let h  = lv.find_node(&3).unwrap();
 
assert_eq!(lv.get(h), Some(&3));
assert_eq!(lv.find_node(&42), None);

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_node().and_then(|h| lv.get(h)), 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. 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. 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.get(hnode), Some(&42));

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_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.get(h2), Some(&43));

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

Inserts a new element before 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_before(h1, 43);
 
assert_eq!(lv.next_node(h2), Some(h1));
assert_eq!(lv.get(h1), Some(&42));

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 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 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 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, value: &T) -> Option<T>where
T: PartialEq,

Removes the first element with the indicated value. Returns the element if it is found, or None otherwise. This operation completes in O(n) time.

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

pub fn remove_node(&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.

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

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. Quicksort is used with the Lomuto partition scheme. Only the next and prev fields of the nodes are modified in the list. This operation completes in O(n log n) time.

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.sort_unstable();
 
assert_eq!(lv.to_vec(), vec![1, 2, 3]);
assert_eq!(lv.get(h1), Some(&3));
assert_eq!(lv.get(h2), Some(&2));
assert_eq!(lv.get(h3), Some(&1));

pub fn swap(&mut self, hnode1: &mut HNode, hnode2: &mut HNode)

Swaps the elements indicated by the handles, h1 and h2. Only the next and prev fields of nodes are altered. h1 and h2 will be updated to reference the swapped values. This operation completes in O(1) time.

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

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

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

Formats the value using the given formatter.

impl<T> Default for LinkedVector<T>

fn default() -> Self

Returns the “default value” for a type.

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) -> Selfwhere
I: IntoIterator<Item = T>,

Creates a value from an iterator.

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

fn index_mut(&mut self, handle: HNode) -> &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<LinkedVector<T>> for LinkedVector<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: Eq> Eq for LinkedVector<T>