Struct orx_linked_list::List

pub struct List<'a, V, T>
where
    T: 'a,
    V: ListVariant<'a, T>,
    V::Ends: ListEnds<'a, V, T>,
{ /* private fields */ }

Core structure for singly and doubly linked lists:

• type SinglyLinkedList<'a, T> = List<'a, Singly, T>;
• type DoublyLinkedList<'a, T> = List<'a, Doubly, T>;

Examples

Below is the simple usage of a doubly linked list.

use orx_linked_list::*;

// empty
let doubly = DoublyLinkedList::<i32>::new();
let doubly = List::<Doubly, i32>::new();

// from iter
let doubly: DoublyLinkedList<_> = [1, 2, 3].into_iter().collect();
let mut doubly: List<Doubly, _> = [1, 2, 3].into_iter().collect();
assert_eq!(Some(&1), doubly.front());
assert_eq!(Some(&3), doubly.back());

doubly.push_front(0);
doubly.push_back(4);

assert_eq!(Some(&0), doubly.front());
assert_eq!(Some(&4), doubly.back());

assert_eq!(Some(0), doubly.pop_front());
assert_eq!(Some(4), doubly.pop_back());

assert_eq!(vec![1, 2, 3], doubly.iter().copied().collect::<Vec<_>>());
assert_eq!(vec![3, 2, 1], doubly.iter_from_back().copied().collect::<Vec<_>>());

Using a singly linked list can be used instead by using the SinglyLinkedList type alias or changing the variant from Doubly to Singly.

use orx_linked_list::*;

// empty
let singly = SinglyLinkedList::<i32>::new();
let singly = List::<Singly, i32>::new();

// from iter
let singly: SinglyLinkedList<_> = [1, 2, 3].into_iter().collect();
let mut singly: List<Singly, _> = [1, 2, 3].into_iter().collect();
assert_eq!(Some(&1), singly.front());
assert_eq!(Some(&3), singly.back());

singly.push_front(0);

assert_eq!(Some(&0), singly.front());

assert_eq!(Some(0), singly.pop_front());

assert_eq!(vec![1, 2, 3], singly.iter().copied().collect::<Vec<_>>());

Implementations

impl<'a, V, T: 'a> List<'a, V, T>

where V: ListVariant<'a, T>, V::Ends: ListEnds<'a, V, T>,

pub fn new() -> Self

Creates an empty list.

Examples

use orx_linked_list::*;

