Struct List

pub struct List<V, M = MemoryReclaimOnThreshold<2, V, V::Reclaimer>, P = SplitVec<Node<V>, Recursive>>(/* private fields */)
where
    V: ListVariant,
    M: MemoryPolicy<V>,
    P: PinnedVec<Node<V>>;

Core linked list structure which might represent either of the two variants doubly or singly linked with different memory policies such as auto-reclaim or lazy-reclaim. See DoublyList, DoublyListLazy, SinglyList, SinglyListLazy for variants.

Implementations

impl<const D: usize, R, V, P> List<V, MemoryReclaimOnThreshold<D, V, R>, P>

where V: ListVariant, R: MemoryReclaimer<V>, P: PinnedVec<Node<V>>,

pub fn into_lazy_reclaim(self) -> List<V, MemoryReclaimNever, P>

Transforms the list into lazy memory reclaim mode, such as:

• DoublyList is transformed into DoublyListLazy
• SinglyList is transformed into SinglyListLazy

This transformation has no cost, and can as well be reverted with no cost calling the into_auto_reclaim method.

The lazy mode will never automatically reorganize nodes; and hence, will never invalidate node indices.

It is still possible to manually call reclaim_closed_nodes.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(&a), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(&c), None);
assert_eq!(list.idx_err(&d), None);

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), Some(&'c'));
assert_eq!(list.get(&d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(&d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(&a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(&b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(&c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(&d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), None);
assert_eq!(list.get(&d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(&idx[0]), Some(&'c'));
assert_eq!(list.get(&idx[1]), Some(&'a'));

impl<T, P> List<Doubly<T>, MemoryReclaimNever, P>

where P: PinnedVec<Node<Doubly<T>>>,

pub fn into_auto_reclaim(self) -> DoublyList<T, P>

Transforms the list into auto memory reclaim mode, such as:

• DoublyListLazy is transformed into DoublyList
• SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(&a), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(&c), None);
assert_eq!(list.idx_err(&d), None);

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), Some(&'c'));
assert_eq!(list.get(&d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(&d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(&a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(&b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(&c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(&d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), None);
assert_eq!(list.get(&d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(&idx[0]), Some(&'c'));
assert_eq!(list.get(&idx[1]), Some(&'a'));

pub fn into_auto_reclaim_with_threshold<const D: usize>( self, ) -> DoublyListThreshold<D, T, P>

Transforms the list into auto memory reclaim mode, such as:

• DoublyListLazy is transformed into DoublyList
• SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(&a), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(&c), None);
assert_eq!(list.idx_err(&d), None);

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), Some(&'c'));
assert_eq!(list.get(&d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(&d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(&a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(&b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(&c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(&d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), None);
assert_eq!(list.get(&d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(&idx[0]), Some(&'c'));
assert_eq!(list.get(&idx[1]), Some(&'a'));

impl<T, P> List<Singly<T>, MemoryReclaimNever, P>

where P: PinnedVec<Node<Singly<T>>>,

pub fn into_auto_reclaim(self) -> SinglyList<T, P>

Transforms the list into auto memory reclaim mode, such as:

• DoublyListLazy is transformed into DoublyList
• SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(&a), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(&c), None);
assert_eq!(list.idx_err(&d), None);

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), Some(&'c'));
assert_eq!(list.get(&d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(&d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(&a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(&b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(&c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(&d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), None);
assert_eq!(list.get(&d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(&idx[0]), Some(&'c'));
assert_eq!(list.get(&idx[1]), Some(&'a'));

pub fn into_auto_reclaim_with_threshold<const D: usize>( self, ) -> SinglyListThreshold<D, T, P>

Transforms the list into auto memory reclaim mode, such as:

• DoublyListLazy is transformed into DoublyList
• SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(&a), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(&c), None);
assert_eq!(list.idx_err(&d), None);

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), Some(&'c'));
assert_eq!(list.get(&d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(&d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(&a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(&b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(&c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(&d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&c), None);
assert_eq!(list.get(&d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(&idx[0]), Some(&'c'));
assert_eq!(list.get(&idx[1]), Some(&'a'));

impl<V, M, P> List<V, M, P>

where V: ListVariant, M: MemoryPolicy<V>, P: PinnedVec<Node<V>>,

pub fn into_iter_x(self) -> impl Iterator<Item = V::Item>

Returns an arbitrary order consuming iterator of owned elements of the list.

Note that the iterator created by into_iter_x is often faster than that created by into_iter; and hence, can be preferred whenever the iteration order does not matter.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

// a -> b -> c
list.push_front('c');
list.push_front('b');
list.push_back('x');
list.push_front('a');
list.pop_back();

let mut vec: Vec<_> = list.into_iter_x().collect();

// although deterministic depending on order of mutations,
// the order can be considered deterministic.
assert_eq!(vec.as_slice(), &['c', 'b', 'a']);

vec.sort();
assert_eq!(vec.as_slice(), &['a', 'b', 'c']);

pub fn into_par_x(self) -> impl ParIter<Item = V::Item>

where V::Item: Send + Sync + Clone, Node<V>: Send + Sync, P: IntoConcurrentIter<Item = Node<V>>,

Consumes the linked list and creates a parallel iterator over owned elements in arbitrary order.

Note that into_par_x is parallel counterpart of into_iter_x.

Please see ParIter for details of the parallel computation. In brief, computation is defined as chain of iterator transformations and parallelization is handled by the underlying parallel executor.

Requires orx-parallel feature.

Examples

use orx_linked_list::*;

let new_list = || DoublyList::from_iter(0..1024);

let expected: usize = new_list().iter_x().sum();

let sum = new_list().into_par_x().sum(); // parallelized computation
assert_eq!(expected, sum);

let sum = new_list().into_par_x().num_threads(4).sum(); // using at most 4 threads
assert_eq!(expected, sum);

let sum_doubles = new_list().into_par_x().map(|x| x * 2).sum();
assert_eq!(2 * expected, sum_doubles);

let expected: usize = new_list().into_iter_x().filter(|x| x % 2 == 0).sum();
let sum_evens = new_list().into_par_x().filter(|x| x % 2 == 0).sum();

impl<V, M, P> List<V, M, P>

where V: ListVariant, M: MemoryPolicy<V>, P: PinnedVec<Node<V>>,

pub fn len(&self) -> usize

O(1) Returns the number of elements in the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

assert_eq!(0, list.len());

list.push_back('a');
list.push_front('b');
_ = list.pop_back();
list.push_back('c');

assert_eq!(2, list.len());

pub fn is_empty(&self) -> bool

Returns the number of elements in the list.

Examples

use orx_linked_list::*;

let mut list = SinglyList::new();

assert!(list.is_empty());

list.push_front('a');
assert!(!list.is_empty());

_ = list.pop_front();
assert!(list.is_empty());

pub fn memory_state(&self) -> MemoryState

Returns a key representing the memory state of the list.

The list’s memory state changes only when its nodes are reorganized.

For SinglyListLazy or DoublyListLazy:

• a node reorganization never happens implicitly,
• it can only be triggered manually by calling reclaim_closed_nodes.

For SinglyList and DoublyList with default memory policy:

• a node reorganization might be triggered on methods that remove nodes from the list such as pop_front or remove,
• a removal leads to a node reorganization if the ratio of closed nodes to all nodes exceeds 25% (see Utilization);

A node reorganization does not necessarily lead to a change in memory state; however, it is likely.

Memory state is critical due to the following:

• let indices be a collection of node indices (DoublyIdx or SinglyIdx) which are taken when the memory state was “s1”;
  • note that all methods that add an element to the list returns its index, such as push_back or insert_at,
  • further note that these growth methods never change the state.
• as long as the memory state does not change (stays as “s1”):
  • we can use all of the indices to safely access elements in constant time,
  • or use them in constant time mutation methods such as insert_after or remove.
• at some point, the memory state may change to “s2” due to:
  • manually calling reclaim_closed_nodes on a lazy memory policy list, or
  • due to many removals from the list,
• then, all of the indices obtained beforehand are invalidated,
  • constant time methods requiring indices will safely fail with a proper error.

pub fn node_utilization(&self) -> Utilization

Returns the node utilization of the underlying storage of the linked list.

pub fn iter_x(&self) -> impl Iterator<Item = &V::Item>

Creates an arbitrary order iterator on elements of the list.

Note that the iterator created by iter_x is often faster than that created by iter; and hence, can be preferred whenever the iteration order does not matter.

pub fn par_x(&self) -> impl ParIter<Item = &V::Item>

where V::Item: Send + Sync, Node<V>: Send + Sync, for<'a> &'a P: IntoConcurrentIter<Item = &'a Node<V>>,

Creates a parallel iterator over references to the elements of the linked list in arbitrary order.

Note that par_x is parallel counterpart of iter_x.

Please see ParIter for details of the parallel computation. In brief, computation is defined as chain of iterator transformations and parallelization is handled by the underlying parallel executor.

Requires orx-parallel feature.

Examples

use orx_linked_list::*;

let list: DoublyList<_> = (0..1024).collect();

let expected: usize = list.iter_x().sum();

let sum = list.par_x().sum(); // parallelized computation
assert_eq!(expected, sum);

let sum = list.par_x().num_threads(4).sum(); // using at most 4 threads
assert_eq!(expected, sum);

let sum_doubles = list.par_x().map(|x| x * 2).sum();
assert_eq!(2 * expected, sum_doubles);

let expected: usize = list.iter_x().filter(|x| *x % 2 == 0).sum();
let sum_evens = list.par_x().filter(|x| *x % 2 == 0).sum();

impl<T, M> List<Doubly<T>, M>

where M: MemoryPolicy<Doubly<T>>,

pub fn slice<'a, R>(&self, range: R) -> ListSlice<'_, Doubly<T>, M>

where R: RangeBounds<&'a DoublyIdx<T>>, T: 'a,

Creates and returns a slice of the list between the given range of indices.

Note that a linked list slice itself also behaves like a linked list, reflecting the recursive nature of the data type. However, it does not own the data. It is rather a view, like a slice is a view to a vec.

Note that slicing might be useful in various ways. For instance, we can keep indices of several critical elements of the list. We can then get all elements before, after or between any pair of these indices. Or we can combine the list with an indices vector, which provides the linked list a vec-like usage

• with the disadvantage of using more memory, and
• with the advantage of constant time insertions, removals or moves.

Panics

Panics if any of indices of the range bounds is invalid.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back(3);
list.push_front(1);
list.push_front(7);
list.push_back(4);
list.push_front(9);

let expected_values = vec![9, 7, 1, 3, 4];

assert!(list.eq_to_iter_refs(&expected_values));
assert!(list.slice(..).eq_to_iter_refs(&expected_values));

let idx: Vec<_> = list.indices().collect();

let slice = list.slice(&idx[1]..=&idx[3]);
assert_eq!(slice.front(), Some(&7));
assert_eq!(slice.back(), Some(&3));
assert!(slice.eq_to_iter_vals([7, 1, 3]));

let sum: usize = slice.iter().sum();
assert_eq!(sum, 11);

Note that the linked list and its slices are directed. In other words, it does not by default have a cyclic behavior. Therefore, if the end of the range is before the beginning, the slice will stop at the back of the list. See the following example for clarification.

Currently, cyclic or ring behavior can be achieved by ring_iter method.

use orx_linked_list::*;

let list: DoublyList<_> = (0..10).collect();
let idx: Vec<_> = list.indices().collect();

// a..b where b comes later, hence, we get the slice a..b
let slice = list.slice(&idx[1]..&idx[4]);
assert!(slice.eq_to_iter_vals([1, 2, 3]));

// a..b where b comes earlier, then, we get the slice a..back
let slice = list.slice(&idx[4]..&idx[1]);
assert!(slice.eq_to_iter_vals([4, 5, 6, 7, 8, 9]));

impl<T, M> List<Doubly<T>, M>

where M: MemoryPolicy<Doubly<T>>,

pub fn remove(&mut self, idx: &DoublyIdx<T>) -> T

O(1) Removes and returns value at the given idx of the list.

Panics

Panics:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();
list.push_back('c');
list.push_back('d');
let idx = list.push_front('b');
list.push_front('a');
list.push_back('e');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

let value = list.remove(&idx);

assert_eq!(value, 'b');
assert!(list.eq_to_iter_vals(['a', 'c', 'd', 'e']));

pub fn insert_next_to(&mut self, idx: &DoublyIdx<T>, value: T) -> DoublyIdx<T>

O(1) Inserts the given value as the next of the node with the given idx.

Panics

Panics:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
let b = list.push_back('b');
list.push_back('c');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let x = list.insert_next_to(&b, 'x');

assert_eq!(list.get(&x), Some(&'x'));
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));

pub fn insert_prev_to(&mut self, idx: &DoublyIdx<T>, value: T) -> DoublyIdx<T>

O(1) Inserts the given value as the next of the node with the given idx. Returns the index of the inserted node.

Panics

Panics:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
list.push_back('b');
let c = list.push_back('c');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let x = list.insert_prev_to(&c, 'x');

assert_eq!(list.get(&x), Some(&'x'));
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));

pub fn try_remove(&mut self, idx: &DoublyIdx<T>) -> Option<T>

O(1) Removes and returns value at the given idx of the list.

Does not change the list and returns None:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();
list.push_back('c');
list.push_back('d');
let idx = list.push_front('b');
list.push_front('a');
list.push_back('e');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

let value = list.try_remove(&idx);

assert_eq!(value, Some('b'));
assert!(list.eq_to_iter_vals(['a', 'c', 'd', 'e']));
assert_eq!(list.idx_err(&idx), Some(NodeIdxError::RemovedNode));

let value = list.try_remove(&idx);
assert_eq!(value, None);

pub fn try_insert_next_to( &mut self, idx: &DoublyIdx<T>, value: T, ) -> Result<DoublyIdx<T>, NodeIdxError>

O(1) Inserts the given value as the next of the node with the given idx. Returns the index of the inserted node.

Does not change the list and returns None:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
let b = list.push_back('b');
list.push_back('c');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let x = list.try_insert_next_to(&b, 'x').unwrap();

assert_eq!(list.get(&x), Some(&'x'));
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));

let _ = list.remove(&b);
assert!(list.eq_to_iter_vals(['a', 'x', 'c', 'd']));

let y = list.try_insert_next_to(&b, 'y');
assert_eq!(y, Err(NodeIdxError::RemovedNode));
assert!(list.eq_to_iter_vals(['a', 'x', 'c', 'd'])); // unchanged

pub fn try_insert_prev_to( &mut self, idx: &DoublyIdx<T>, value: T, ) -> Result<DoublyIdx<T>, NodeIdxError>

O(1) Inserts the given value as the next of the node with the given idx. Returns the index of the inserted node.

Does not change the list and returns None:

• if the idx is invalid (idx_err is not None for the index),
• if the element with the given idx is already removed from the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
list.push_back('b');
let c = list.push_back('c');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let x = list.try_insert_prev_to(&c, 'x').unwrap();

assert_eq!(list.get(&x), Some(&'x'));
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));

let _ = list.remove(&c);
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'd']));

let y = list.try_insert_prev_to(&c, 'y');
assert_eq!(y, Err(NodeIdxError::RemovedNode));
assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'd'])); // unchanged

impl<T, M, P> List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

pub fn insert_at(&mut self, position: usize, value: T) -> NodeIdx<Singly<T>>

O(n) Inserts the given value at the position-th element of the list.

Similar to push methods, returns an index to the inserted node to allow constant time access.

Time complexity:

• starts from the front,
• O(n) iterates until reaching the element,
• O(1) inserts the value.

Panics

Panics if position > self.len().

Example

use orx_linked_list::*;

let mut list = SinglyList::from_iter(['b', 'c', 'd']);

list.insert_at(0, 'a');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

list.insert_at(4, 'e');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

list.insert_at(3, 'x');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));

pub fn remove_at(&mut self, position: usize) -> Option<T>

O(n) Removes and returns value at the position-th element of the list. Returns None if position is out-of-bounds.

Time complexity:

• starts from the front,
• O(n) iterates until reaching the element,
• O(1) removes the value.

Example

use orx_linked_list::*;

let mut list = SinglyList::from_iter(['a', 'b', 'c', 'd', 'e']);

let value = list.remove_at(0);
assert_eq!(value, Some('a'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));

let value = list.remove_at(3);
assert_eq!(value, Some('e'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd']));

let value = list.remove_at(1);
assert_eq!(value, Some('c'));
assert!(list.eq_to_iter_vals(['b', 'd']));

impl<T, M, P> List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

pub fn insert_at(&mut self, position: usize, value: T) -> NodeIdx<Doubly<T>>

O(n) Inserts the given value at the position-th element of the list.

Time complexity:

• starts from the front,
• O(n) iterates until reaching the element,
• O(1) inserts the value.

Panics

Panics if position > self.len().

Example

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['b', 'c', 'd']);

list.insert_at(0, 'a');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

list.insert_at(4, 'e');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

list.insert_at(3, 'x');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));

pub fn insert_at_from_back( &mut self, position_from_back: usize, value: T, ) -> NodeIdx<Doubly<T>>

O(n) Inserts the given value at the position_from_back-th element of the list.

Time complexity:

• starts from the front,
• O(n) iterates until reaching the element,
• O(1) inserts the value.

Panics

Panics if position_from_back > self.len().

Example

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['b', 'c', 'd']);

