Struct im::catlist::CatList

pub struct CatList<A> { /* fields omitted */ }

A catenable list of values of type A.

A list data structure with O(1)* push and pop operations on both ends and O(1) concatenation of lists.

You usually want the Vector instead, which performs better on all operations except concatenation. If instant concatenation is what you need, the CatList is the cat for you.

Methods

impl<A> CatList<A>

pub fn new() -> Self

Construct an empty list.

pub fn singleton<R>(a: R) -> Self where
    R: Shared<A>, 

Construct a list with a single value.

pub fn is_empty(&self) -> bool

Test whether a list is empty.

pub fn len(&self) -> usize

Get the length of a list.

Time: O(1)

Examples

assert_eq!(5, catlist![1, 2, 3, 4, 5].len());

pub fn head(&self) -> Option<Arc<A>>

Get the first element of a list.

If the list is empty, None is returned.

pub fn pop_back(&self) -> Option<(Arc<A>, CatList<A>)>

Get the last element of a list, as well as the list with the last element removed.

If the list is empty, None is returned.

Time: O(1)*

pub fn last(&self) -> Option<Arc<A>>

Get the last element of a list.

Time: O(1)*

If the list is empty, None is returned.

pub fn init(&self) -> Option<CatList<A>>

Get the list without the last element.

Time: O(1)*

If the list is empty, None is returned.

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

Get the tail of a list.

Time: O(1)

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

pub fn append<R>(&self, other: R) -> Self where
    R: Borrow<Self>, 

Append the list other to the end of the current list.

Time: O(1)

Examples

assert_eq!(
  catlist![1, 2, 3].append(catlist![7, 8, 9]),
  catlist![1, 2, 3, 7, 8, 9]
);

pub fn push_front<R>(&self, a: R) -> Self where
    R: Shared<A>, 

Construct a list with a new value prepended to the front of the current list.

Time: O(1)

pub fn append_mut<R>(&mut self, other_ref: R) where
    R: Borrow<Self>, 

Append the list other to the end of the current list, in place.

This is a copy-on-write operation, so that the parts of the set's structure which are shared with other sets will be safely copied before mutating.

Time: O(1)

Examples

let mut l = catlist![1, 2, 3];
l.append_mut(catlist![7, 8, 9]);

assert_eq!(l, catlist![1, 2, 3, 7, 8, 9]);

pub fn push_front_mut<R>(&mut self, a: R) where
    R: Shared<A>, 

Push a value onto the front of a list, updating in place.

This is a copy-on-write operation, so that the parts of the set's structure which are shared with other sets will be safely copied before mutating.

Time: O(1)

pub fn push_back_mut<R>(&mut self, a: R) where
    R: Shared<A>, 

Push a value onto the back of a list, updating in place.

This is a copy-on-write operation, so that the parts of the set's structure which are shared with other sets will be safely copied before mutating.

Time: O(1)

pub fn pop_front_mut(&mut self) -> Option<Arc<A>>

Remove a value from the front of a list, updating in place. Returns the removed value.

This is a copy-on-write operation, so that the parts of the set's structure which are shared with other sets will be safely copied before mutating.

Time: O(1)*

pub fn pop_back_mut(&mut self) -> Option<Arc<A>>

Remove a value from the back of a list, updating in place. Returns the removed value.

This is a copy-on-write operation, so that the parts of the set's structure which are shared with other sets will be safely copied before mutating.

Time: O(1)*

pub fn snoc<R>(&self, a: R) -> Self where
    R: Shared<A>, 

Construct a list with a new value appended to the back of the current list.

snoc, for the curious, is cons spelled backwards, to denote that it works on the back of the list rather than the front. If you don't find that as clever as whoever coined the term no doubt did, this method is also available as push_back().

Time: O(1)

pub fn push_back<R>(&self, a: R) -> Self where
    R: Shared<A>, 

Construct a list with a new value appended to the back of the current list.

Time: O(1)

pub fn pop_front(&self) -> Option<(Arc<A>, CatList<A>)>

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.

Time: O(1)*

Examples

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

fn walk_through_list<A>(list: &CatList<A>) where A: Debug {
    match list.pop_front() {
        None => (),
        Some((ref head, ref tail)) => {
            print!("{:?}", head);
            walk_through_list(tail)
        }
    }
}

pub fn cons<R>(&self, a: R) -> Self where
    R: Shared<A>, 

