Struct List

pub struct List<T>(Backend<T>);

Represents OCaml list type.

Tuple Fields

0: Backend<T>

Implementations

impl<T> List<T>

pub fn new() -> Self

pub fn one(elt: T) -> Self

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

Methods from Deref<Target = Backend<T>>

pub fn append(&mut self, other: &mut LinkedList<T>)

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(1) time and O(1) memory.

Examples

use std::collections::LinkedList;

let mut list1 = LinkedList::new();
list1.push_back('a');

let mut list2 = LinkedList::new();
list2.push_back('b');
list2.push_back('c');

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<'_, T>

Provides a forward iterator.

Examples

use std::collections::LinkedList;

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

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

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<'_, T>

Provides a forward iterator with mutable references.

Examples

use std::collections::LinkedList;

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

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

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 cursor_front(&self) -> Cursor<'_, T, A>

🔬This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A>

🔬This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor with editing operations at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_back(&self) -> Cursor<'_, T, A>

🔬This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A>

🔬This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor with editing operations at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert!(dl.is_empty());

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

pub fn len(&self) -> usize

Returns the length of the LinkedList.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

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

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

dl.push_back(3);
assert_eq!(dl.len(), 3);

pub fn clear(&mut self)

Removes all elements from the LinkedList.

This operation should compute in O(n) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

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

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

pub fn contains(&self, x: &T) -> bool

where T: PartialEq,

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

This operation should compute linearly in O(n) time.

Examples

use std::collections::LinkedList;

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

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

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

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

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

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.front(), None);

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

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

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

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.front(), None);

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

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

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

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

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

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

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

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

match dl.back_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(dl.back(), Some(&5));

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

Adds an element first in the list.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

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

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

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

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

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_front(), None);

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

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

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().unwrap());

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

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_back(), None);
d.push_back(1);
d.push_back(3);
assert_eq!(d.pop_back(), Some(3));

pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>

where A: Clone,

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

This operation should compute in O(n) time.

Panics

Panics if at > len.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();

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

let mut split = d.split_off(2);

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

pub fn remove(&mut self, at: usize) -> T

🔬This is a nightly-only experimental API. (linked_list_remove)

Removes the element at the given index and returns it.

This operation should compute in O(n) time.

Panics

Panics if at >= len

Examples

#![feature(linked_list_remove)]
use std::collections::LinkedList;

let mut d = LinkedList::new();

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

assert_eq!(d.remove(1), 2);
assert_eq!(d.remove(0), 3);
assert_eq!(d.remove(0), 1);

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&mut T) -> bool,

🔬This is a nightly-only experimental API. (linked_list_retain)

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&mut e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Examples

#![feature(linked_list_retain)]
use std::collections::LinkedList;

let mut d = LinkedList::new();

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

d.retain(|&mut x| x % 2 == 0);

assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

Because the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.

#![feature(linked_list_retain)]
use std::collections::LinkedList;

let mut d = LinkedList::new();

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

let keep = [false, true, false];
let mut iter = keep.iter();
d.retain(|_| *iter.next().unwrap());
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>

where F: FnMut(&mut T) -> bool,

Creates an iterator which uses a closure to determine if an element should be removed.

If the closure returns true, the element is removed from the list and yielded. If the closure returns false, or panics, the element remains in the list and will not be yielded.

If the returned ExtractIf is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use extract_if().for_each(drop) if you do not need the returned iterator.

The iterator also lets you mutate the value of each element in the closure, regardless of whether you choose to keep or remove it.

Examples

Splitting a list into even and odd values, reusing the original list:

use std::collections::LinkedList;

let mut numbers: LinkedList<u32> = LinkedList::new();
numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);

let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<LinkedList<_>>();
let odds = numbers;

assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);

Trait Implementations

impl<T> BinProtRead for List<T>

where T: BinProtRead,

fn binprot_read<R: Read + ?Sized>(r: &mut R) -> Result<Self, Error>

impl<T> BinProtWrite for List<T>

where T: BinProtWrite,

fn binprot_write<W: Write>(&self, w: &mut W) -> Result<()>

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for List<T>

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

Formats the value using the given formatter.

impl<T: Default> Default for List<T>

fn default() -> List<T>

Returns the “default value” for a type.

impl<T> DerefMut for List<T>

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<'de, T> Deserialize<'de> for List<T>

where T: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T, D> FailableToInputs for List<D>

where D: Deref<Target = T>, T: FailableToInputs,

fn to_input(&self, inputs: &mut Inputs) -> Result<(), InvalidBigInt>

impl<T> From<LinkedList<T>> for List<T>

fn from(original: Backend<T>) -> List<T>

Converts to this type from the input type.

impl<T> From<List<T>> for Backend<T>

fn from(original: List<T>) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for List<T>

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a List<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = <&'a LinkedList<T> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for List<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = <LinkedList<T> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> MallocSizeOf for List<T>

where T: MallocSizeOf,

fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize

Measure the heap usage of all descendant heap-allocated structures, but not the space taken up by the value itself.

impl<T: OfSexp> OfSexp for List<T>

fn of_sexp(s: &Sexp) -> Result<Self, IntoSexpError>

where Self: Sized,

impl<T: Ord> Ord for List<T>

fn cmp(&self, other: &List<T>) -> 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: PartialEq> PartialEq for List<T>

fn eq(&self, other: &List<T>) -> 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: PartialOrd> PartialOrd for List<T>

fn partial_cmp(&self, other: &List<T>) -> 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> Serialize for List<T>

where T: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<T: SexpOf> SexpOf for List<T>

fn sexp_of(&self) -> Sexp

impl<T> Deref for List<T>

type Target = LinkedList<T>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

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

impl<T> StructuralPartialEq for List<T>