Struct im::vector::Vector

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 (amortised linear time) 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>

pub fn new() -> Self

Construct an empty vector.

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

Construct a vector with a single value.

pub fn len(&self) -> usize

Get the length of a vector.

Time: O(1)

Examples

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

pub fn is_empty(&self) -> bool

Test whether a list is empty.

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 vector.

Time: O(log n) per next() call

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

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>>

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>>

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>>

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>>

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>

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>, 

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>, 

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>, 

Construct a vector with a new value prepended to the end of the current vector.

Time: O(log n)

pub fn push_back_mut<RA>(&mut self, value: RA) where
    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>, 

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

Time: O(log n)

pub fn push_front_mut<RA>(&mut self, value: RA) where
    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)>

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>>

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)>

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 pop_front_mut(&mut self) -> Option<Arc<A>>

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)

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

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

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

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>, 

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
)

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

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)

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, 

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, 

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>, 

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>

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 Vector<A>

fn default() -> Self

Returns the "default value" for a type.

impl<A: Debug> Debug for Vector<A>

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

Formats the value using the given formatter.

impl<A: PartialEq> PartialEq for Vector<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 Vector<A>

impl<A: PartialOrd> PartialOrd for Vector<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 Vector<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> Add for Vector<A>

type Output = Vector<A>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Vector<A>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<A: Hash> Hash for Vector<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> Sum for Vector<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, R: Shared<A>> Extend<R> for Vector<A>

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

Extends a collection with the contents of an iterator.

impl<A, RA: Shared<A>> FromIterator<RA> for Vector<A>

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

Creates a value from an iterator.

impl<A> IntoIterator for Vector<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 Vector<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> From<Vec<A>> for Vector<A>

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

Performs the conversion.