Struct im::catlist::CatList
[−]
[src]
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>
[src]
pub fn new() -> Self
[src]
Construct an empty list.
pub fn singleton<R>(a: R) -> Self where
R: Shared<A>,
[src]
R: Shared<A>,
Construct a list with a single value.
pub fn is_empty(&self) -> bool
[src]
Test whether a list is empty.
pub fn len(&self) -> usize
[src]
pub fn head(&self) -> Option<Arc<A>>
[src]
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>)>
[src]
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>>
[src]
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>>
[src]
Get the list without the last element.
Time: O(1)*
If the list is empty, None
is returned.
pub fn tail(&self) -> Option<Self>
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>>
[src]
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>>
[src]
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>,
[src]
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>,
[src]
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>)>
[src]
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>,
[src]
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>)>
[src]
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>)>
[src]
pub fn unsnoc(&self) -> Option<(Arc<A>, CatList<A>)>
[src]
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>pub fn iter(&self) -> Iter<A>
[src]
Get an iterator over a list.
pub fn reverse(&self) -> Self
[src]
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,
[src]
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,
[src]
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>,
[src]
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>
[src]
fn clone(&self) -> Self
[src]
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<A> Default for CatList<A>
[src]
impl<A> Add for CatList<A>
[src]
type Output = CatList<A>
The resulting type after applying the +
operator.
fn add(self, other: Self) -> Self::Output
[src]
Performs the +
operation.
impl<'a, A> Add for &'a CatList<A>
[src]
type Output = CatList<A>
The resulting type after applying the +
operator.
fn add(self, other: Self) -> Self::Output
[src]
Performs the +
operation.
impl<A, R> Extend<R> for CatList<A> where
A: Ord,
R: Shared<A>,
[src]
A: Ord,
R: Shared<A>,
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = R>,
[src]
I: IntoIterator<Item = R>,
Extends a collection with the contents of an iterator. Read more
impl<A: PartialEq> PartialEq for CatList<A>
[src]
fn eq(&self, other: &Self) -> bool
[src]
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests for !=
.
impl<A: Eq> Eq for CatList<A>
[src]
impl<A: PartialOrd> PartialOrd for CatList<A>
[src]
fn partial_cmp(&self, other: &Self) -> Option<Ordering>
[src]
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<A: Ord> Ord for CatList<A>
[src]
fn cmp(&self, other: &Self) -> Ordering
[src]
This method returns an Ordering
between self
and other
. Read more
fn max(self, other: Self) -> Self
1.21.0[src]
Compares and returns the maximum of two values. Read more
fn min(self, other: Self) -> Self
1.21.0[src]
Compares and returns the minimum of two values. Read more
impl<A: Hash> Hash for CatList<A>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<A: Debug> Debug for CatList<A>
[src]
fn fmt(&self, f: &mut Formatter) -> Result<(), Error>
[src]
Formats the value using the given formatter. Read more
impl<A> IntoIterator for CatList<A>
[src]
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
[src]
Creates an iterator from a value. Read more
impl<'a, A> IntoIterator for &'a CatList<A>
[src]
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
[src]
Creates an iterator from a value. Read more
impl<A> Sum for CatList<A>
[src]
fn sum<I>(it: I) -> Self where
I: Iterator<Item = Self>,
[src]
I: Iterator<Item = Self>,
Method which takes an iterator and generates Self
from the elements by "summing up" the items. Read more
impl<A, T> FromIterator<T> for CatList<A> where
T: Shared<A>,
[src]
T: Shared<A>,
fn from_iter<I>(source: I) -> Self where
I: IntoIterator<Item = T>,
[src]
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<'a, A, T> From<&'a [T]> for CatList<A> where
&'a T: Shared<A>,
[src]
&'a T: Shared<A>,
impl<'a, A, T> From<&'a Vec<T>> for CatList<A> where
&'a T: Shared<A>,
[src]
&'a T: Shared<A>,