Struct List

Source

pub struct List<E> { /* private fields */ }

Expand description

A singly-linked persistent thread safe list.

Implementations§

Source §

impl<E: Clone> List<E>

Source

pub fn new() -> Self

Creates an empty List.

§Examples

use persistent_list::List;

let list: List<u32> = List::new();

Source

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

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(self.len()) time and O(self.len())* memory. The memory usage depends on how much of the self List is shared. Nodes are taken using clone-on-write mechanics, only cloning any shared tail part.

§Examples

use persistent_list::List;

let mut list1 = List::new();
list1.push_front('a');

let mut list2 = List::new();
list2.push_front('c');
list2.push_front('b');

list1.append(&mut list2);

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

assert!(list2.is_empty());

Source

pub fn iter(&self) -> Iter<'_, E> ⓘ

Provides a forward iterator.

§Examples

use persistent_list::List;

let mut list: List<u32> = List::new();

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

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(), None);

Source

pub fn iter_mut(&mut self) -> IterMut<'_, E> ⓘ

Provides a forward iterator with mutable references.

§Examples

use persistent_list::List;

let mut list: List<u32> = List::new();

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

for element in list.iter_mut() {
    *element += 10;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&11));
assert_eq!(iter.next(), Some(&12));
assert_eq!(iter.next(), None);

Source

pub fn is_empty(&self) -> bool

Returns true if the List is empty.

This operation should compute in O(1) time.

§Examples

use persistent_list::List;

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

list.push_front("foo");
assert!(!list.is_empty());

Source

pub fn len(&self) -> usize

Returns the length of the List.

This operation should compute in O(1) time.

§Examples

use persistent_list::List;

let mut list = List::new();

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

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

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

Source

pub fn unit(first: E) -> Self

Construct a List with a single value.

§Examples

use persistent_list::List;

let list = List::unit(1);
assert_eq!(1, list.len());
assert_eq!(
  list.front(),
  Some(&1)
);

Source

pub fn clear(&mut self)

Removes all elements from the List.

This operation should compute in O(n) time.

§Examples

use persistent_list::List;

let mut list = List::new();

list.push_front(2);
list.push_front(1);
assert_eq!(list.len(), 2);
assert_eq!(list.front(), Some(&1));

list.clear();
assert_eq!(list.len(), 0);
assert_eq!(list.front(), None);

Source

pub fn cons(&self, first: E) -> Self

Construct a List with a new element at the front of the current List.

See crate::cons for alternative version.

Source

pub fn uncons(&self) -> Option<(&E, Self)>

Get the head and the tail of a list.

This function performs both the head function and the tail function in one go, returning a tuple of the head and the tail, or None if the list is empty.

§Examples

This can be useful when pattern matching your way through a list:

use persistent_list::{List, cons};
use std::fmt::Debug;

fn walk_through_list<E: Clone>(list: &List<E>) where E: Debug {
    match list.uncons() {
        None => (),
        Some((ref head, ref tail)) => {
            print!("{:?}", head);
            walk_through_list(tail)
        }
    }
}

Source

pub fn contains(&self, x: &E) -> bool
where E: PartialEq<E>,

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

§Examples

use persistent_list::List;

let mut list: List<u32> = List::new();

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

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

Source

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

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

§Examples

use persistent_list::List;

let mut list = List::new();
assert_eq!(list.front(), None);

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

Source

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

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

§Examples

use persistent_list::List;

let mut list = List::new();
assert_eq!(list.front(), None);

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

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

Source

pub fn push_front(&mut self, element: E)

Adds an element first in the list.

This operation should compute in O(1) time.

§Examples

use persistent_list::List;

let mut list = List::new();

list.push_front(2);
assert_eq!(list.front().unwrap(), &2);

list.push_front(1);
assert_eq!(list.front().unwrap(), &1);

Source

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

Removes the first element and returns it, or None if the list is empty.

This operation should compute in O(1) time.

§Examples

use persistent_list::List;

let mut list = List::new();
assert_eq!(list.pop_front(), None);

list.push_front(1);
list.push_front(3);
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);

Source

pub fn split_off(&mut self, at: usize) -> Self

Splits the list into two at the given index. Returns everything after the given index, including the index.

This operation should compute in O(at) time.

§Panics

Panics if at > len.

§Examples

use persistent_list::List;

let mut list = List::new();

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

let mut splitted = list.split_off(2);

assert_eq!(splitted.pop_front(), Some(1));
assert_eq!(splitted.pop_front(), None);

assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.pop_front(), None);

Source

pub fn split_at(self, at: usize) -> (Self, Self)

Split a List at a given index.

Split a List at a given index, consuming the List and returning a pair of the left hand side and the right hand side of the split.

This operation should compute in O(at) time.

§Panics

Panics if at > len.

§Examples

let mut list = list![1, 2, 3, 7, 8, 9];
let (left, right) = list.split_at(3);
assert_eq!(list![1, 2, 3], left);
assert_eq!(list![7, 8, 9], right);

Source

pub fn reverse(&mut self)

Reverses the list

This operation should compute in O(n) time and O(n)* memory allocations, O(1) if this list does not share any node (tail) with another list.

The memory usage depends on how much of the self List is shared. Nodes are taken using clone-on-write mechanics, only cloning any shared tail part.

§Examples

use persistent_list::List;

let mut list1 = List::from(vec![1, 2, 3, 4]);
list1.reverse();
assert_eq!(list1, List::from(vec![4, 3, 2, 1]));

let list2 = list1.clone();
list1.reverse();
assert_eq!(list2, List::from(vec![4, 3, 2, 1]));

list1.reverse();
assert_eq!(list1, list2);

Source

pub fn rest(&self) -> Self

Get the rest of the List after any potential front element has been removed.

§Examples

use persistent_list::List;

let mut list = List::new();
assert_eq!(list.rest(), List::new());

list.push_front(2);
assert_eq!(list.rest(), List::new());

list.push_front(1);
assert_eq!(list.rest(), List::unit(2));

Source

pub fn head(&self) -> Option<&E>

Get the first element of a List.

If the List is empty, None is returned.

This is an alias for the front method.

Source

pub fn tail(&self) -> Option<Self>

Get the tail of a List.

The tail means all elements in the List after the first item. If the list only has one element, the result is an empty list. If the list is empty, the result is None.

§Examples

use persistent_list::List;

let mut list = List::new();
assert_eq!(list.tail(), None);

list.push_front(2);
assert_eq!(list.tail(), Some(List::new()));

list.push_front(1);
assert_eq!(list.tail(), Some(List::unit(2)));