list.insert_at_from_back(0, 'e');
assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));

list.insert_at_from_back(4, 'a');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

list.insert_at_from_back(2, 'x');
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));

pub fn remove_at(&mut self, position: usize) -> Option<T>

O(n) Removes and returns value at the position-th element of the list. Returns None if position is out-of-bounds.

Time complexity:

• starts from the front,
• O(n) iterates until reaching the element,
• O(1) removes the value.

Example

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd', 'e']);

let value = list.remove_at(0);
assert_eq!(value, Some('a'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));

let value = list.remove_at(3);
assert_eq!(value, Some('e'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd']));

let value = list.remove_at(1);
assert_eq!(value, Some('c'));
assert!(list.eq_to_iter_vals(['b', 'd']));

pub fn remove_at_from_back(&mut self, position_from_back: usize) -> Option<T>

O(n) Removes and returns value at the position_from_back-th element from the back of the list. Returns None if position is out-of-bounds.

Time complexity:

• starts from the back,
• O(n) iterates until reaching the element,
• O(1) removes the value.

Example

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd', 'e']);

let value = list.remove_at_from_back(4);
assert_eq!(value, Some('a'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));

let value = list.remove_at_from_back(0);
assert_eq!(value, Some('e'));
assert!(list.eq_to_iter_vals(['b', 'c', 'd']));

let value = list.remove_at_from_back(1);
assert_eq!(value, Some('c'));
assert!(list.eq_to_iter_vals(['b', 'd']));

impl<T, M, P> List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, T: PartialEq, P: PinnedVec<Node<Singly<T>>>,

pub fn idx_of(&self, value: &T) -> Option<SinglyIdx<T>>

O(n) Performs a forward search from the front and returns the index of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Obtained NodeIdx can later be used for constant time access to the corresponding element.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.idx_of(&'x');
assert!(x.is_none());

let b = list.idx_of(&'b'); // O(n)
assert!(b.is_some());

let b = b.unwrap();

let data_b = list.get(&b); // O(1)
assert_eq!(data_b, Some(&'b'));

// O(1) to create the iterators from the index
assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());

list.insert_prev_to(&b, 'X'); // O(1)
list.insert_next_to(&b, 'Y'); // O(1)
assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));

