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

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

Trait Implementations§

Source§

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

Source§

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

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

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

Source§

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

Formats the value using the given formatter. Read more
Source§

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

Source§

fn default() -> Self

Creates an empty List<E>.

Source§

impl<E> Drop for List<E>

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

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

Source§

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

Converts to this type from the input type.
Source§

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

Source§

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

Converts to this type from the input type.
Source§

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

Source§

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

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

Time: O(n)

Source§

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

Source§

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

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

Time: O(n)

Source§

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

Source§

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

Creates a value from an iterator. Read more
Source§

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

Source§

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

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

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

Feeds a slice of this type into the given Hasher. Read more
Source§

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

Source§

type Item = &'a E

The type of the elements being iterated over.
Source§

type IntoIter = Iter<'a, E>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

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

Source§

type Item = &'a mut E

The type of the elements being iterated over.
Source§

type IntoIter = IterMut<'a, E>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

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

Source§

type Item = E

The type of the elements being iterated over.
Source§

type IntoIter = IntoIter<E>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

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

Source§

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

Tests for self and other values to be equal, and is used by ==.
Source§

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

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

Auto Trait Implementations§

§

impl<E> Freeze for List<E>

§

impl<E> RefUnwindSafe for List<E>
where E: RefUnwindSafe,

§

impl<E> Send for List<E>
where E: Sync + Send,

§

impl<E> Sync for List<E>
where E: Sync + Send,

§

impl<E> Unpin for List<E>

§

impl<E> UnwindSafe for List<E>
where E: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.