Struct GenericList 

pub struct GenericList<T: Clone + 'static, P: PointerFamily = RcPointer, const N: usize = 256, const G: usize = 1, D: DropHandler<Self> = DefaultDropHandler>(/* private fields */);

A persistent list.

This list is suitable for either a single threaded or multi threaded environment. The list accepts the smart pointer that you would like to use as a type parameter. There are sensible type aliases for implementations that you can use:

SharedList is simply a type alias for GenericList<T, ArcPointer, 256, 1>, which is both Send + Sync Similarly, List is just a type alias for GenericList<T, RcPointer, 256, 1>. SharedVList and VList are type aliases, as well, using the same backing of GenericList, however they have a growth factor of 2 - meaning bucket sizes will grow exponentially.

It’s implemented as an unrolled linked list, which is a single linked list which stores a variable amount of elements in each node. The capacity of any individual node for now is set to to be N elements, which means that until more than N elements are cons’d onto a list, it will remain a vector under the hood. By default, N is sset to 256. There is also a growth rate, G, which describes how each successive node will grow in size. With N = 2, and G = 2, the list will look something like this:

[0, 1, 2, 3, 4, 5, 6, 7] -> [8, 9, 10, 11] -> [12, 13]

The list is also designed to leverage in place mutations whenever possible - if the number of references pointing to either a cell containing a vector or the shared vector is one, then that mutation is done in place. Otherwise, it is copy-on-write, maintaining our persistent invariant.

Performance Notes

The algorithmic complexity of an unrolled linked list matches that of a normal linked list - however in practice we have a decrease by the factor of the capacity of a node that gives us practical performance wins. For a list that is fully filled, iteration over nodes becomes O(n / N), rather than the typical O(n). If the growth rate is set to 2 (or more), over individual nodes becomes O(log(n)) - which means indexing or finding the last element is O(log(n)) as well. In addition, the unrolled linked list is able to avoid the costly cache misses that a typical linked list suffers from, seeing very realistic performance gains.

Let n be the number of elements in the list, and m is the capacity of a node. In the worst case, a node will be on average half filled. In the best case, all nodes are completely full. This means for operations that for a normal linked list may take linear time Θ(n), we get a constant factor decrease of either a factor of m or m / 2. Similarly, we will see O(log(n)) performance characteristics if the growth rate is set to be larger than 1.

Implementations

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> GenericList<T, P, N, G, D>

pub fn new() -> Self

Construct an empty list.

pub fn new_with_capacity() -> Self

Constructs an empty list with capacity N

pub fn strong_count(&self) -> usize

Get the number of strong references pointing to this list

Time: O(1)

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

Compare this list to another for pointer equality

pub fn len(&self) -> usize

Get the length of the list

Examples

let list = list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
assert_eq!(list.len(), 10);

pub fn reverse(self) -> Self

Reverses the input list and returns a new list

Examples

let list = list![1, 2, 3, 4, 5].reverse();
assert_eq!(list, list![5, 4, 3, 2, 1])

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

Get the last element of the list. Returns None if the list is empty.

Examples

let list = list![1, 2, 3, 4, 5];
assert_eq!(list.last().cloned(), Some(5));

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

Get the first element of the list. Returns None if the list is empty.

Examples

let list = list![1, 2, 3, 4, 5];
let car = list.car();
assert_eq!(car, Some(1));

let list: List<usize> = list![];
let car = list.car();
assert!(car.is_none());

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

Returns a reference to the first element of the list. Returns None if the list is empty.

Examples

let list = list![1, 2, 3, 4, 5];
let first = list.first().cloned();
assert_eq!(first, Some(1));

let list: List<usize> = list![];
let first = list.first();
assert!(first.is_none());

pub fn cdr(&self) -> Option<GenericList<T, P, N, G, D>>

Get the “rest” of the elements as a list, excluding the first element

Examples

