Struct ImmutableVector

pub struct ImmutableVector<T> { /* private fields */ }

An immutable vector implementation with efficient edits/clones.

Internally, the vector is represented like a finger tree. Each interal node holds up to 32 children, and each leaf node holds up to 32 values. Most operations take O(log₃₂ n) time, but log₃₂ grows really slowly, so in pracice they are basically O(1).

Example

use rust_dsa::ImmutableVector;

let vector = ImmutableVector::new();

// Each time we push a value, the original vector doesn't change.
let vector1 = vector.push(1);
let vector2 = vector1.push(2);
let vector3 = vector2.push(3);

assert_eq!(vector, ImmutableVector::from([]));
assert_eq!(vector1, ImmutableVector::from([1]));
assert_eq!(vector2, ImmutableVector::from([1, 2]));
assert_eq!(vector3, ImmutableVector::from([1, 2, 3]));

// We can also remove elements.
let vector4 = vector3.remove(1);
assert_eq!(vector4, ImmutableVector::from([1, 3]));

// And join two vectors.
let vector5 = vector4.join(&vector2);
assert_eq!(vector5, ImmutableVector::from([1, 3, 1, 2]));

// We can iterate over vectors.
for x in vector5 {
    // x has type Rc<i32>
    println!("{x}");
}

for x in &vector4 {
    // x has type &i32
    println!("{x}");
}

// And create vectors from iterators.
let vector6: ImmutableVector<_> = ('a'..='z').collect();
assert_eq!(vector6.len(), 26);

Runtime complexity

Operation	Runtime Complexity
ImmutableVector::push	O(log32 n)
ImmutableVector::remove	O(log32 n)
ImmutableVector::replace	O(log32 n)
ImmutableVector::join	O(1)
ImmutableVector::clone	O(1)

Implementations

impl<T> ImmutableVector<T>

pub fn new() -> ImmutableVector<T>

Creates an empty vector.

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

Returns a reference to the element at index or None if out of bounds.

Example

use rust_dsa::ImmutableVector;

let vector = ImmutableVector::from([1, 2, 3, 4, 5, 6, 7]);

assert_eq!(vector.get(3), Some(&4));
assert_eq!(vector.get(10), None);

pub fn range<R>(&self, range: R) -> ImmutableVector<T>

where R: RangeBounds<usize>,

Returns a new vector that contains the elements in the specified range.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the vector.

Example

use rust_dsa::ImmutableVector;

let racecar: ImmutableVector<_> = "racecar".chars().collect();
let car: ImmutableVector<_> = "car".chars().collect();

assert_eq!(racecar.range(4..), car);

pub fn get_rc(&self, index: usize) -> Option<Rc<T>>

Returns an Rc that contains to the element at index or None if out of bounds.

Example

use rust_dsa::ImmutableVector;
use std::rc::Rc;

let vector = ImmutableVector::from([1, 2, 3, 4, 5, 6, 7]);

assert_eq!(vector.get_rc(3), Some(Rc::new(4)));
assert_eq!(vector.get_rc(10), None);

pub fn push(&self, value: T) -> ImmutableVector<T>

Returns a new vector with the value appended.

Example

use rust_dsa::ImmutableVector;

let vector = ImmutableVector::new();
let vector = vector.push(1);
let vector = vector.push(2);
let vector = vector.push(3);

assert_eq!(vector, ImmutableVector::from([1, 2, 3]));

pub fn remove(&self, index: usize) -> ImmutableVector<T>

Returns a new vector without the value at index.

Panics

Panics if index >= len.

Example

use rust_dsa::ImmutableVector;

let feast: ImmutableVector<_> = "feast".chars().collect();

let east = feast.remove(0);

assert_eq!(
    east,
    ImmutableVector::from(['e', 'a', 's', 't'])
);

pub fn replace(&self, index: usize, value: T) -> ImmutableVector<T>

Returns a new vector with value at position index.

Panics

Panics if index >= len.

Example

use rust_dsa::ImmutableVector;

let unseasonably: ImmutableVector<_> = "unseasonably".chars().collect();
let unreasonably: ImmutableVector<_> = "unreasonably".chars().collect();

assert_eq!(
    unseasonably.replace(2, 'r'),
    unreasonably
);

pub fn join(&self, other: &ImmutableVector<T>) -> ImmutableVector<T>

Returns a new vector that contains the elements in self followed by the elements in other.

Example

use rust_dsa::ImmutableVector;

let fruits = ImmutableVector::from(["apple", "banana"]);
let veggies = ImmutableVector::from(["asparagus", "broccoli"]);

let both = fruits.join(&veggies);

assert_eq!(
    both,
    ImmutableVector::from(["apple", "banana", "asparagus", "broccoli"])
);

pub fn len(&self) -> usize

Returns the length of the vector.

Example

use rust_dsa::ImmutableVector;

let empty: ImmutableVector<bool> = ImmutableVector::new();
let forty: ImmutableVector<_> = (0..40).collect();

assert_eq!(empty.len(), 0);
assert_eq!(forty.len(), 40);

pub fn is_empty(&self) -> bool

Returns true if the vector is empty.

Example

use rust_dsa::ImmutableVector;

let empty: ImmutableVector<bool> = ImmutableVector::new();
let forty: ImmutableVector<_> = (0..40).collect();

assert!(empty.is_empty());
assert!(!forty.is_empty());

Trait Implementations

impl<T: Clone> Clone for ImmutableVector<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for ImmutableVector<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for ImmutableVector<T>

fn default() -> ImmutableVector<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for ImmutableVector<T>

fn from(array: [T; N]) -> ImmutableVector<T>

Converts to this type from the input type.

impl<T> FromIterator<Rc<T>> for ImmutableVector<T>

fn from_iter<I: IntoIterator<Item = Rc<T>>>(iter: I) -> ImmutableVector<T>

Creates a value from an iterator.

impl<T> FromIterator<T> for ImmutableVector<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> ImmutableVector<T>

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a ImmutableVector<T>

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for ImmutableVector<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = Rc<T>

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> PartialEq for ImmutableVector<T>

where T: PartialEq,

fn eq(&self, other: &ImmutableVector<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Eq for ImmutableVector<T>

where T: Eq,