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 by their value. This operation will invalidate all previously held handles, and they should be discarded. If required, a set of new handles can be obtained by calling handles(). This operation completes in O(n log n) time.

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>