let list: List<Singly, char> = List::new();
assert!(list.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the list.

Examples

use orx_linked_list::*;

let mut list: List<Doubly, char> = List::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 = List::<Doubly, _>::new();

assert!(list.is_empty());

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

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

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

O(1) Returns a reference to the front of the list.

Examples

use orx_linked_list::*;

let mut list = List::<Singly, _>::new();

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

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

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

_ = list.pop_front();
assert_eq!(Some(&'a'), list.front());

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

O(1) Returns a reference to the back of the list.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

assert!(list.back().is_none());

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

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

list.push_front('c');
assert_eq!(Some(&'b'), list.back());

_ = list.pop_back();
assert_eq!(Some(&'a'), list.back());

pub fn iter(&self) -> IterForward<'_, 'a, V, T>

O(n) Returns an iterator to elements of the list from the front node to the back.

Time complexity:

• O(1) to access the front node.
• O(n) to iterate forward from the given node.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

let mut iter = list.iter();

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

pub fn iter_forward_from( &self, node_index: NodeIndex<'a, V, T> ) -> Result<IterForward<'_, 'a, V, T>, NodeIndexError>

O(n) Creates a forward iterator starting from the node with the given node_index.

Returns the corresponding NodeIndexError if the given index is invalid for this linked list.

Time complexity:

• O(1) to access the front node.
• O(n) to iterate forward from the given node.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

let b = list.push_front('b');
list.push_back('c');
list.push_front('a');
list.push_back('d'); // list: [a-b-c-d]

let mut iter = list.iter_forward_from(b);

assert!(iter.is_ok());

let mut iter = iter.unwrap();

assert_eq!(Some(&'b'), iter.next());
assert_eq!(Some(&'c'), iter.next());
assert_eq!(Some(&'d'), iter.next());
assert_eq!(None, iter.next());

pub fn clear(&mut self)

Clears the list removing all elements.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

assert_eq!(3, list.len());
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

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

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 list was empty.

Examples

use orx_linked_list::*;

let mut list: List<Doubly, _> = List::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 list was empty.

Examples

use orx_linked_list::*;

let mut list: List<Doubly, _> = List::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 pop_front(&mut self) -> Option<T>

where for<'rf> SelfRefColMut<'rf, 'a, V, T, SplitVec<Node<'a, V, T>, Recursive>>: Reclaim<V::Prev, V::Next>,

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: List<Singly, char> = List::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 get(&self, node_index: NodeIndex<'a, V, T>) -> Option<&T>

O(1) Returns a reference to the node with the given node_index in constant time.

Returns None if the index is invalid.

Safety

get(node_index) returns Some if all of of the following safety and correctness conditions hold:

• the index is created from this linked list,
• the node that this index is created for still belongs to the list`; i.e., it is not removed,
• the node positions in this list are not reorganized to reclaim memory:
  • this case is never observed if MemoryReclaimNever is used,
  • this case is observed when:
    • the memory reclaim policy is MemoryReclaimOnThreshold, and
    • the utilization of active nodes has dropped a threshold due to pop and remove operations.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

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

list.push_front('c');
list.push_back('d');
list.push_front('e');
list.push_back('f');

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

list.clear();

assert_eq!(None, list.get(a));
assert_eq!(None, list.get(b));

pub fn get_or_error( &self, node_index: NodeIndex<'a, V, T> ) -> Result<&T, NodeIndexError>

O(1) Returns a reference to the node with the given node_index in constant time.

Returns None if the index is invalid.

Safety

get(node_index) returns Some if all of of the following safety and correctness conditions hold:

• the index is created from this linked list,
• the node that this index is created for still belongs to the list`; i.e., it is not removed,
• the node positions in this list are not reorganized to reclaim memory:
  • this case is never observed if MemoryReclaimNever is used,
  • this case is observed when:
    • the memory reclaim policy is MemoryReclaimOnThreshold, and
    • the utilization of active nodes has dropped a threshold due to pop and remove operations.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

assert_eq!(Ok(&'a'), list.get_or_error(a));
assert_eq!(Ok(&'b'), list.get_or_error(b));

list.push_back('c');
list.push_back('d');
list.push_back('e');
list.push_back('f');

assert_eq!(
    vec!['a', 'b', 'c', 'd', 'e', 'f'],
    list.iter().copied().collect::<Vec<_>>()
);

assert_eq!(Ok(&'a'), list.get_or_error(a));
assert_eq!(Ok(&'b'), list.get_or_error(b));

let removed = list.remove(a);
assert_eq!(removed, Ok('a'));

assert_eq!(Err(NodeIndexError::RemovedNode), list.get_or_error(a));
assert_eq!(Ok(&'b'), list.get_or_error(b));

pub fn index_of(&self, value: &T) -> Option<NodeIndex<'a, V, T>>

where T: PartialEq,

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 NodeIndex can later be used for constant time access to the corresponding element.

Examples

use orx_linked_list::*;
use orx_selfref_col::NodeIndexError;

let mut list = List::<Doubly, _>::from_iter(['a', 'b', 'c', 'd']);

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

let b = list.index_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_forward_from(b).unwrap().copied().collect::<Vec<_>>().as_slice());
assert_eq!(&['b', 'a'], list.iter_backward_from(b).unwrap().copied().collect::<Vec<_>>().as_slice());

list.insert_prev_to(b, 'X').unwrap(); // O(1)
list.insert_next_to(b, 'Y').unwrap(); // O(1)
assert_eq!(&['a', 'X', 'b', 'Y', 'c', 'd'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove(b);  // O(1)
assert_eq!(removed, Ok('b'));
assert_eq!(&['a', 'X', 'Y', 'c', 'd'], list.iter().copied().collect::<Vec<_>>().as_slice());

assert_eq!(list.get(b), None);
assert_eq!(list.get_or_error(b).err(), Some(NodeIndexError::RemovedNode));

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

where T: PartialEq,

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 mut list = List::<Doubly, _>::from_iter(['a', 'b', 'c', 'd']);

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

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

where T: PartialEq,

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.

Note that, unlike vectors, the position of an element does not provide a constant time access to the element. In order to obtain a NodeIndex allowing O(1) access, use the index_of method; or store the node index returned when the element is added to the list for the first time by methods such as push_front or insert_next_to, etc.

Examples

use orx_linked_list::*;
use orx_selfref_col::NodeIndexError;

let mut list = List::<Doubly, _>::from_iter(['a', 'b', 'c', 'd']);

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

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

pub fn node_utilization(&self) -> f32

Returns the node utilization as a fraction of active nodes to the used nodes:

• 1.0 when there is no closed node;
• 0.0 when all used memory is used by closed nodes.

Node utilization can be brought to 100%:

• automatically by the underlying memory policy if MemoryReclaimOnThreshold is used; or
• manually by calling the reclaim_closed_nodes method.

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

Examples

use orx_linked_list::*;

fn float_eq(x: f32, y: f32) -> bool {
    (x - y).abs() < f32::EPSILON
}

// MemoryReclaimOnThreshold<2> -> memory will be reclaimed when utilization is below 75%
let mut list = List::<Doubly, _>::new();
let a = list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');
list.push_back('e');

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 5/5 = 100%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves a hole

assert!(float_eq(list.node_utilization(), 0.80)); // utilization = 4/5 = 80%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves the second hole; we have utilization = 3/5 = 60%
                        // this is below the threshold 75%, and triggers reclaim
                        // we claim the two unused nodes / holes

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 3/3 = 100%

// nodes reorganized; 'a' is no more valid
assert_eq!(
    list.get_or_error(a),
    Err(NodeIndexError::ReorganizedCollection)
);
assert_eq!(list.get(a), None);

pub fn reclaim_closed_nodes(&mut self)

where for<'rf> SelfRefColMut<'rf, 'a, V, T, SplitVec<Node<'a, V, T>, Recursive>>: Reclaim<V::Prev, V::Next>,

Manually attempts to reclaim closed nodes.

Safety

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

Examples

use orx_linked_list::*;

fn float_eq(x: f32, y: f32) -> bool {
    (x - y).abs() < f32::EPSILON
}

// MemoryReclaimNever -> memory will never be reclaimed automatically
let mut list = List::<Doubly<MemoryReclaimNever>, _>::new();
let a = list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');
list.push_back('e');

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 5/5 = 100%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves a hole
_ = list.pop_back(); // leaves the second hole
_ = list.pop_back(); // leaves the third hole

assert!(float_eq(list.node_utilization(), 0.40)); // utilization = 2/5 = 40%

// still no reorganization; 'a' is and will always be valid unless we manually reclaim
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

list.reclaim_closed_nodes();

// we can manually reclaim memory any time we want to maximize utilization
assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 2/2 = 100%

// we are still protected by list & index validation
// nodes reorganized; 'a' is no more valid, we cannot wrongly use the index
assert_eq!(
    list.get_or_error(a),
    Err(NodeIndexError::ReorganizedCollection)
);
assert_eq!(list.get(a), None);

impl<'a, T: 'a, M> List<'a, Singly<M>, T>

where M: MemoryReclaimPolicy,

pub fn push_front(&mut self, value: T) -> NodeIndex<'a, Singly<M>, T>

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

Examples

use orx_linked_list::*;

let mut list: List<Singly, char> = List::new();

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

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

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

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

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: List<Singly, char> = List::new();
list.push_front('c');
list.push_front('b');
list.push_front('a');

let mut other: List<Singly, char> = List::new();
other.push_front('e');
other.push_front('d');

list.append_front(other);
assert_eq!(&['d', 'e', 'a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

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

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: List<Singly, char> = List::new();
list.push_front('c');
list.push_front('b');
list.push_front('a');

let mut other: List<Singly, char> = List::new();
other.push_front('e');
other.push_front('d');

list.append_back(other);
assert_eq!(&['a', 'b', 'c', 'd', 'e'], list.iter().copied().collect::<Vec<_>>().as_slice());

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

O(n) Removes and returns value of the at-th element in the list; returns None if list length is less than or equal to at.

Time complexity:

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

Example

use orx_linked_list::*;

let mut list = List::<Singly, char>::new();

list.push_front('c');
list.push_front('b');
list.push_front('a');
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove_at(3);
assert!(removed.is_none());
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove_at(1);
assert_eq!(Some('b'), removed);
assert_eq!(&['a', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn insert_at(&mut self, at: usize, value: T) -> NodeIndex<'a, Singly<M>, T>

O(n) Inserts the given value at the at-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 at > self.len().

Example

use orx_linked_list::*;

let mut list = List::<Singly, char>::new();

list.push_front('c');
list.push_front('b');
list.push_front('a');
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

list.insert_at(1, 'x');
assert_eq!(&['a', 'x', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn retain<Predicate>(&mut self, predicate: &Predicate)

where Predicate: Fn(&T) -> bool,

O(n) Retains only the elements specified by the predicate.

In other words, removes all elements e for which predicate(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Time complexity:

• O(n) to iterate over all elements,
  • O(1) to remove elements failing to satisfy the predicate.

Examples

use orx_linked_list::*;

let mut list = List::<Singly, _>::from_iter([0, 1, 2, 3, 4]);

list.retain(&|x| *x % 2 == 0);

assert_eq!(&[0, 2, 4], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn retain_collect<Predicate, Collect>( &mut self, predicate: &Predicate, collect: &mut Collect )

where Predicate: Fn(&T) -> bool, Collect: FnMut(T),

O(n) Retains only the elements specified by the predicate; all elements that are removed elements are collected by the provided closure.

In other words, removes all elements e for which predicate(&e) returns false; and calls collect(e) on the removed values. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Time complexity:

• O(n) to iterate over all elements,
  • O(1) to remove elements failing to satisfy the predicate and collect.

Examples

use orx_linked_list::*;

let mut list = List::<Singly, _>::from_iter([0, 1, 2, 3, 4]);

let mut odds = vec![];
let mut collect = |x| odds.push(x);

list.retain_collect(&|x| *x % 2 == 0, &mut collect);

assert_eq!(&[0, 2, 4], list.iter().copied().collect::<Vec<_>>().as_slice());
assert_eq!(&[1, 3], odds.as_slice());

impl<'a, T: 'a, M> List<'a, Doubly<M>, T>

where M: MemoryReclaimPolicy,

pub fn index_of_from_back( &self, value: &T ) -> Option<NodeIndex<'a, Doubly<M>, T>>

where T: PartialEq,

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 NodeIndex can later be used for constant time access to the corresponding element.

Examples

use orx_linked_list::*;
use orx_selfref_col::NodeIndexError;

let mut list = List::<Doubly, _>::from_iter(['a', 'b', 'c', 'd']);

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

let b = list.index_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_forward_from(b).unwrap().copied().collect::<Vec<_>>().as_slice());
assert_eq!(&['b', 'a'], list.iter_backward_from(b).unwrap().copied().collect::<Vec<_>>().as_slice());

list.insert_prev_to(b, 'X').unwrap(); // O(1)
list.insert_next_to(b, 'Y').unwrap(); // O(1)
assert_eq!(&['a', 'X', 'b', 'Y', 'c', 'd'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove(b);  // O(1)
assert_eq!(removed, Ok('b'));
assert_eq!(&['a', 'X', 'Y', 'c', 'd'], list.iter().copied().collect::<Vec<_>>().as_slice());

assert_eq!(list.get(b), None);
assert_eq!(list.get_or_error(b).err(), Some(NodeIndexError::RemovedNode));

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

where T: PartialEq,

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 mut list = List::<Doubly, _>::from_iter(['a', 'b', 'c', 'd']);

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

pub fn iter_from_back(&self) -> IterBackward<'_, 'a, Doubly<M>, T>

O(n) Returns an iterator to elements of the list from the back node to the front.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

let mut iter = list.iter_from_back();

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

pub fn iter_backward_from( &self, node_index: NodeIndex<'a, Doubly<M>, T> ) -> Result<IterBackward<'_, 'a, Doubly<M>, T>, NodeIndexError>

O(n) Creates a backward iterator starting from the node with the given node_index.

Returns the corresponding NodeIndexError if the given index is invalid for this linked list.

Time complexity:

• O(1) to access the front node.
• O(n) to iterate forward from the given node.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

let b = list.push_front('b');
list.push_back('c');
list.push_front('a');
list.push_back('d'); // list: [a-b-c-d]

let mut iter = list.iter_backward_from(b);

assert!(iter.is_ok());

let mut iter = iter.unwrap();

assert_eq!(Some(&'b'), iter.next());
assert_eq!(Some(&'a'), iter.next());
assert_eq!(None, iter.next());

pub fn push_front(&mut self, value: T) -> NodeIndex<'a, Doubly<M>, T>

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

Examples

use orx_linked_list::*;

let mut list: List<Doubly, char> = List::new();

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

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

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

pub fn push_back(&mut self, value: T) -> NodeIndex<'a, Doubly<M>, T>

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

Examples

use orx_linked_list::*;

let mut list: List<Doubly, char> = List::new();

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

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

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

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

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: List<Doubly, char> = List::new();
list.push_front('b');
list.push_front('a');
list.push_back('c');

let mut other: List<Doubly, char> = List::new();
other.push_back('d');
other.push_back('e');

list.append_front(other);
assert_eq!(&['d', 'e', 'a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

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

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: List<Doubly, char> = List::new();
list.push_front('b');
list.push_front('a');
list.push_back('c');

let mut other: List<Doubly, char> = List::new();
other.push_back('d');
other.push_back('e');

list.append_back(other);
assert_eq!(&['a', 'b', 'c', 'd', 'e'], list.iter().copied().collect::<Vec<_>>().as_slice());

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: List<Doubly, char> = List::new();

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

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

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

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

O(n) Removes and returns value of the at-th element in the list; returns None if list length is less than or equal to at.

Time complexity:

• starts from the front or back choosing the shorter path depending on the length of the list and value of at,
• O(n) iterates until reaching the element,
• O(1) removes and returns the value.

Example

use orx_linked_list::*;

let mut list = List::<Doubly, char>::new();

list.push_front('b');
list.push_back('c');
list.push_front('a');
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove_at(3);
assert!(removed.is_none());
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

let removed = list.remove_at(1);
assert_eq!(Some('b'), removed);
assert_eq!(&['a', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn remove( &mut self, node_index: NodeIndex<'a, Doubly<M>, T> ) -> Result<T, NodeIndexError>

O(1) Removes and returns value of the element with the given node_index.

Does not change the list and returns the NodeIndexError if the node index is invalid.

Safety

Removal is carried out only if the node_index is valid. And the node index is valid if all of of the following safety and correctness conditions hold:

• the index is created from this linked list,
• the node that this index is created for still belongs to the list`; i.e., it is not removed,
• the node positions in this list are not reorganized to reclaim memory:
  • this case is never observed if MemoryReclaimNever is used,
  • this case is observed when:
    • the memory reclaim policy is MemoryReclaimOnThreshold, and
    • the utilization of active nodes has dropped a threshold due to pop and remove operations.

Examples

use orx_linked_list::*;
use orx_selfref_col::NodeIndexError;

let mut list = List::<Doubly, _>::new();

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

assert_eq!(vec!['a', 'b', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

let removed = list.remove(b);

assert_eq!(removed, Ok('b'));
assert_eq!(vec!['a', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

let not_removed = list.remove(b);
assert_eq!(not_removed.err(), Some(NodeIndexError::RemovedNode));
assert_eq!(vec!['a', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

pub fn insert_at(&mut self, at: usize, value: T) -> NodeIndex<'a, Doubly<M>, T>

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

Time complexity:

• starts from the front or back choosing the shorter path depending on the length of the list and value of at,
• O(n) iterates until reaching the element,
• O(1) inserts the value.

Panics

Panics if at > self.len().

Example

use orx_linked_list::*;

let mut list = List::<Doubly, char>::new();

list.push_back('c');
list.push_front('b');
list.push_front('a');
assert_eq!(&['a', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

list.insert_at(1, 'x');
assert_eq!(&['a', 'x', 'b', 'c'], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn insert_prev_to( &mut self, node_index: NodeIndex<'a, Doubly<M>, T>, value: T ) -> Result<NodeIndex<'a, Doubly<M>, T>, NodeIndexError>

O(1) Inserts the given value as the previous of the node with the given node_index and returns the index of the inserted node.

Does not change the list and returns the NodeIndexError if the node index is invalid.

Safety

Insertion is carried out only if the node_index is valid. And the node index is valid if all of of the following safety and correctness conditions hold:

• the index is created from this linked list,
• the node that this index is created for still belongs to the list`; i.e., it is not removed,
• the node positions in this list are not reorganized to reclaim memory:
  • this case is never observed if MemoryReclaimNever is used,
  • this case is observed when:
    • the memory reclaim policy is MemoryReclaimOnThreshold, and
    • the utilization of active nodes has dropped a threshold due to pop and remove operations.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

assert_eq!(vec!['a', 'b', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

let x = list.insert_prev_to(b, 'X').unwrap();

assert_eq!(list.get(x), Some(&'X'));
assert_eq!(vec!['a', 'X', 'b', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

pub fn insert_next_to( &mut self, node_index: NodeIndex<'a, Doubly<M>, T>, value: T ) -> Result<NodeIndex<'a, Doubly<M>, T>, NodeIndexError>

O(1) Inserts the given value as the next of the node with the given node_index and returns the index of the inserted node.

Does not change the list and returns the NodeIndexError if the node index is invalid.

Safety

Insertion is carried out only if the node_index is valid. And the node index is valid if all of of the following safety and correctness conditions hold:

• the index is created from this linked list,
• the node that this index is created for still belongs to the list`; i.e., it is not removed,
• the node positions in this list are not reorganized to reclaim memory:
  • this case is never observed if MemoryReclaimNever is used,
  • this case is observed when:
    • the memory reclaim policy is MemoryReclaimOnThreshold, and
    • the utilization of active nodes has dropped a threshold due to pop and remove operations.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::new();

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

assert_eq!(vec!['a', 'b', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

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

assert_eq!(list.get(x), Some(&'X'));
assert_eq!(vec!['a', 'b', 'X', 'c', 'd'], list.iter().copied().collect::<Vec<_>>());

pub fn retain<Predicate>(&mut self, predicate: &Predicate)

where Predicate: Fn(&T) -> bool,

O(n) Retains only the elements specified by the predicate.

In other words, removes all elements e for which predicate(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Time complexity:

• O(n) to iterate over all elements,
  • O(1) to remove elements failing to satisfy the predicate.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::from_iter([0, 1, 2, 3, 4]);

list.retain(&|x| *x % 2 == 0);

assert_eq!(&[0, 2, 4], list.iter().copied().collect::<Vec<_>>().as_slice());

pub fn retain_collect<Predicate, Collect>( &mut self, predicate: &Predicate, collect: &mut Collect )

where Predicate: Fn(&T) -> bool, Collect: FnMut(T),

O(n) Retains only the elements specified by the predicate; all elements that are removed elements are collected by the provided closure.

In other words, removes all elements e for which predicate(&e) returns false; and calls collect(e) on the removed values. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Time complexity:

• O(n) to iterate over all elements,
  • O(1) to remove elements failing to satisfy the predicate and collect.

Examples

use orx_linked_list::*;

let mut list = List::<Doubly, _>::from_iter([0, 1, 2, 3, 4]);

let mut odds = vec![];
let mut collect = |x| odds.push(x);

list.retain_collect(&|x| *x % 2 == 0, &mut collect);

assert_eq!(&[0, 2, 4], list.iter().copied().collect::<Vec<_>>().as_slice());
assert_eq!(&[1, 3], odds.as_slice());

Trait Implementations

impl<'a, V, T> Clone for List<'a, V, T>

where V: ListVariant<'a, T>, V::Ends: ListEnds<'a, V, T>, T: Clone, Self: FromIterator<T>,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, T, M> Debug for List<'a, Doubly<M>, T>

where T: Debug, M: 'a + MemoryReclaimPolicy,

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

Formats the value using the given formatter.

impl<'a, T, M> Debug for List<'a, Singly<M>, T>

where T: Debug, M: MemoryReclaimPolicy,

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

Formats the value using the given formatter.

impl<'a, V, T> Default for List<'a, V, T>

where V: ListVariant<'a, T>, V::Ends: ListEnds<'a, V, T>,

fn default() -> Self

Creates an empty list.

Examples

use orx_linked_list::*;

let list: List<Singly, char> = List::default();
assert!(list.is_empty());

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

where M: MemoryReclaimPolicy,

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

Creates a value from an iterator.

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

where M: MemoryReclaimPolicy,

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

Creates a value from an iterator.