Struct orx_linked_list::LinkedListX

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

LinkedListX is a structurally immutable LinkedList. In other words, it is a linked list which is done building:

• no insertions or removals are allowed from the list,
• the list cannot be cleared.

On the other hand, having a mut reference, the data of the elements can still be mutated.

Note that it is possible to convert a LinkedList to a LinkedListX using built(self) and vice versa by continue_building(self) methods. Both methods are consuming and the conversions are cheap (equivalent to adding/removing a RefCell indirection).

Another major difference is between the implementation of Send and Sync traits:

type / trait	Send	Sync
LinkedList	+	-
LinkedListX	+	+

Examples

Example below demonstrates how to switch between LinkedList and LinkedListX to designate whether structural mutations are allowed or not.

use orx_linked_list::prelude::*;

#[derive(Debug, PartialEq)]
struct Wizard {
    name: String,
    level: u32,
}
impl Wizard {
    fn new<S: Into<String>>(name: S, level: u32) -> Self {
        Self {
            name: name.into(),
            level,
        }
    }
    fn cast_spell(&self) {}
}

// build the structure: both the structure and elements are mutable
let mut list: LinkedList<'_, Wizard> = LinkedList::new();
list.push_back(Wizard::new("Gandalf", 99));
list.push_front(Wizard::new("Sauron", 72));
list.push_back(Wizard::new("Palpatine", 71));
list.push_front(Wizard::new("Dumbledore", 86));
assert_eq!(
    vec!["Dumbledore", "Sauron", "Gandalf", "Palpatine"],
    list.iter().map(|w| &w.name).collect::<Vec<_>>()
);

// absolute immutable
let list: LinkedListX<'_, Wizard> = list.built();
for w in list.iter() {
    w.cast_spell();
}

// back to structural mutations
let mut list: LinkedList<'_, Wizard> = list.continue_building();
let dumbledore = list.pop_front();
assert_eq!(dumbledore, Some(Wizard::new("Dumbledore", 86)));
list.push_back(Wizard::new("Merlin", 94));
assert_eq!(
    vec!["Sauron", "Gandalf", "Palpatine", "Merlin"],
    list.iter().map(|w| &w.name).collect::<Vec<_>>()
);

// stop structural mutations; however keep elements mutable
let mut list: LinkedListX<'_, Wizard> = list.built();
list.get_mut_at(1).unwrap().level += 1;
assert_eq!(list.get_at(1), Some(&Wizard::new("Gandalf", 100)));

// back to structural mutations
let mut list = list.continue_building();
let gandalf = list.remove_at(1);
assert_eq!(gandalf, Wizard::new("Gandalf", 100));

// freeze again
let list = list.built();

On structural immutablility