let removed = list.remove(&b);  // O(1)
assert_eq!(removed, 'b');
assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));

assert_eq!(list.get(&b), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));

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

O(n) Performs a forward search from the front and returns true if there exists a node with value equal to the given value.

Returns false if there is no element with the given value.

Examples

use orx_linked_list::*;

let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();

assert!(list.contains(&'a'));
assert!(!list.contains(&'x'));

pub fn position_of_value(&self, value: &T) -> Option<usize>

O(n) Performs a forward search from the front and returns the position of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.position_of_value(&'x');
assert_eq!(x, None);

let b = list.position_of_value(&'b'); // O(n)
assert_eq!(b, Some(1));

impl<T, M, P> List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, T: PartialEq, P: PinnedVec<Node<Doubly<T>>>,

pub fn idx_of(&self, value: &T) -> Option<DoublyIdx<T>>

O(n) Performs a forward search from the front and returns the index of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Obtained NodeIdx can later be used for constant time access to the corresponding element.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.idx_of(&'x');
assert!(x.is_none());

let b = list.idx_of(&'b'); // O(n)
assert!(b.is_some());

let b = b.unwrap();

let data_b = list.get(&b); // O(1)
assert_eq!(data_b, Some(&'b'));

// O(1) to create the iterators from the index
assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());

