Struct immutable_seq::Seq

pub struct Seq<T>(_);

A data-structure implementing an immutable sequence of values.

An amortized running time is given for each operation, with n referring to the length of the sequence and i being the integral index used by some operations. These bounds hold even in a persistent (shared) setting.

This implementation is based on Haskell's Data.Sequence library (http://hackage.haskell.org/package/containers/docs/Data-Sequence.html), and the following paper: * Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217. http://staff.city.ac.uk/~ross/papers/FingerTree.html

Methods

impl<T: 'static> Seq<T>

fn empty() -> Seq<T>

The empty sequence. Time: O(1)

fn singleton(x: T) -> Seq<T>

A sequence with a single value. Time O(1)

fn push_front(&self, x: T) -> Seq<T>

A new sequence that is self with x added to the front. Time: O(1)

fn push_back(&self, x: T) -> Seq<T>

A new sequence that is self with x added to the back. Time: O(1)

fn append(&self, other: &Seq<T>) -> Seq<T>

The concatenation of self with other. Time: O(log(min(n1,n2)))

fn is_empty(&self) -> bool

Is the sequence empty?. Time: O(1)

fn len(&self) -> usize

The number of elements in the sequence. Time: O(1)

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

The first element in the sequence, if it exists. Time: O(1)

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

The back element, if it exsts. Time: O(1)

fn pop_front(&self) -> Seq<T>

A new sequence that is self with the front element removed, together with the front element (if it exists). Time: O(1)

fn pop_back(&self) -> Seq<T>

A new sequence that is self with the back element removed, together with the back element (if it exists). Time: O(1)

fn adjust<F>(&self, i: usize, func: F) -> Seq<T> where
    F: FnOnce(&T) -> T, 

A new sequence with the element at index i replaced by f(self[i]). Time: O(log(min(i,n-i)))

If i is out of range, returns a clone of self.

fn update(&self, i: usize, x: T) -> Seq<T>

A new sequence with the element at index i replaced by x. Time: O(log(min(i,n-i)))

If i is out of range, returns a clone of self.

fn truncate(&self, count: usize) -> Seq<T>

A new sequence consisting of only the first count elements. Time: O(log(min(count, n - count)))

If count >= self.len(), then returns a clone of self.

fn skip(&self, count: usize) -> Seq<T>

A new sequence consisting of only the last count elements. Time: O(log(min(count,n - count)))

If count >= self.len(), then returns a clone of self.

fn split(&self, n: usize) -> (Seq<T>, Seq<T>)

Two new sequences, consisting of the first count elements, and the remaining elements, respectively. Time: O(log(min(count,n-count)))

If count >= self.len(), then the first sequence is a clone of self and the second is empty.

fn remove(&self, i: usize) -> Seq<T>

A new sequence with the element at index i removed, together with the element at index i, if it exists. Time: O(log(min(i,n-i)))

If i is out of range, then the returned sequence is a clone of self, and the element is None.

fn insert(&self, i: usize, x: T) -> Seq<T>

A new sequence with x inserted at index i. Time: O(log(min(i,n-i)))

If i < self.len(), then x will immediately precede self[i] in the new sequence.

if i >= self.len(), then x will be the last element in the new sequence.

fn get(&self, i: usize) -> Option<&T>

Get the element at index i, if it exists. Time: O(log(min(i,n-i)))

fn iter(&self) -> Iter<T>

An iterator over the sequence. Time: O(1)

Trait Implementations

impl<T: 'static> Clone for Seq<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: 'static> PartialEq for Seq<T> where
    T: PartialEq, 

fn eq(&self, other: &Seq<T>) -> 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<T: 'static> Eq for Seq<T> where
    T: Eq, 

impl<T: 'static> PartialOrd for Seq<T> where
    T: PartialOrd, 

fn partial_cmp(&self, other: &Seq<T>) -> 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<T: 'static> Ord for Seq<T> where
    T: Ord, 

fn cmp(&self, other: &Seq<T>) -> Ordering

This method returns an Ordering between self and other.

impl<T: 'static> Debug for Seq<T> where
    T: Debug, 

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

Formats the value using the given formatter.

impl<'a, T: 'static> IntoIterator for &'a Seq<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T: 'static> FromIterator<T> for Seq<T>

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

Creates a value from an iterator.

impl<T: 'static> From<Vec<T>> for Seq<T>

fn from(v: Vec<T>) -> Seq<T>

Performs the conversion.

impl<T: 'static> Index<usize> for Seq<T>

type Output = T

The returned type after indexing

fn index(&self, index: usize) -> &T

The method for the indexing (container[index]) operation