Struct orx_linked_list::LinkedList

pub struct LinkedList<'a, T, P = SplitVec<LinkedListNode<'a, T>>>where
    P: PinnedVec<LinkedListNode<'a, T>>,{
    pub memory_utilization: MemoryUtilization,
    /* private fields */
}

The LinkedList allows pushing and popping elements at either end in constant time.

Fields

memory_utilization: MemoryUtilization

Memory utilization strategy of the linked list allowing control over the tradeoff between memory efficiency and amortized time complexity of pop_back, pop_front or remove operations.

See MemoryUtilization for details.

Implementations

impl<'a, T, P> LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

pub fn contains(&'a self, x: &T) -> bool

Returns true if the LinkedList contains an element equal to the given value.

This operation should compute linearly in O(n) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_doubling_growth(8);
list.push_back(0);
list.push_back(1);
list.push_back(2);

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

impl<'a, T, P> LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: 'a,

pub fn iter<'b>(&self) -> Iter<'b, T>where 'a: 'b,

Provides a forward iterator.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(4);

list.push_back(1);
list.push_back(2);
list.push_front(0);
list.push_back(3);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

impl<'a, T, P> LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a,

pub fn len(&self) -> usize

Returns the length of the LinkedList.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());
assert_eq!(0, list.len());

list.push_front('a');
list.push_front('b');
assert_eq!(2, list.len());

_ = list.pop_back();
assert_eq!(1, list.len());

_ = list.pop_front();
assert_eq!(0, list.len());

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());
assert!(list.is_empty());

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

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

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

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

Provides a reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_doubling_growth(4, Default::default());
assert_eq!(list.back(), None);

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

list.push_front(1);
assert_eq!(list.back(), Some(&42));

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

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

Provides a mutable reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(16, Default::default());
assert_eq!(list.back(), None);

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

match list.back_mut() {
    None => {},
    Some(x) => *x = 7,
}
assert_eq!(list.back(), Some(&7));

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

Provides a reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_doubling_growth(4, Default::default());
assert_eq!(list.front(), None);

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

list.push_back(1);
assert_eq!(list.front(), Some(&42));

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

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

Provides a mutable reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(16, Default::default());
assert_eq!(list.front(), None);

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

match list.front_mut() {
    None => {},
    Some(x) => *x = 7,
}
assert_eq!(list.front(), Some(&7));

pub fn push_back(&mut self, value: T)

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());

list.push_back('a');
assert_eq!('a', *list.back().unwrap());

list.push_back('b');
assert_eq!('b', *list.back().unwrap());

list.push_front('x');
assert_eq!('b', *list.back().unwrap());

pub fn push_front(&mut self, value: T)

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());

list.push_front('a');
assert_eq!('a', *list.front().unwrap());

list.push_front('b');
assert_eq!('b', *list.front().unwrap());

list.push_back('x');
assert_eq!('b', *list.front().unwrap());

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

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());

// build linked list: x <-> a <-> b <-> c
list.push_back('a');
list.push_back('b');
list.push_front('x');
list.push_back('c');

assert_eq!(Some('c'), list.pop_back());
assert_eq!(Some('b'), list.pop_back());
assert_eq!(Some('a'), list.pop_back());
assert_eq!(Some('x'), list.pop_back());
assert_eq!(None, list.pop_back());
assert_eq!(None, list.pop_front());

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

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());

// build linked list: c <-> b <-> a <-> x
list.push_front('a');
list.push_front('b');
list.push_back('x');
list.push_front('c');

assert_eq!(Some('c'), list.pop_front());
assert_eq!(Some('b'), list.pop_front());
assert_eq!(Some('a'), list.pop_front());
assert_eq!(Some('x'), list.pop_front());
assert_eq!(None, list.pop_front());
assert_eq!(None, list.pop_back());

pub fn clear(&mut self)

Removes all elements from the LinkedList.

This operation should compute in O(n) time.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, Default::default());

// build linked list: x <-> a <-> b <-> c
list.push_front('a');
list.push_front('b');
list.push_back('x');
list.push_front('c');

assert_eq!(4, list.len());
assert_eq!(Some(&'c'), list.front());
assert_eq!(Some(&'x'), list.back());

list.clear();

assert!(list.is_empty());
assert_eq!(None, list.front());
assert_eq!(None, list.back());

pub fn remove(&mut self, at: usize) -> T

Removes the element at the given index and returns it.

This operation should compute in O(n) time to access the at-th element and constant time to remove.

Panics

Panics if at >= len

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(8, Default::default());

// build linked list: x <-> a <-> b <-> c
list.push_back('a');
list.push_back('b');
list.push_front('x');
list.push_back('c');

assert_eq!(list.remove(1), 'a');
assert_eq!(list.remove(0), 'x');
assert_eq!(list.remove(1), 'c');
assert_eq!(list.remove(0), 'b');