list.insert_prev_to(&b, 'X'); // O(1)
list.insert_next_to(&b, 'Y'); // O(1)
assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));

let removed = list.remove(&b);  // O(1)
assert_eq!(removed, 'b');
assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));

assert_eq!(list.get(&b), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));

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

O(n) Performs a forward search from the front and returns true if there exists a node with value equal to the given value.

Returns false if there is no element with the given value.

Examples

use orx_linked_list::*;

let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();

assert!(list.contains(&'a'));
assert!(!list.contains(&'x'));

pub fn position_of_value(&self, value: &T) -> Option<usize>

O(n) Performs a forward search from the front and returns the position of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.position_of_value(&'x');
assert_eq!(x, None);

let b = list.position_of_value(&'b'); // O(n)
assert_eq!(b, Some(1));

pub fn idx_of_from_back(&self, value: &T) -> Option<DoublyIdx<T>>

O(n) Performs a backward search from the back and returns the index of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Obtained NodeIdx can later be used for constant time access to the corresponding element.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.idx_of(&'x');
assert!(x.is_none());

let b = list.idx_of_from_back(&'b'); // O(n)
assert!(b.is_some());

let b = b.unwrap();

let data_b = list.get(&b); // O(1)
assert_eq!(data_b, Some(&'b'));

