Struct linked_vector::LinkedVector
source · pub struct LinkedVector<T> { /* private fields */ }
Expand description
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§
source§impl<T> LinkedVector<T>
impl<T> LinkedVector<T>
sourcepub fn with_capacity(size: usize) -> Self
pub fn with_capacity(size: usize) -> Self
Creates a new, empty LinkedVector
with the specified capacity.
sourcepub fn append(&mut self, other: &mut Self)
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);
sourcepub fn back(&self) -> Option<&T>
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));
sourcepub fn back_mut(&mut self) -> Option<&mut T>
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));
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Returns the total number of elements the vector can hold without reallocating.
sourcepub fn compact(self) -> Self
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.
sourcepub fn contains(&self, value: &T) -> boolwhere
T: PartialEq,
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.
sourcepub fn cursor(&self, node: HNode) -> Cursor<'_, T>
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);
sourcepub fn cursor_mut(&mut self, node: HNode) -> CursorMut<'_, T>
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]);
sourcepub fn cursor_back(&self) -> Option<Cursor<'_, T>>
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.
sourcepub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, T>>
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.
sourcepub fn cursor_front(&self) -> Option<Cursor<'_, T>>
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.
sourcepub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, T>>
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.
sourcepub fn front(&self) -> Option<&T>
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.
sourcepub fn front_mut(&mut self) -> Option<&mut T>
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.
sourcepub fn front_node(&self) -> Option<HNode>
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));
sourcepub fn back_node(&self) -> Option<HNode>
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.
sourcepub fn get(&self, node: HNode) -> Option<&T>
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));
sourcepub fn get_mut(&mut self, node: HNode) -> Option<&mut T>
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);
sourcepub fn handle(&self, index: usize) -> Option<HNode>
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));
sourcepub fn handles(&self) -> Handles<'_, T> ⓘ
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]);
sourcepub fn insert(&mut self, node: HNode, value: T) -> HNode
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);
sourcepub fn insert_after(&mut self, node: HNode, value: T) -> HNode
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);
sourcepub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
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]));
sourcepub fn next_node(&self, node: HNode) -> Option<HNode>
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));
sourcepub fn next_value(&self, node: HNode) -> Option<&T>
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.
sourcepub fn next_value_mut(&mut self, node: HNode) -> Option<&mut T>
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.
sourcepub fn prev_node(&self, node: HNode) -> Option<HNode>
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));
sourcepub fn prev_value(&self, node: HNode) -> Option<&T>
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.
sourcepub fn prev_value_mut(&mut self, node: HNode) -> Option<&mut T>
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.
sourcepub fn pop_back(&mut self) -> Option<T>
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));
sourcepub fn pop_front(&mut self) -> Option<T>
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));
sourcepub fn push_back(&mut self, value: T) -> HNode
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));
sourcepub fn push_front(&mut self, value: T) -> HNode
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));
sourcepub fn remove(&mut self, node: HNode) -> Option<T>
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]));
sourcepub fn sort(&mut self)where
T: Ord,
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);
sourcepub fn sort_by<F>(&mut self, compare: F)where
F: FnMut(&T, &T) -> Ordering,
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]);
sourcepub fn sort_by_key<K, F>(&mut self, key: F)where
K: Ord,
F: FnMut(&T) -> K,
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]);
sourcepub fn sort_unstable(&mut self)where
T: Ord,
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]);
sourcepub fn sort_unstable_by<F>(&mut self, compare: F)where
F: FnMut(&T, &T) -> Ordering,
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]);
sourcepub fn sort_unstable_by_key<K, F>(&mut self, key: F)where
K: Ord,
F: FnMut(&T) -> K,
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]);
Trait Implementations§
source§impl<T> Clone for LinkedVector<T>where
T: Clone,
impl<T> Clone for LinkedVector<T>where
T: Clone,
source§impl<T> Debug for LinkedVector<T>where
T: Debug,
impl<T> Debug for LinkedVector<T>where
T: Debug,
source§impl<T> Default for LinkedVector<T>
impl<T> Default for LinkedVector<T>
source§impl<'a, T> Extend<&'a T> for LinkedVector<T>where
T: Clone,
impl<'a, T> Extend<&'a T> for LinkedVector<T>where
T: Clone,
source§fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = &'a T>,
fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = &'a T>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)source§impl<T> Extend<T> for LinkedVector<T>
impl<T> Extend<T> for LinkedVector<T>
source§fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = T>,
fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = T>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)