Struct im::vector::Vector
[−]
[src]
pub struct Vector<A> { /* fields omitted */ }
A persistent vector of elements of type A
.
This is an implementation of bitmapped vector tries, which offers highly efficient index lookups as well as appending elements to, or popping elements off, either side of the vector.
This is generally the best data structure if you're looking for
something list like. If you don't need lookups or updates by
index, but do need fast concatenation of whole lists, you should
use the CatList
instead.
If you're familiar with the Clojure variant, this improves on it
by being efficiently extensible at the front as well as the back.
If you're familiar with Immutable.js, this is
essentially the same, but with easier mutability because Rust has
the advantage of direct access to the garbage collector (which in
our case is just Arc
).
Methods
impl<A> Vector<A>
[src]
pub fn new() -> Self
[src]
Construct an empty vector.
pub fn singleton<R>(a: R) -> Self where
R: Shared<A>,
[src]
R: Shared<A>,
Construct a vector with a single value.
pub fn len(&self) -> usize
[src]
pub fn is_empty(&self) -> bool
[src]
Test whether a list is empty.
Time: O(1)
ⓘImportant traits for Iter<A>pub fn iter(&self) -> Iter<A>
[src]
Get an iterator over a vector.
Time: O(log n) per next()
call
pub fn head(&self) -> Option<Arc<A>>
[src]
Get the first element of a vector.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn tail(&self) -> Option<Vector<A>>
[src]
Get the vector without the first element.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn last(&self) -> Option<Arc<A>>
[src]
Get the last element of a vector.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn init(&self) -> Option<Vector<A>>
[src]
Get the vector without the last element.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn get(&self, index: usize) -> Option<Arc<A>>
[src]
Get the value at index index
in a vector.
Returns None
if the index is out of bounds.
Time: O(log n)
pub fn get_unwrapped(&self, index: usize) -> Arc<A>
[src]
Get the value at index index
in a vector, directly.
Panics if the index is out of bounds.
Time: O(log n)
pub fn set<RA>(&self, index: usize, value: RA) -> Self where
RA: Shared<A>,
[src]
RA: Shared<A>,
Create a new vector with the value at index index
updated.
Panics if the index is out of bounds.
Time: O(log n)
pub fn set_mut<RA>(&mut self, index: usize, value: RA) where
RA: Shared<A>,
[src]
RA: Shared<A>,
Update the value at index index
in a vector.
Panics if the index is out of bounds.
This is a copy-on-write operation, so that the parts of the vector's structure which are shared with other vectors will be safely copied before mutating.
Time: O(log n)
pub fn push_back<RA>(&self, value: RA) -> Self where
RA: Shared<A>,
[src]
RA: Shared<A>,
Construct a vector with a new value prepended to the end of the current vector.
Time: O(log n)
pub fn snoc<RA>(&self, a: RA) -> Self where
RA: Shared<A>,
[src]
RA: Shared<A>,
Construct a vector with a new value prepended to the end of the current vector.
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(log n)
pub fn push_back_mut<RA>(&mut self, value: RA) where
RA: Shared<A>,
[src]
RA: Shared<A>,
Update a vector in place with a new value prepended to the end of it.
This is a copy-on-write operation, so that the parts of the vector's structure which are shared with other vectors will be safely copied before mutating.
Time: O(log n)
pub fn push_front<RA>(&self, value: RA) -> Self where
RA: Shared<A>,
[src]
RA: Shared<A>,
Construct a vector with a new value prepended to the front of the current vector.
Time: O(log n)
pub fn cons<RA>(&self, a: RA) -> Self where
RA: Shared<A>,
[src]
RA: Shared<A>,
Construct a vector with a new value prepended to the front of the current vector.
This is an alias for push_front, for the Lispers in the house.
Time: O(log n)
pub fn push_front_mut<RA>(&mut self, value: RA) where
RA: Shared<A>,
[src]
RA: Shared<A>,
Update a vector in place with a new value prepended to the front of it.
This is a copy-on-write operation, so that the parts of the vector's structure which are shared with other vectors will be safely copied before mutating.
Time: O(log n)
pub fn pop_back(&self) -> Option<(Arc<A>, Self)>
[src]
Get the last element of a vector, as well as the vector with the last element removed.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn pop_back_mut(&mut self) -> Option<Arc<A>>
[src]
Remove the last element of a vector in place and return it.
This is a copy-on-write operation, so that the parts of the vector's structure which are shared with other vectors will be safely copied before mutating.
Time: O(log n)
pub fn pop_front(&self) -> Option<(Arc<A>, Self)>
[src]
Get the first element of a vector, as well as the vector with the first element removed.
If the vector is empty, None
is returned.
Time: O(log n)
pub fn uncons(&self) -> Option<(Arc<A>, Self)>
[src]
Get the head and the tail of a vector.
If the vector is empty, None
is returned.
This is an alias for pop_front
.
Time: O(log n)
pub fn unsnoc(&self) -> Option<(Arc<A>, Vector<A>)>
[src]
Get the last element of a vector, as well as the vector with the last element removed.
If the vector is empty, None
is returned.
This is an alias for pop_back
.
Time: O(1)*
pub fn pop_front_mut(&mut self) -> Option<Arc<A>>
[src]
Remove the first element of a vector in place and return it.
This is a copy-on-write operation, so that the parts of the vector's structure which are shared with other vectors will be safely copied before mutating.
Time: O(log n)
pub fn split_at(&self, index: usize) -> (Self, Self)
[src]
Split a vector at a given index, returning a vector containing every element before of the index and a vector containing every element from the index onward.
Time: O(log n)
pub fn skip(&self, count: usize) -> Self
[src]
Construct a vector with count
elements removed from the
start of the current vector.
Time: O(log n)
pub fn take(&self, count: usize) -> Self
[src]
Construct a vector of the first count
elements from the
current vector.
Time: O(log n)
pub fn slice(&self, start_index: usize, end_index: usize) -> Self
[src]
Construct a vector with the elements from start_index
until end_index
in the current vector.
Time: O(log n)
pub fn append<R>(&self, other: R) -> Self where
R: Borrow<Self>,
[src]
R: Borrow<Self>,
Append the vector other
to the end of the current vector.
Time: O(n) where n = the length of other
Examples
assert_eq!( vector![1, 2, 3].append(vector![7, 8, 9]), vector![1, 2, 3, 7, 8, 9] );
pub fn write<I: IntoIterator<Item = R>, R: Shared<A>>(
&mut self,
index: usize,
iter: I
)
[src]
&mut self,
index: usize,
iter: I
)
Write from an iterator into a vector, starting at the given index.
This will overwrite elements in the vector until the iterator ends or the end of the vector is reached.
Time: O(n) where n = the length of the iterator
pub fn reverse(&self) -> Self
[src]
Construct a vector which is the reverse of the current vector.
Time: O(1)
Examples
assert_eq!( vector![1, 2, 3, 4, 5].reverse(), vector![5, 4, 3, 2, 1] );
pub fn reverse_mut(&mut self)
[src]
Reverse a vector in place.
Time: O(1)
Examples
let mut v = vector![1, 2, 3, 4, 5]; v.reverse_mut(); assert_eq!( v, vector![5, 4, 3, 2, 1] );
pub fn sort(&self) -> Self where
A: Ord,
[src]
A: Ord,
Sort a vector of ordered elements.
Time: O(n log n) worst case
Examples
assert_eq!( vector![2, 8, 1, 6, 3, 7, 5, 4].sort(), vector![1, 2, 3, 4, 5, 6, 7, 8] );
pub fn sort_by<F>(&self, cmp: F) -> Self where
F: Fn(&A, &A) -> Ordering,
[src]
F: Fn(&A, &A) -> Ordering,
Sort a vector using a comparator function.
Time: O(n log n) roughly
pub fn insert<RA>(&self, item: RA) -> Self where
A: Ord,
RA: Shared<A>,
[src]
A: Ord,
RA: Shared<A>,
Insert an item into a sorted vector.
Constructs a new vector with the new item inserted before the
first item in the vector 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!( vector![2, 4, 5].insert(1).insert(3).insert(6), vector![1, 2, 3, 4, 5, 6] );
Trait Implementations
impl<A> Clone for Vector<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 Vector<A>
[src]
impl<A: Debug> Debug for Vector<A>
[src]
fn fmt(&self, f: &mut Formatter) -> Result<(), Error>
[src]
Formats the value using the given formatter. Read more
impl<A: PartialEq> PartialEq for Vector<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 Vector<A>
[src]
impl<A: PartialOrd> PartialOrd for Vector<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 Vector<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> Add for Vector<A>
[src]
type Output = Vector<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 Vector<A>
[src]
type Output = Vector<A>
The resulting type after applying the +
operator.
fn add(self, other: Self) -> Self::Output
[src]
Performs the +
operation.
impl<A: Hash> Hash for Vector<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> Sum for Vector<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, R: Shared<A>> Extend<R> for Vector<A>
[src]
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> Index<usize> for Vector<A>
[src]
type Output = A
The returned type after indexing.
fn index(&self, index: usize) -> &Self::Output
[src]
Performs the indexing (container[index]
) operation.
impl<A> IndexMut<usize> for Vector<A> where
A: Clone,
[src]
A: Clone,
fn index_mut(&mut self, index: usize) -> &mut Self::Output
[src]
Performs the mutable indexing (container[index]
) operation.
impl<A, RA: Shared<A>> FromIterator<RA> for Vector<A>
[src]
fn from_iter<T>(iter: T) -> Self where
T: IntoIterator<Item = RA>,
[src]
T: IntoIterator<Item = RA>,
Creates a value from an iterator. Read more
impl<A> IntoIterator for Vector<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 Vector<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