pub struct List<E> { /* private fields */ }
Expand description
A singly-linked persistent thread safe list.
Implementations§
Source§impl<E: Clone> List<E>
impl<E: Clone> List<E>
Sourcepub fn append(&mut self, other: &mut Self)
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());
Sourcepub fn iter(&self) -> Iter<'_, E> ⓘ
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);
Sourcepub fn iter_mut(&mut self) -> IterMut<'_, E> ⓘ
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);
Sourcepub fn is_empty(&self) -> bool
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());
Sourcepub fn len(&self) -> usize
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);
Sourcepub fn unit(first: E) -> Self
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)
);
Sourcepub fn clear(&mut self)
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);
Sourcepub fn cons(&self, first: E) -> Self
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.
Sourcepub fn uncons(&self) -> Option<(&E, Self)>
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)
}
}
}
Sourcepub fn contains(&self, x: &E) -> boolwhere
E: PartialEq<E>,
pub fn contains(&self, x: &E) -> boolwhere
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);
Sourcepub fn front(&self) -> Option<&E>
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));
Sourcepub fn front_mut(&mut self) -> Option<&mut E>
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));
Sourcepub fn push_front(&mut self, element: E)
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);
Sourcepub fn pop_front(&mut self) -> Option<E>
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);
Sourcepub fn split_off(&mut self, at: usize) -> Self
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);
Sourcepub fn split_at(self, at: usize) -> (Self, Self)
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);
Sourcepub fn reverse(&mut self)
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);
Sourcepub fn rest(&self) -> Self
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));
Sourcepub fn head(&self) -> Option<&E>
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.
Sourcepub fn tail(&self) -> Option<Self>
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§
Source§impl<'a, E: Clone> From<&'a Vec<E>> for List<E>
impl<'a, E: Clone> From<&'a Vec<E>> for List<E>
Source§fn from(vec: &Vec<E>) -> Self
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>
impl<E: Clone> From<Vec<E>> for List<E>
Source§fn from(vec: Vec<E>) -> Self
fn from(vec: Vec<E>) -> Self
Create a List
from a std::vec::Vec
.
Time: O(n)