Struct persistent_list::List

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

A singly-linked persistent thread safe list.

Implementations

impl<E: Clone> List<E>

pub fn new() -> Self

Creates an empty List.

Examples

use persistent_list::List;

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

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

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);

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);

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

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);

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)
);

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);

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.

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)
        }
    }
}

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);

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));

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));

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);

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);

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);

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);

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);

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));

#[must_use]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.

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)));

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

Trait Implementations

impl<E: Clone> Clone for List<E>

fn clone(&self) -> List<E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E: Debug + Clone> Debug for List<E>

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

Formats the value using the given formatter.

impl<E: Clone> Default for List<E>

fn default() -> Self

Creates an empty List<E>.

impl<E> Drop for List<E>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Eq + Clone> Eq for List<T>

impl<'a, E: Clone> From<&'a [E]> for List<E>

fn from(slice: &[E]) -> Self

Performs the conversion.

impl<'a, E: Clone> From<&'a Vec<E>> for List<E>

fn from(vec: &Vec<E>) -> Self

Create a vector from a std::vec::Vec.

Time: O(n)

impl<'s, 'a, E, OE> From<&'s List<&'a E>> for List<OE> where
    E: ToOwned<Owned = OE>,
    OE: Borrow<E> + Clone, 

fn from(vec: &List<&E>) -> Self

Performs the conversion.

impl<E: Clone> From<Vec<E>> for List<E>

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

Create a List from a std::vec::Vec.

Time: O(n)

impl<E: Clone> FromIterator<E> for List<E>

fn from_iter<I: IntoIterator<Item = E>>(iterator: I) -> Self

Creates a value from an iterator.

impl<E: Hash + Clone> Hash for List<E>

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, 

Feeds a slice of this type into the given Hasher.

impl<E: Clone> IntoIterator for List<E>

type Item = E

The type of the elements being iterated over.

type IntoIter = IntoIter<E>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, E: Clone> IntoIterator for &'a List<E>

type Item = &'a E

The type of the elements being iterated over.

type IntoIter = Iter<'a, E>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, E: Clone> IntoIterator for &'a mut List<E>

type Item = &'a mut E

The type of the elements being iterated over.

type IntoIter = IterMut<'a, E>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<E: PartialEq + Clone> PartialEq<List<E>> for List<E>

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: &Self) -> bool

This method tests for !=.