let list = list![1, 2, 3, 4, 5];
let cdr = list.cdr().unwrap();
assert_eq!(cdr, list![2, 3, 4, 5]);

let list = list![5];
let cdr = list.cdr();
assert!(cdr.is_none());

pub fn rest(&self) -> Option<GenericList<T, P, N, G, D>>

Get the “rest” of the elements as a list. Alias for cdr

pub fn cdr_mut(&mut self) -> Option<&mut Self>

Gets the cdr of the list, mutably. Returns None if the next is empty - otherwise updates self to be the rest

Examples

let mut list = list![1, 2, 3, 4, 5];
list.cdr_mut().expect("This list has a tail");
assert_eq!(list, list![2, 3, 4, 5]);


let mut list = list![1, 2, 3];
assert!(list.cdr_mut().is_some());
assert_eq!(list, list![2, 3]);
assert!(list.cdr_mut().is_some());
assert_eq!(list, list![3]);
assert!(list.cdr_mut().is_none());
assert_eq!(list, list![]);

pub fn rest_mut(&mut self) -> Option<&mut Self>

Gets the rest of the list, mutably. Alias for cdr_mut

pub fn cons( value: T, other: GenericList<T, P, N, G, D>, ) -> GenericList<T, P, N, G, D>

Pushes an element onto the front of the list, returning a new list

Examples

let list = List::cons(1, List::cons(2, List::cons(3, List::cons(4, List::new()))));
assert_eq!(list, list![1, 2, 3, 4]);

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

Mutably pushes an element onto the front of the list, in place

Examples

let mut list = list![];
list.cons_mut(3);
list.cons_mut(2);
list.cons_mut(1);
list.cons_mut(0);
assert_eq!(list, list![0, 1, 2, 3])

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

Alias for cons_mut

Examples

let mut list = list![];
list.push_front(3);
list.push_front(2);
list.push_front(1);
list.push_front(0);
assert_eq!(list, list![0, 1, 2, 3])

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

Mutably pop the first value off of the list

Examples

let mut list = list![1, 2, 3];
assert_eq!(list.pop_front().unwrap(), 1);
assert_eq!(list.pop_front().unwrap(), 2);
assert_eq!(list.pop_front().unwrap(), 3);
assert!(list.pop_front().is_none())

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

Push one value to the back of the list

Time: O(n)

Examples

let mut list = list![];
list.push_back(0);
list.push_back(1);
list.push_back(2);
list.push_back(3);
assert_eq!(list, list![0, 1, 2, 3])

pub fn take(&self, count: usize) -> Self

Construct a new list from the first count elements from the current list

Examples

let list = list![0, 1, 2, 3, 4, 5];
let new_list = list.take(3);
assert_eq!(new_list, list![0, 1, 2]);

pub fn tail(&self, len: usize) -> Option<Self>

Returns the list after the first len elements of lst. If the list has fewer then len elements, then this returns None.

Examples

let list = list![0, 1, 2, 3, 4, 5];
let new_list = list.tail(2);
assert_eq!(new_list.unwrap(), list![2, 3, 4, 5]);

let no_list = list.tail(100);
assert!(no_list.is_none())

pub fn iter(&self) -> impl Iterator<Item = &T>

Constructs an iterator over the list

pub fn get(&self, index: usize) -> Option<&T>

Get a reference to the value at index index in a list. Returns None if the index is out of bounds.

pub fn append(self, other: Self) -> Self

Append the list other to the end of the current list. Returns a new list.

Examples

let left = list![1usize, 2, 3];
let right = list![4usize, 5, 6];
assert_eq!(left.append(right), list![1, 2, 3, 4, 5, 6])

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

Append the list ‘other’ to the end of the current list in place.

Examples

let mut left = list![1usize, 2, 3];
let right = list![4usize, 5, 6];
left.append_mut(right);
assert_eq!(left, list![1, 2, 3, 4, 5, 6])

