Struct immutable_seq::Seq
[−]
[src]
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>
[src]
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,
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>
[src]
fn clone(&self) -> Seq<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<T: 'static> PartialEq for Seq<T> where
T: PartialEq,
[src]
T: PartialEq,
fn eq(&self, other: &Seq<T>) -> bool
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
This method tests for !=
.
impl<T: 'static> Eq for Seq<T> where
T: Eq,
[src]
T: Eq,
impl<T: 'static> PartialOrd for Seq<T> where
T: PartialOrd,
[src]
T: PartialOrd,
fn partial_cmp(&self, other: &Seq<T>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
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
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
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
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<T: 'static> Ord for Seq<T> where
T: Ord,
[src]
T: Ord,
fn cmp(&self, other: &Seq<T>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<T: 'static> Debug for Seq<T> where
T: Debug,
[src]
T: Debug,
impl<'a, T: 'static> IntoIterator for &'a Seq<T>
[src]
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. Read more
impl<T: 'static> FromIterator<T> for Seq<T>
[src]
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = T>,
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more