Together with the choice between immutable or mut variable, LinkedList and LinkedListX` address the fact that im|mutability of collections is more than a boolean choice.

See the complete possibilities here:

type	element mutability	structural mutability	useful when/as
LinkedList	-	-	not really, see Immutable LinkedList vs Immutable LinkedListX
mut LinkedList	+	+	while building the linked list
LinkedListX	-	-	as an absolute immutable built linked list
mut LinkedListX	+	-	as a structurally immutable built linked list; while values of nodes can be mutated but relations cannot be

Immutable LinkedList vs Immutable LinkedListX

As you may see an immutable LinkedList is not very useful.

use orx_linked_list::prelude::*;

let list = LinkedList::<'_, char>::new();

There is nothing to do with this list, it is and will be an empty list.

The situation is common. For instance, when we cannot convenitently collect, we create a mut std::vec::Vec, build it up and move it to an immutable variable to make sure that the built vector will not be mutated.

Linked list is a self referencing data structure which is much harder to collect. In other words, building will probably require a mut reference. Therefore, this approach seems to fit and can be used in the same manner as in the example below.

use orx_linked_list::prelude::*;

let mut list = LinkedList::new();
list.push_back('a');
let list: LinkedList<_> = list; // building is complete, no undesired mutation is allowed

However, to be able to build the inter-element relations via thin references, LinkedList makes use of ImpVec. ImpVec wraps a PinnedVec giving it the ability to define such relations with cheap thin references. It achieves this with one additional level of indirection which wraps the PinnedVec that actually holds the data.

If the structural mutation is completed, we do not need and will not use the ability to build inter-element references. Therefore, we can get rid of the additional indirection and achieve the access performance of PinnedVec.

The transformation is convenient and cheap, and bidirectional.

Therefore, the usage below would be preferable than the example above:

use orx_linked_list::prelude::*;

let mut list = LinkedList::new();
list.push_back('a');
let list: LinkedListX<_> = list.built(); // building is complete, no undesired mutation is allowed

Implementations

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

pub fn collect_vec(&self) -> Vec<T>

Clones and collects values in the linked list into a standard vector.

self.collect_vec() is simply a shorthand for self.iter().cloned().collect().

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

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

Provides a forward iterator; which starts from the front-most element to the back.

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 list = list.built();
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);

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

Provides a backward iterator; which starts from the back-most element to the front.

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 list = list.built();
let mut iter = list.iter_from_back();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

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

pub fn continue_building(self) -> LinkedList<'a, T, P>

Converts the LinkedListX back to a LinkedList allowing for structural mutability.

See the documentation of LinkedListX for details.

The LinkedList is created with MemoryUtilization::default(), which can be updated with with_memory_utilization method if needed.

pub fn len(&self) -> usize

Returns the length of the linked list.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::new();
assert_eq!(0, list.len());

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

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

let list = list.built();
assert_eq!(1, 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::new();
assert!(list.is_empty());

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

let list = list.built();
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);
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));

let list = list.built();
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);
assert_eq!(list.back(), None);

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

let mut list = list.built();
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);
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));

let list = list.built();
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);
assert_eq!(list.front(), None);

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

let mut list = list.built();
assert_eq!(list.front(), Some(&42));

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

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

Returns a reference to element at the at position starting from the front; None when at is out of bounds.

This operation requires O(n) time.

Examples

use orx_linked_list::prelude::*;

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

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

let list = list.built();

assert_eq!(Some(&'a'), list.get_at(0));
assert_eq!(Some(&'b'), list.get_at(1));
assert_eq!(Some(&'c'), list.get_at(2));
assert_eq!(None, list.get_at(3));

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

Returns a mutable reference to element at the at position starting from the front; None when at is out of bounds.

This operation requires O(n) time.

Examples

use orx_linked_list::prelude::*;

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

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

let mut list = list.built();

*list.get_mut_at(0).unwrap() = 'x';
*list.get_mut_at(1).unwrap() = 'y';
*list.get_mut_at(2).unwrap() = 'z';
assert_eq!(None, list.get_mut_at(3));

assert_eq!(Some(&'x'), list.get_at(0));
assert_eq!(Some(&'y'), list.get_at(1));
assert_eq!(Some(&'z'), list.get_at(2));

Trait Implementations

impl<'a, T, P> Clone for LinkedListX<'a, T, P>where T: 'a + Clone, P: PinnedVec<LinkedListNode<'a, T>> + 'a,

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, P> Debug for LinkedListX<'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, P> Default for LinkedListX<'a, T, P>where T: 'a + Default, P: PinnedVec<LinkedListNode<'a, T>> + 'a + Default,

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

Returns the “default value” for a type.

impl<'a, T, P> PartialEq<[T]> for LinkedListX<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &[T]) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P, const N: usize> PartialEq<[T; N]> for LinkedListX<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &[T; N]) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P> PartialEq<FixedVec<T>> for LinkedListX<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &FixedVec<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

fn eq(&self, other: &LinkedList<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P> PartialEq<LinkedListX<'a, T, P>> for [T]where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P, const N: usize> PartialEq<LinkedListX<'a, T, P>> for [T; N]where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P> PartialEq<LinkedListX<'a, T, P>> for FixedVec<T>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P, G> PartialEq<LinkedListX<'a, T, P>> for SplitVec<T, G>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq, G: Growth,

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P> PartialEq<LinkedListX<'a, T, P>> for Vec<T>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &LinkedListX<'a, T, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P, G> PartialEq<SplitVec<T, G>> for LinkedListX<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq, G: Growth,

fn eq(&self, other: &SplitVec<T, G>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T, P> PartialEq<Vec<T, Global>> for LinkedListX<'a, T, P>where P: PinnedVec<LinkedListNode<'a, T>> + 'a, T: PartialEq,

fn eq(&self, other: &Vec<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.