Construct a list with a new value prepended to the front of the current list.

This is an alias for push_front, for the Lispers in the house.

Time: O(1)

pub fn uncons(&self) -> Option<(Arc<A>, CatList<A>)>

Get the head and the tail of a list.

If the list is empty, None is returned.

This is an alias for pop_front.

Time: O(1)*

pub fn uncons2(&self) -> Option<(Arc<A>, Arc<A>, CatList<A>)>

pub fn unsnoc(&self) -> Option<(Arc<A>, CatList<A>)>

Get the last element of a list, as well as the list with the last element removed.

If the list is empty, None is returned.

This is an alias for pop_back.

Time: O(1)*

Important traits for Iter<A>

impl<A> Iterator for Iter<A> type Item = Arc<A>;

pub fn iter(&self) -> Iter<A>

Get an iterator over a list.

pub fn reverse(&self) -> Self

Construct a list which is the reverse of the current list.

Please note that if all you want is to iterate over the list from back to front, it is much more efficient to use a reversed iterator rather than doing the work of reversing the list first.

Time: O(n)

Examples

assert_eq!(
  catlist![1, 2, 3, 4, 5].reverse(),
  catlist![5, 4, 3, 2, 1]
);

pub fn sort_by<F>(&self, cmp: F) -> Self where
    F: Fn(&A, &A) -> Ordering, 

Sort a list using a comparator function.

Time: O(n log n)

pub fn sort(&self) -> Self where
    A: Ord, 

Sort a list of ordered elements.

Time: O(n log n)

Examples

assert_eq!(
  catlist![2, 8, 1, 6, 3, 7, 5, 4].sort(),
  CatList::from_iter(1..9)
);

pub fn insert<T>(&self, item: T) -> Self where
    A: Ord,
    T: Shared<A>, 

Insert an item into a sorted list.

Constructs a new list with the new item inserted before the first item in the list which is larger than the new item, as determined by the Ord trait.

Please note that this is a very inefficient operation; if you want a sorted list, consider if OrdSet might be a better choice for you.

Time: O(n)

Examples

assert_eq!(
  catlist![2, 4, 5].insert(1).insert(3).insert(6),
  catlist![1, 2, 3, 4, 5, 6]
);

Trait Implementations

impl<A> Clone for CatList<A>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A> Default for CatList<A>

fn default() -> Self

Returns the "default value" for a type.

impl<A> Add for CatList<A>

type Output = CatList<A>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self::Output

Performs the + operation.

impl<'a, A> Add for &'a CatList<A>

type Output = CatList<A>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self::Output

Performs the + operation.

impl<A, R> Extend<R> for CatList<A> where
    A: Ord,
    R: Shared<A>, 

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = R>, 

Extends a collection with the contents of an iterator.

impl<A: PartialEq> PartialEq for CatList<A>

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

This method tests for !=.

impl<A: Eq> Eq for CatList<A>

impl<A: PartialOrd> PartialOrd for CatList<A>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A: Ord> Ord for CatList<A>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<A: Hash> Hash for CatList<A>

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<A: Debug> Debug for CatList<A>

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

Formats the value using the given formatter.

impl<A> IntoIterator for CatList<A>

type Item = Arc<A>

The type of the elements being iterated over.

type IntoIter = Iter<A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A> IntoIterator for &'a CatList<A>

type Item = Arc<A>

The type of the elements being iterated over.

type IntoIter = Iter<A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A> Sum for CatList<A>

fn sum<I>(it: I) -> Self where
    I: Iterator<Item = Self>, 

Method which takes an iterator and generates Self from the elements by "summing up" the items.

impl<A, T> FromIterator<T> for CatList<A> where
    T: Shared<A>, 

fn from_iter<I>(source: I) -> Self where
    I: IntoIterator<Item = T>, 

Creates a value from an iterator.

impl<'a, A, T> From<&'a [T]> for CatList<A> where
    &'a T: Shared<A>, 

fn from(slice: &'a [T]) -> Self

Performs the conversion.

impl<'a, A, T> From<&'a Vec<T>> for CatList<A> where
    &'a T: Shared<A>, 

fn from(vec: &'a Vec<T>) -> Self

Performs the conversion.

impl<A> From<Vec<A>> for CatList<A>

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

Performs the conversion.

impl<A> From<Vec<Arc<A>>> for CatList<A>

fn from(vec: Vec<Arc<A>>) -> Self

Performs the conversion.