impl<'a, T, P> LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: 'a,

pub fn memory_status(&self) -> MemoryStatus

Returns the utilization of the underlying vector of the linked list.

LinkedList holds all elements close to each other in a PinnedVec aiming for better cache locality while using thin references rather than wide pointers and to reduce heap allocations.

In order to achieve O(1) time complexity while avoiding smart pointers, remove and pop operations are able to be Lazy. In this case; i.e., when the strategy is set to MemoryReclaimStrategy::Lazy: every pop_back, pop_front or remove method call leaves a gap in the underlying vector. Status of utilization of the underlying vector can be queried using the memory_status method and the gaps can completely be reclaimed by manually calling the memory_reclaim method which has a time complexity of O(n) where n is the length of the underlying vector.

This method reveals the memory utilization of the underlying pinned vector at any given time as the fraction of active linked list nodes to total spaces used by the pinned vector.

Some extreme examples are as follows:

• in an push-only situation, memory utilization is equal to 1.0:
  • num_active_nodes == num_used_nodes
• in a situation where each push is followed by a pop, memory utilization is 0.0:
  • num_active_nodes == 0
  • num_used_nodes == n, where n is the number of items pushed.

Complexity

LinkedList gives the control over laziness to user:

• the list can remain lazy throughout the lifetime until it is dropped, or
• at certain points in its lifetime, memory which is not utilized can be reclaimed by the memory_reclaim method.

memory_reclaim shrinks the used memory by placing all linked list elements next to each other in the underlying pinned vector without leaving any gaps. This is achieved by a single pass; hence, the method has O(n) time complexity.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, MemoryUtilization::Lazy);

// fill list with 4 elements
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