// O(1) to create the iterators from the index
assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());

list.insert_prev_to(&b, 'X'); // O(1)
list.insert_next_to(&b, 'Y'); // O(1)
assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));

let removed = list.remove(&b);  // O(1)
assert_eq!(removed, 'b');
assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));

assert_eq!(list.get(&b), None);
assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));

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

O(n) Performs a backward search from the back and returns true if there exists a node with value equal to the given value.

Returns false if there is no element with the given value.

Examples

use orx_linked_list::*;

let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();

assert!(list.contains(&'a'));
assert!(!list.contains(&'x'));

pub fn position_of_from_back(&self, value: &T) -> Option<usize>

O(n) Performs a backward search from the back and returns the position of the first node with value equal to the given value.

Returns None if there is no element with the given value.

Examples

use orx_linked_list::*;

let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);

let x = list.position_of_from_back(&'x');
assert_eq!(x, None);

let b = list.position_of_from_back(&'b'); // O(n)
assert_eq!(b, Some(2));

impl<T, M, P> List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

pub fn swap_front(&mut self, new_front: T) -> Option<T>

O(1) Sets value of front of the list as new_front and:

• returns value of the front element;
• returns None if the list was empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

assert_eq!(0, list.len());

let prior_front = list.swap_front('a');
assert!(prior_front.is_none());
assert_eq!(Some(&'a'), list.front());

let prior_front = list.swap_front('z');
assert_eq!(Some('a'), prior_front);
assert_eq!(Some(&'z'), list.front());

pub fn swap_back(&mut self, new_back: T) -> Option<T>

O(1) Sets value of back of the list as new_back and:

• returns value of the back element;
• returns None if the list was empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

assert_eq!(0, list.len());

let prior_back = list.swap_back('a');
assert!(prior_back.is_none());
assert_eq!(Some(&'a'), list.back());

let prior_back = list.swap_back('z');
assert_eq!(Some('a'), prior_back);
assert_eq!(Some(&'z'), list.back());

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

O(1) Pushes the value to the front of the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_front('a');
list.push_front('b');

assert_eq!(Some(&'b'), list.front());
assert_eq!(Some(&'a'), list.back());

let popped = list.pop_front();
assert_eq!(Some('b'), popped);

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

O(1) Pushes the value to the back of the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
list.push_back('b');

assert_eq!(Some(&'b'), list.back());
assert_eq!(Some(&'a'), list.front());

let popped = list.pop_back();
assert_eq!(Some('b'), popped);

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

O(1) Pops and returns the value at the front of the list; returns None if the list is empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

let popped = list.pop_front();
assert!(popped.is_none());

list.push_front('a');
assert_eq!(Some(&'a'), list.front());