pub fn is_empty(&self) -> bool

Checks whether a list is empty

Examples

let mut list = List::new();
assert!(list.is_empty());
list.cons_mut("applesauce");
assert!(!list.is_empty());

pub fn sort(&mut self)

where T: Ord,

Sorts the list

Examples

let mut list = list![4, 2, 6, 3, 1, 5];
list.sort();
assert_eq!(list, list![1, 2, 3, 4, 5, 6]);

pub fn sort_by<F>(&mut self, cmp: F)

where F: Fn(&T, &T) -> Ordering,

Sorts the list according to the ordering

Examples

let mut list = list![4, 2, 6, 3, 1, 5];
list.sort_by(Ord::cmp);
assert_eq!(list, list![1, 2, 3, 4, 5, 6]);

Trait Implementations

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<GenericList<T, P, N, G, D>>> Add for &GenericList<T, P, N, G, D>

fn add(self, other: Self) -> Self::Output

Concatenate two lists

type Output = GenericList<T, P, N, G, D>

The resulting type after applying the + operator.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Add for GenericList<T, P, N, G, D>

fn add(self, other: Self) -> Self::Output

Concatenate two lists

type Output = GenericList<T, P, N, G, D>

The resulting type after applying the + operator.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Clone for GenericList<T, P, N, G, D>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Clone + Debug, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Debug for GenericList<T, P, N, G, D>

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

Formats the value using the given formatter.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Default for GenericList<T, P, N, G, D>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Drop for GenericList<T, P, N, G, D>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Extend<T> for GenericList<T, P, N, G, D>

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<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> From<&[T]> for GenericList<T, P, N, G, D>

fn from(vec: &[T]) -> Self

Converts to this type from the input type.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> From<Vec<T>> for GenericList<T, P, N, G, D>

fn from(vec: Vec<T>) -> Self

Converts to this type from the input type.

impl<'a, T: 'a + Clone, P: 'a + PointerFamily, const N: usize, const G: usize, D: 'a + DropHandler<Self>> FromIterator<&'a GenericList<T, P, N, G, D>> for GenericList<T, P, N, G, D>

fn from_iter<I: IntoIterator<Item = &'a GenericList<T, P, N, G, D>>>( iter: I, ) -> Self

Creates a value from an iterator.

impl<'a, T: 'a + Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> FromIterator<&'a T> for GenericList<T, P, N, G, D>

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

Creates a value from an iterator.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> FromIterator<GenericList<T, P, N, G, D>> for GenericList<T, P, N, G, D>

fn from_iter<I: IntoIterator<Item = GenericList<T, P, N, G, D>>>( iter: I, ) -> Self

Creates a value from an iterator.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> FromIterator<T> for GenericList<T, P, N, G, D>

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

Creates a value from an iterator.

impl<T: Clone + Hash, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Hash for GenericList<T, P, N, G, D>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Index<usize> for GenericList<T, P, N, G, D>

fn index(&self, index: usize) -> &Self::Output

Get a reference to the value at index index in the vector.

Time: O(log n)

type Output = T

The returned type after indexing.

impl<'a, T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<GenericList<T, P, N, G, D>>> IntoIterator for &'a GenericList<T, P, N, G, D>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, P, N, G, D>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> IntoIterator for GenericList<T, P, N, G, D>

type Item = T

The type of the elements being iterated over.

type IntoIter = ConsumingIter<T, P, N, G, D>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Clone + Ord, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Ord for GenericList<T, P, N, G, D>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T: Clone + PartialEq, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> PartialEq for GenericList<T, P, N, G, D>

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: Clone + PartialOrd, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> PartialOrd for GenericList<T, P, N, G, D>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Sum for GenericList<T, P, N, G, D>

fn sum<I>(it: I) -> Self

where I: Iterator<Item = Self>,

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<T: Clone + Eq, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Eq for GenericList<T, P, N, G, D>