let util = list.memory_status();
assert_eq!(4, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// remove 1 of 4
_ = list.remove(2);
let util = list.memory_status();
assert_eq!(3, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.75, util.utilization());

// pop 2 more
_ = list.pop_back();
_ = list.pop_front();
let util = list.memory_status();
assert_eq!(1, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.25, util.utilization());

// remove the last element
_ = list.remove(0);
let util = list.memory_status();
assert_eq!(0, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.00, util.utilization());

pub fn memory_reclaim(&mut self) -> usize

This method reclaims the gaps which are opened due to lazy pops and removals, and brings back memory_status to 100% in O(n) time complexity.

use orx_linked_list::prelude::*;

let mut list = LinkedList::default();
list.memory_utilization = MemoryUtilization::Lazy;

// ...
// regardless of the sequence of pushes, pops, removals
// memory utilization will be 100% after memory_reclaim call.
let _reclaimed = list.memory_reclaim();
assert_eq!(1.00, list.memory_status().utilization());

LinkedList holds all elements close to each other in a PinnedVec aiming for better cache locality while using thin references rather than wide pointers and to reduce heap allocations.

In order to achieve O(1) time complexity while avoiding smart pointers, remove and pop operations are able to be Lazy. In this case; i.e., when the strategy is set to MemoryReclaimStrategy::Lazy: every pop_back, pop_front or remove method call leaves a gap in the underlying vector. Status of utilization of the underlying vector can be queried using the memory_status method and the gaps can completely be reclaimed by manually calling the memory_reclaim method which has a time complexity of O(n) where n is the length of the underlying vector.

In addition to the automatic memory utilization strategy, memory can be manually reclaimed by using this method. The memory_status method helps here by revealing the memory utilization at any given time as the fraction of active linked list nodes to total spaces used by the pinned vector.

Some extreme examples are as follows:

• in an push-only situation, memory utilization is equal to 1.0:
  • num_active_nodes == num_used_nodes
• in a situation where each push is followed by a pop, memory utilization is 0.0:
  • num_active_nodes == 0
  • num_used_nodes == n, where n is the number of items pushed.

Complexity

LinkedList gives the control over laziness to user:

• the list can remain lazy throughout the lifetime until it is dropped, or
• at certain points in its lifetime, memory which is not utilized can be reclaimed by the memory_reclaim method having O(n) time complexity.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(2, 1.5, MemoryUtilization::Lazy);

// build list: c <-> b <-> a <-> d
list.push_back('a');
list.push_front('b');
list.push_front('c');
list.push_back('d');

assert_eq!(
    list.iter().cloned().collect::<Vec<_>>(),
    ['c', 'b', 'a', 'd'],
);
assert_eq!(1.00, list.memory_status().utilization());

// nothing to reclaim
let reclaimed = list.memory_reclaim();
assert_eq!(0, reclaimed);

let popped = list.pop_back();
assert_eq!(Some('d'), popped);
assert_eq!(list.iter().cloned().collect::<Vec<_>>(), ['c', 'b', 'a']);
assert_eq!(0.75, list.memory_status().utilization());

// one position to reclaim
let reclaimed = list.memory_reclaim();
assert_eq!(1, reclaimed);
assert_eq!(list.iter().cloned().collect::<Vec<_>>(), ['c', 'b', 'a']);
assert_eq!(1.00, list.memory_status().utilization());

let removed = list.remove(1);
assert_eq!('b', removed);
let popped = list.pop_front();
assert_eq!(Some('c'), popped);
assert_eq!(list.iter().cloned().collect::<Vec<_>>(), ['a']);
assert_eq!(1.0 / 3.0, list.memory_status().utilization());

// two positions to reclaim
let reclaimed = list.memory_reclaim();
assert_eq!(2, reclaimed);
assert_eq!(list.iter().cloned().collect::<Vec<_>>(), ['a']);
assert_eq!(1.00, list.memory_status().utilization());

// pushing more using reclaimed capacity under the hood
list.push_back('x');
list.push_back('y');
list.push_back('z');
assert_eq!(1.00, list.memory_status().utilization());

// as one could expect, `clear` does not leave gaps
list.clear();
assert!(list.is_empty());
assert_eq!(1.00, list.memory_status().utilization());

impl<'a, T> LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, DoublingGrowth>>

pub fn with_doubling_growth( first_fragment_capacity: usize, memory_utilization: MemoryUtilization ) -> Self

Creates an empty LinkedList where new allocations are doubled every time the vector reaches its capacity.

• first_fragment_capacity determines the capacity of the first fragment of the underlying split vector.
• memory_utilization defines the memory utilization strategy of the linked list, see MemoryUtilization for details.

The ImpVec of the linked list allowing to build internal links uses a SplitVec: PinnedVec with DoublingGrowth growth strategy. See SplitVec for details.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_doubling_growth(4, MemoryUtilization::Lazy);

for i in 0..8 {
    list.push_back(i);
}
assert_eq!(8, list.len());

impl<'a, T> LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, LinearGrowth>>

pub fn with_linear_growth( constant_fragment_capacity: usize, memory_utilization: MemoryUtilization ) -> Self

Creates an empty LinkedList where new allocations are always the same and equal to the initial capacity of the vector.

• constant_fragment_capacity determines the capacity of the first fragment and every succeeding fragment of the underlying split vector.
• memory_utilization defines the memory utilization strategy of the linked list, see MemoryUtilization for details.

The ImpVec of the linked list allowing to build internal links uses a SplitVec: PinnedVec with LinearGrowth growth strategy. See SplitVec for details.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(5, MemoryUtilization::Eager);

for i in 0..8 {
    list.push_back(i);
}
assert_eq!(8, list.len());

impl<'a, T> LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, ExponentialGrowth>>

pub fn with_exponential_growth( first_fragment_capacity: usize, growth_coefficient: f32, memory_utilization: MemoryUtilization ) -> Self

Creates an empty LinkedList where new allocations are exponentially increased every time the vector reaches its capacity.

• first_fragment_capacity determines the capacity of the first fragment of the underlying split vector.
• growth_coefficient determines the exponential growth rate of the succeeding fragments of the split vector.
• memory_utilization defines the memory utilization strategy of the linked list, see MemoryUtilization for details.

The ImpVec of the linked list allowing to build internal links uses a SplitVec: PinnedVec with ExponentialGrowth growth strategy. See SplitVec for details.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_exponential_growth(4, 1.5, MemoryUtilization::default());

for i in 0..8 {
    list.push_back(i);
}
assert_eq!(8, list.len());

impl<'a, T> LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, CustomGrowth<LinkedListNode<'a, T>>>>

pub fn with_custom_growth_function( get_capacity_of_new_fragment: Rc<dyn Fn(&[Fragment<LinkedListNode<'a, T>>]) -> usize>, memory_utilization: MemoryUtilization ) -> Self

Creates an empty LinkedList where new allocations are determined explicitly by the passed in function.

• get_capacity_of_new_fragment determines the capacity of succeeding fragments as a function of already created and filled fragments.
• memory_utilization defines the memory utilization strategy of the linked list, see MemoryUtilization for details.

The ImpVec of the linked list allowing to build internal links uses a SplitVec: PinnedVec with CustomGrowth growth strategy. See SplitVec for details.

Examples

use orx_linked_list::prelude::*;
use std::rc::Rc;

let mut list =
    LinkedList::with_custom_growth_function(Rc::new(|fragments: &[Fragment<_>]| {
        if fragments.len() % 2 == 0 {
            2
        } else {
            8
        }
    }), MemoryUtilization::WithThreshold(0.25));

for i in 0..8 {
    list.push_back(i);
}
assert_eq!(8, list.len());

Trait Implementations

impl<'a, T, P> Debug for LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: Debug,

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

Formats the value using the given formatter.

impl<'a, T: Default, P> Default for LinkedList<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + Default,

fn default() -> LinkedList<'a, T, P>

Returns the “default value” for a type.