let popped = list.pop_front();
assert_eq!(Some('a'), popped);
assert!(list.is_empty());

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

O(1) Pops and returns the value at the back of the list; returns None if the list is empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

let popped = list.pop_back();
assert!(popped.is_none());

list.push_front('a');
assert_eq!(Some(&'a'), list.front());

let popped = list.pop_back();
assert_eq!(Some('a'), popped);
assert!(list.is_empty());

pub fn slice_mut<'a, R>( &mut self, range: R, ) -> ListSliceMut<'_, Doubly<T>, M, P>

where R: RangeBounds<&'a DoublyIdx<T>>, T: 'a,

Creates and returns a slice of the list between the given range of indices.

Note that a linked list slice itself also behaves like a linked list, reflecting the recursive nature of the data type. However, it does not own the data. It is rather a view, like a slice is a view to a vec.

Note that slicing might be useful in various ways. For instance, we can keep indices of several critical elements of the list. We can then get all elements before, after or between any pair of these indices. Or we can combine the list with an indices vector, which provides the linked list a vec-like usage

• with the disadvantage of using more memory, and
• with the advantage of constant time insertions, removals or moves.

Panics

Panics if any of indices of the range bounds is invalid.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back(3);
list.push_front(1);
list.push_front(7);
list.push_back(4);
list.push_front(9);

let expected_values = vec![9, 7, 1, 3, 4];

assert!(list.eq_to_iter_refs(&expected_values));
assert!(list.slice(..).eq_to_iter_refs(&expected_values));

let idx: Vec<_> = list.indices().collect();

let slice = list.slice(&idx[1]..=&idx[3]);
assert_eq!(slice.front(), Some(&7));
assert_eq!(slice.back(), Some(&3));
assert!(slice.eq_to_iter_vals([7, 1, 3]));

let sum: usize = slice.iter().sum();
assert_eq!(sum, 11);

Note that the linked list and its slices are directed. In other words, it does not by default have a cyclic behavior. Therefore, if the end of the range is before the beginning, the slice will stop at the back of the list. See the following example for clarification.

Currently, cyclic or ring behavior can be achieved by ring_iter method.

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..10).collect();
let idx: Vec<_> = list.indices().collect();

// a..b where b comes later, hence, we get the slice a..b
let slice = list.slice_mut(&idx[1]..&idx[4]);
assert!(slice.eq_to_iter_vals([1, 2, 3]));

// a..b where b comes earlier, then, we get the slice a..back
let slice = list.slice_mut(&idx[4]..&idx[1]);
assert!(slice.eq_to_iter_vals([4, 5, 6, 7, 8, 9]));

impl<T, M> List<Doubly<T>, M, SplitVec<Node<Doubly<T>>, Recursive>>

where M: MemoryPolicy<Doubly<T>>,

pub fn append_front<M2: MemoryPolicy<Doubly<T>>>( &mut self, other: List<Doubly<T>, M2>, )

O(1) Appends the other list to the front of this list.

Time complexity:

• O(1) gets front of this list, say a,
• O(1) gets back of the other list, say b,
• O(1) connects b -> a.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();
list.push_front('b');
list.push_front('a');
list.push_back('c');

let other = DoublyList::from_iter(['d', 'e'].into_iter());

list.append_front(other);
assert!(list.eq_to_iter_vals(['d', 'e', 'a', 'b', 'c']));

pub fn append_back<M2: MemoryPolicy<Doubly<T>>>( &mut self, other: List<Doubly<T>, M2>, )

O(1) Appends the other list to the back of this list.

Time complexity:

• O(1) gets back of this list, say a,
• O(1) gets front of the other list, say b,
• O(1) connects a -> b.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();
list.push_front('b');
list.push_front('a');
list.push_back('c');

let other = DoublyList::from_iter(['d', 'e'].into_iter());

list.append_back(other);
assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

impl<T, M, P> List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

pub fn swap_front(&mut self, new_front: T) -> Option<T>

O(1) Sets value of front of the list as new_front and:

• returns value of the front element;
• returns None if the list was empty.

Examples

use orx_linked_list::*;

let mut list = SinglyList::new();

assert_eq!(0, list.len());

let prior_front = list.swap_front('a');
assert!(prior_front.is_none());
assert_eq!(Some(&'a'), list.front());

let prior_front = list.swap_front('z');
assert_eq!(Some('a'), prior_front);
assert_eq!(Some(&'z'), list.front());

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

O(1) Pushes the value to the front of the list.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_front('a');
list.push_front('b');

assert_eq!(Some(&'b'), list.front());
assert_eq!(Some(&'a'), list.back());

let popped = list.pop_front();
assert_eq!(Some('b'), popped);

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

O(1) Pops and returns the value at the front of the list; returns None if the list is empty.

Examples

use orx_linked_list::*;

let mut list = SinglyList::new();

let popped = list.pop_front();
assert!(popped.is_none());

list.push_front('a');
assert_eq!(Some(&'a'), list.front());

let popped = list.pop_front();
assert_eq!(Some('a'), popped);
assert!(list.is_empty());

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

Returns a forward iterator of mutable references to elements of the list from front to back.

Examples

use orx_linked_list::*;

let mut list = SinglyList::new();

list.push_front(2);
list.push_front(1);
list.push_front(0);
assert!(list.eq_to_iter_vals([0, 1, 2]));

for x in list.iter_mut() {
    *x += 40;
}

assert!(list.eq_to_iter_vals([40, 41, 42]));

impl<V, M> List<V, M>

where V: ListVariant, M: MemoryPolicy<V>,

pub fn clear(&mut self)

Clears the list removing all elements.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_front('b');
list.push_back('c');
list.push_front('a');

assert_eq!(3, list.len());

list.clear();
assert!(list.is_empty());
assert!(list.front().is_none());

pub fn iter_mut_x(&mut self) -> impl Iterator<Item = &mut V::Item>

Returns an arbitrary order iterator of mutable references to elements of the list from front to back.

Note that the iterator created by iter_mut_x is often faster than that created by iter_mut; and hence, can be preferred whenever the iteration order does not matter.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_front(2);
list.push_front(1);
list.push_front(0);
assert!(list.eq_to_iter_vals([0, 1, 2]));

for x in list.iter_mut_x() {
    *x += 40;
}

assert!(list.eq_to_iter_vals([40, 41, 42]));

impl<T> List<Singly<T>>

pub fn new() -> Self

Creates an empty singly linked list with default memory reclaim policy.

pub fn with_threshold_reclaimer<const D: usize>() -> SinglyListThreshold<D, T>

Creates an empty singly linked list with custom memory reclaim on threshold policy:

• memory of removed nodes are automatically reclaimed when the ratio of closed nodes to all nodes exceeds one over 2^D:
  • when D = 0: memory will be reclaimed when utilization is below 0.00% (equivalent to Lazy).
  • when D = 1: memory will be reclaimed when utilization is below 50.00%.
  • when D = 2: memory will be reclaimed when utilization is below 75.00%.
  • when D = 3: memory will be reclaimed when utilization is below 87.50%.
  • when D = 4: memory will be reclaimed when utilization is below 93.75%.

impl<T> List<Singly<T>, MemoryReclaimNever>

pub fn new() -> Self

Creates an empty singly linked list with lazy memory reclaim policy.

Memory of removed nodes are never reclaimed implicitly, the caller can explicitly reclaim by calling reclaim_closed_nodes.

This also guarantees that indices will never be invalidated implicitly.

impl<T> List<Doubly<T>>

pub fn new() -> Self

Creates an empty doubly linked list with default memory reclaim policy.

pub fn with_threshold_reclaimer<const D: usize>() -> DoublyListThreshold<D, T>

Creates an empty doubly linked list with custom memory reclaim on threshold policy:

• memory of removed nodes are automatically reclaimed when the ratio of closed nodes to all nodes exceeds one over 2^D:
  • when D = 0: memory will be reclaimed when utilization is below 0.00% (equivalent to Lazy).
  • when D = 1: memory will be reclaimed when utilization is below 50.00%.
  • when D = 2: memory will be reclaimed when utilization is below 75.00%.
  • when D = 3: memory will be reclaimed when utilization is below 87.50%.
  • when D = 4: memory will be reclaimed when utilization is below 93.75%.

impl<T> List<Doubly<T>, MemoryReclaimNever>

pub fn new() -> Self

Creates an empty doubly linked list with lazy memory reclaim policy.

Memory of removed nodes are never reclaimed implicitly, the caller can explicitly reclaim by calling reclaim_closed_nodes.

This also guarantees that indices will never be invalidated implicitly.

impl<V, M> List<V, M, FixedVec<Node<V>>>

where V: ListVariant, M: MemoryPolicy<V>,

pub fn with_fixed_capacity(fixed_capacity: usize) -> Self

Creates a linked list that uses a FixedVec<T> as the underlying storage.

impl<V, M> List<V, M, SplitVec<Node<V>, Doubling>>

where V: ListVariant, M: MemoryPolicy<V>,

pub fn with_doubling_growth() -> Self

Creates a linked list that uses a SplitVec<T, Doubling> as the underlying storage.

impl<V, M> List<V, M, SplitVec<Node<V>, Recursive>>

where V: ListVariant, M: MemoryPolicy<V>,

pub fn with_recursive_growth() -> Self

Creates a linked list that uses a SplitVec<T, Recursive> as the underlying storage.

impl<V, M> List<V, M, SplitVec<Node<V>, Linear>>

where V: ListVariant, M: MemoryPolicy<V>,

pub fn with_linear_growth(constant_fragment_capacity_exponent: usize) -> Self

Creates a linked list that uses a SplitVec<T, Linear> as the underlying storage.

Each fragment will have a capacity of 2 ^ constant_fragment_capacity_exponent.

impl<V, M, P> List<V, M, P>

where V: ListVariant, M: MemoryPolicy<V>, P: PinnedVec<Node<V>>,

pub fn reclaim_closed_nodes(&mut self) -> (MemoryState, MemoryState)

Manually attempts to reclaim closed nodes.

Safety

It is important to note that, memory reclaim operation might lead to reorganization of the nodes which invalidates the node indices obtained before the process.

Trait Implementations

impl<T: Clone, M, P> Clone for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>> + Default,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Clone, M, P> Clone for List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>> + Default,

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, M, P> Debug for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>, List<Doubly<T>, M, P>: Default,

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

Formats the value using the given formatter.

impl<T: Debug, M, P> Debug for List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>, List<Singly<T>, M, P>: Default,

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

Formats the value using the given formatter.

impl<'a, T: Clone, M, P> Extend<&'a T> for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

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, M, P> Extend<T> for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

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<const D: usize, R, V, P> From<List<V, MemoryReclaimNever, P>> for List<V, MemoryReclaimOnThreshold<D, V, R>, P>

where V: ListVariant, R: MemoryReclaimer<V>, P: PinnedVec<Node<V>>,

fn from(value: List<V, MemoryReclaimNever, P>) -> Self

Converts to this type from the input type.

impl<const D: usize, R, V, P> From<List<V, MemoryReclaimOnThreshold<D, V, R>, P>> for List<V, MemoryReclaimNever, P>

where V: ListVariant, R: MemoryReclaimer<V>, P: PinnedVec<Node<V>>,

fn from(value: List<V, MemoryReclaimOnThreshold<D, V, R>, P>) -> Self

Converts to this type from the input type.

impl<T, M> FromIterator<T> for List<Doubly<T>, M>

where M: MemoryPolicy<Doubly<T>>,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T, M> FromIterator<T> for List<Singly<T>, M>

where M: MemoryPolicy<Singly<T>>,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'i, T, M, P> Index<&'i NodeIdx<Doubly<T>>> for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

fn index(&self, index: &'i DoublyIdx<T>) -> &Self::Output

Returns the element at the given index.

Panics

Panics if the index is invalid; i.e.,

• list.is_valid(index) returns false, equivalently,
• list.idx_err(index) returns the detail of the error.

type Output = T

The returned type after indexing.

impl<'i, T, M, P> Index<&'i NodeIdx<Singly<T>>> for List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

fn index(&self, index: &'i SinglyIdx<T>) -> &Self::Output

Returns the element at the given index.

Panics

Panics if the index is invalid; i.e.,

• list.is_valid(index) returns false, equivalently,
• list.idx_err(index) returns the detail of the error.

type Output = T

The returned type after indexing.

impl<'i, T, M, P> IndexMut<&'i NodeIdx<Doubly<T>>> for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

fn index_mut(&mut self, index: &'i DoublyIdx<T>) -> &mut Self::Output

Returns a mutable reference to the element at the given index.

Panics

Panics if the index is invalid; i.e.,

• list.is_valid(index) returns false, equivalently,
• list.idx_err(index) returns the detail of the error.

impl<'i, T, M, P> IndexMut<&'i NodeIdx<Singly<T>>> for List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

fn index_mut(&mut self, index: &'i SinglyIdx<T>) -> &mut Self::Output

Returns a mutable reference to the element at the given index.

Panics

Panics if the index is invalid; i.e.,

• list.is_valid(index) returns false, equivalently,
• list.idx_err(index) returns the detail of the error.

impl<T, M, P> IntoIterator for List<Doubly<T>, M, P>

where M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

fn into_iter(self) -> Self::IntoIter

Returns a consuming forward iterator to owned elements of the list from front to back.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

// a -> b -> c
list.push_front('c');
list.push_front('b');
list.push_front('a');

let mut iter = list.into_iter();

assert_eq!(Some('a'), iter.next());
assert_eq!(Some('b'), iter.next());
assert_eq!(Some('c'), iter.next());
assert!(iter.next().is_none());

type Item = T

The type of the elements being iterated over.

type IntoIter = DoublyIterOwned<T, P>

Which kind of iterator are we turning this into?

impl<T, M, P> IntoIterator for List<Singly<T>, M, P>

where M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

fn into_iter(self) -> Self::IntoIter

Returns a consuming forward iterator to owned elements of the list from front to back.

Examples

use orx_linked_list::*;

let mut list = SinglyList::new();

// a -> b -> c
list.push_front('c');
list.push_front('b');
list.push_front('a');

let mut iter = list.into_iter();

assert_eq!(Some('a'), iter.next());
assert_eq!(Some('b'), iter.next());
assert_eq!(Some('c'), iter.next());
assert!(iter.next().is_none());

type Item = T

The type of the elements being iterated over.

type IntoIter = SinglyIterOwned<T, P>

Which kind of iterator are we turning this into?

impl<T, M, P> PartialEq for List<Doubly<T>, M, P>

where T: PartialEq, M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

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, M, P> PartialEq for List<Singly<T>, M, P>

where T: PartialEq, M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,

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, M, P> Eq for List<Doubly<T>, M, P>

where T: PartialEq, M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,

impl<T, M, P> Eq for List<Singly<T>, M, P>

where T: PartialEq, M: MemoryPolicy<Singly<T>>, P: PinnedVec<Node<Singly<T>>>,