Struct orx_imp_vec::ImpVec

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

ImpVec stands for ‘immutable-push-vec’.

It uses orx_split_vec::SplitVec as the underlying data structure, and hence, has the following features:

• Flexible in growth strategies; custom strategies can be defined.
• Growth does not cause any memory copies.
• Capacity of an already created fragment is never changed.
• The above feature allows the data to stay pinned in place. Memory location of an item added to the split vector will never change unless it is removed from the vector or the vector is dropped.

In addition, it allows to push/extend the vector with an immutable reference.

This allows to hold on the references of already pushed elements while building the collection.

Implementations

impl<T: Clone> ImpVec<T>

pub fn extend_from_slice(&self, other: &[T])

Clones and appends all elements in a slice to the vec.

Iterates over the slice other, clones each element, and then appends it to this vector. The other slice is traversed in-order.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::default();
vec.push(1);
vec.push(2);
vec.push(3);
assert_eq!(vec, [1, 2, 3]);

vec.extend_from_slice(&[4, 5, 6, 7]);
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

impl<'a, T: Clone + 'a> ImpVec<T>

pub fn extend<I: IntoIterator<Item = &'a T>>(&self, iter: I)

Clones and appends all elements in the iterator to the vec.

Iterates over the iter, clones each element, and then appends it to this vector.

Unlike std::vec::Vec or orx_split_vec::SplitVec; extend operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::default();
vec.push(1);
vec.push(2);
vec.push(3);
assert_eq!(vec, [1, 2, 3]);

vec.extend(&[4, 5, 6, 7]);
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

let sec_vec = ImpVec::default();
sec_vec.extend(vec.into_iter());
assert_eq!(sec_vec, [1, 2, 3, 4, 5, 6, 7]);

impl<T> ImpVec<T>

pub fn to_vec(self) -> Vec<T>

Converts the ImpVec into a standard Vec with a contagious memory layout.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::FragmentGrowth;

let imp_vec = ImpVec::with_growth(FragmentGrowth::constant(4));
imp_vec.extend_from_slice(&['a', 'b', 'c']);

assert_eq!(1, imp_vec.fragments().len());

let vec = imp_vec.to_vec();
assert_eq!(vec, &['a', 'b', 'c']);

let imp_vec = ImpVec::with_growth(FragmentGrowth::constant(4));
for i in 0..10 {
    imp_vec.push(i);
}
assert_eq!(&[0, 1, 2, 3], imp_vec.fragments()[0].as_slice());
assert_eq!(&[4, 5, 6, 7], imp_vec.fragments()[1].as_slice());
assert_eq!(&[8, 9], imp_vec.fragments()[2].as_slice());

let vec = imp_vec.to_vec();
assert_eq!(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], vec.as_slice());

impl<T> ImpVec<T>

pub fn with_growth(growth: FragmentGrowth) -> Self

Creates an empty imp-vector with the given growth strategy.

impl<T> ImpVec<T>

pub fn push(&self, value: T)

Appends an element to the back of a collection.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::default();
vec.push(1);
vec.push(2);

// since push does not require a mut reference,
// it is legal to hold on to other immutable references
// while pushing elements.
let ref_elem = &vec[1];
let ref_elem_addr = ref_elem as *const i32;
assert_eq!(2, *ref_elem);

vec.push(3);
vec.push(4);
vec.push(5);

assert_eq!(2, *ref_elem);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[1] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

pub fn push_get_ref(&self, value: T) -> &T

Appends an element to the back of a collection and returns a reference to it.

The reference will always be valid unless the collection is mutated; note that methods that grows the vector do not require a mutable reference, such as, push, push_get_ref, extend or extend_from_slice methods.

Examples

Hold on to valid references while pushing new items, as long as the collection is not mutated with methods such as insert, remove or pop.

use orx_split_vec::FragmentGrowth;
use orx_imp_vec::ImpVec;

let vec = ImpVec::with_growth(FragmentGrowth::constant(4));
let ref1 = vec.push_get_ref(1);
let ref_elem_addr = ref1 as *const i32;

vec.push(2);
vec.push(3);
let ref4 = vec.push_get_ref(4);

// capacity is expaneded here from 4 to 8; however, in chunks;
// therefore, data is not moved around and the references remain valid.
let ref5 = vec.push_get_ref(5);


assert_eq!(ref1, &1);
assert_eq!(ref4, &4);
assert_eq!(ref5, &5);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[0] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

As you may see below, any mutable method that can possibly invalidate the references are not allowed.

use orx_imp_vec::ImpVec;

let mut vec = ImpVec::default(); // mut required for the `insert`
let ref1 = vec.push_get_ref(1);
vec.push(2);
vec.push(3);

assert_eq!(ref1, &1);
assert_eq!(vec, [1, 2, 3]);

vec.insert(0, 42);
assert_eq!(vec, [42, 1, 2, 3]);

// below line does not compile as the 'insert' call breaks reference 'ref1'
// let value1 = *ref1;

Methods from Deref<Target = SplitVec<T>>

pub fn extend_from_slice(&mut self, other: &[T])

Clones and appends all elements in a slice to the vec.

Iterates over the slice other, clones each element, and then appends it to this vector. The other slice is traversed in-order.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
vec.push(1);
vec.push(2);
vec.push(3);
assert_eq!(vec, [1, 2, 3]);

vec.extend_from_slice(&[4, 5, 6, 7]);
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

pub fn push(&mut self, value: T)

Appends an element to the back of a collection.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
vec.push(1);
vec.push(2);
vec.push(3);
assert_eq!(vec, [1, 2, 3]);

pub fn pop(&mut self) -> Option<T>

Removes the last element from a vector and returns it, or None if it is empty.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
vec.push(1);
vec.push(2);
vec.push(3);

assert_eq!(vec.pop(), Some(3));
assert_eq!(vec, [1, 2]);

pub fn insert(&mut self, index: usize, value: T)

Inserts an element at position index within the vector, shifting all elements after it to the right.

Panics

Panics if index > len.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
vec.push(1);
vec.push(2);
vec.push(3);

vec.insert(1, 4);
assert_eq!(vec, [1, 4, 2, 3]);

vec.insert(4, 5);
assert_eq!(vec, [1, 4, 2, 3, 5]);

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

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Note: Because this shifts over the remaining elements, it has a worst-case performance of O(n).

Panics

Panics if index is out of bounds.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
vec.push(1);
vec.push(2);
vec.push(3);
vec.push(4);
vec.push(5);

assert_eq!(vec.remove(1), 2);
assert_eq!(vec, [1, 3, 4, 5]);

assert_eq!(vec.remove(2), 4);
assert_eq!(vec, [1, 3, 5]);

pub fn try_get_slice(&self, range: Range<usize>) -> SplitVecSlice<'_, T>

Returns the result of trying to return the required range as a contagious slice of data. It might return Ok of the slice if the range belongs to one fragment.

Otherwise, one of the two failure cases will be returned:

• OutOfBounds if the range does not fit in the range of the entire split vector, or
• Fragmented if the range belongs to at least two fragments, additionally returns the fragment indices of the range.

Examples

use orx_split_vec::{FragmentGrowth, SplitVec, SplitVecSlice};

let growth = FragmentGrowth::constant(4);
let mut vec = SplitVec::with_growth(growth);

vec.extend_from_slice(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

assert_eq!(4, vec.fragments()[0].capacity());
assert_eq!(4, vec.fragments()[1].capacity());
assert_eq!(4, vec.fragments()[2].capacity());

assert_eq!(4, vec.fragments()[0].len()); // [0, 1, 2, 3]
assert_eq!(4, vec.fragments()[1].len()); // [4, 5, 6, 7]
assert_eq!(2, vec.fragments()[2].len()); // [8, 9]

// Ok
assert_eq!(SplitVecSlice::Ok(&[0, 1, 2, 3]), vec.try_get_slice(0..4));
assert_eq!(SplitVecSlice::Ok(&[5, 6]), vec.try_get_slice(5..7));
assert_eq!(SplitVecSlice::Ok(&[8, 9]), vec.try_get_slice(8..10));

// Fragmented
assert_eq!(SplitVecSlice::Fragmented(0, 1), vec.try_get_slice(3..6));
assert_eq!(SplitVecSlice::Fragmented(0, 2), vec.try_get_slice(3..9));
assert_eq!(SplitVecSlice::Fragmented(1, 2), vec.try_get_slice(7..9));

// OutOfBounds
assert_eq!(SplitVecSlice::OutOfBounds, vec.try_get_slice(5..12));
assert_eq!(SplitVecSlice::OutOfBounds, vec.try_get_slice(10..11));

pub fn slice(&self, range: Range<usize>) -> Vec<&[T], Global>

Returns the view on the required range as a vector of slices:

• returns an empty vector if the range is out of bounds;
• returns a vector with one slice if the range completely belongs to one fragment (in this case try_get_slice would return Ok),
• returns an ordered vector of slices when chained forms the required range.

Examples

use orx_split_vec::{FragmentGrowth, SplitVec, SplitVecSlice};

let growth = FragmentGrowth::constant(4);
let mut vec = SplitVec::with_growth(growth);

vec.extend_from_slice(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

assert_eq!(4, vec.fragments()[0].capacity());
assert_eq!(4, vec.fragments()[1].capacity());
assert_eq!(4, vec.fragments()[2].capacity());

assert_eq!(4, vec.fragments()[0].len()); // [0, 1, 2, 3]
assert_eq!(4, vec.fragments()[1].len()); // [4, 5, 6, 7]
assert_eq!(2, vec.fragments()[2].len()); // [8, 9]

// single fragment
assert_eq!(vec![&[0, 1, 2, 3]], vec.slice(0..4));
assert_eq!(vec![&[5, 6]], vec.slice(5..7));
assert_eq!(vec![&[8, 9]], vec.slice(8..10));

// Fragmented
assert_eq!(vec![&vec![3], &vec![4, 5]], vec.slice(3..6));
assert_eq!(vec![&vec![3], &vec![4, 5, 6, 7], &vec![8]], vec.slice(3..9));
assert_eq!(vec![&vec![7], &vec![8]], vec.slice(7..9));

// OutOfBounds
assert!(vec.slice(5..12).is_empty());
assert!(vec.slice(10..11).is_empty());

pub unsafe fn fragments_mut(&mut self) -> &mut Vec<Fragment<T>, Global>

Returns a mutable reference to the vector of fragments.

Safety

Fragments of the split vector maintain the following structure:

• the fragments vector is never empty, it has at least one fragment;
• all fragments have a positive capacity;
  • capacity of fragment f is equal to self.growth.get_capacity(f).
• if there exist F fragments in the vector:
  • none of the fragments with indices 0..F-2 has capacity; i.e., len==capacity,
  • the last fragment at position F-1 might or might not have capacity.

Breaking this structure invalidates the SplitVec struct, and its methods lead to UB.

pub fn fragments(&self) -> &[Fragment<T>]

Returns the fragments of the split vector.

The fragments of the split vector satisfy the following structure:

• the fragments vector is never empty, it has at least one fragment;
• all fragments have a positive capacity;
  • capacity of fragment f is equal to self.growth.get_capacity(f).
• if there exist F fragments in the vector:
  • none of the fragments with indices 0..F-2 has capacity; i.e., len==capacity,
  • the last fragment at position F-1 might or might not have capacity.

Examples

use orx_split_vec::{FragmentGrowth, SplitVec};

let mut vec = SplitVec::with_growth(FragmentGrowth::constant(4));

for i in 0..6 {
    vec.push(i);
}

assert_eq!(2, vec.fragments().len());
assert_eq!(&[0, 1, 2, 3], vec.fragments()[0].as_slice());
assert_eq!(&[4, 5], vec.fragments()[1].as_slice());

pub fn last_fragment(&self) -> &Fragment<T>

Returns a reference to the last fragment of the split vector.

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

Returns the fragment index and the index within fragment of the item with the given index; None if the index is out of bounds.

Examples

use orx_split_vec::{FragmentGrowth, SplitVec};

let mut vec = SplitVec::with_growth(FragmentGrowth::constant(4));

for i in 0..6 {
    vec.push(i);
}

assert_eq!(&[0, 1, 2, 3], vec.fragments()[0].as_slice());
assert_eq!(&[4, 5], vec.fragments()[1].as_slice());

// first fragment
assert_eq!(Some((0, 0)), vec.fragment_and_inner_index(0));
assert_eq!(Some((0, 1)), vec.fragment_and_inner_index(1));
assert_eq!(Some((0, 2)), vec.fragment_and_inner_index(2));
assert_eq!(Some((0, 3)), vec.fragment_and_inner_index(3));

// second fragment
assert_eq!(Some((1, 0)), vec.fragment_and_inner_index(4));
assert_eq!(Some((1, 1)), vec.fragment_and_inner_index(5));

// out of bounds
assert_eq!(None, vec.fragment_and_inner_index(6));

pub fn len(&self) -> usize

Returns the number of elements in the vector, also referred to as its ‘length’.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
assert_eq!(0, vec.len());
vec.push(1);
vec.push(2);
vec.push(3);
assert_eq!(3, vec.len());

pub fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
assert!(vec.is_empty());
vec.push(1);
assert!(!vec.is_empty());

pub fn capacity(&self) -> usize

Returns the total number of elements the split vector can hold without reallocating.

See FragmentGrowth for details of capacity growth policies.

Examples

use orx_split_vec::SplitVec;

// default growth starting with 4, and doubling at each new fragment.
let mut vec = SplitVec::<usize>::default();
assert_eq!(4, vec.capacity());

for i in 0..4 {
    vec.push(i);
}
assert_eq!(4, vec.capacity());

vec.push(4);
assert_eq!(4 + 6, vec.capacity());

// second fragment will have capacity 4*1.5 by default growth
// see `FragmentGrowth` for different growth strategies.

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

Returns a reference to the element with the given index; None if index is out of bounds.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::<usize>::default();
vec.extend_from_slice(&[10, 40, 30]);
assert_eq!(Some(&40), vec.get(1));
assert_eq!(None, vec.get(3));

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

Returns a mutable reference to the element with the given index; None if index is out of bounds.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::<usize>::default();
vec.extend_from_slice(&[0, 1, 2]);

if let Some(elem) = vec.get_mut(1) {
    *elem = 42;
}

assert_eq!(vec, &[0, 42, 2]);

pub fn append<F>(&mut self, fragment: F)where F: Into<Fragment<T>>,

Directly appends the fragment to the end of the split vector.

This operation does not require any copies or allocation; the fragment is moved into the split vector and added as a new fragment, without copying the underlying data.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::<usize>::default();

// append to empty split vector
assert!(vec.is_empty());
let mut other = Vec::with_capacity(4);
other.extend_from_slice(&[0, 1, 2]);

vec.append(other);
assert_eq!(vec, &[0, 1, 2]);
assert_eq!(1, vec.fragments().len());
assert_eq!(4, vec.fragments()[0].capacity()); // SplitVec will make use of the appended vector's additional capacity

vec.push(3);
assert_eq!(vec, &[0, 1, 2, 3]);
assert_eq!(1, vec.fragments().len());
assert_eq!(vec.fragments()[0].as_slice(), &[0, 1, 2, 3]);

// next push will use SplitVec's growth
vec.extend_from_slice(&[4, 5, 6]);
assert_eq!(vec, &[0, 1, 2, 3, 4, 5, 6]);
assert_eq!(2, vec.fragments().len());
assert_eq!(vec.fragments()[0].as_slice(), &[0, 1, 2, 3]);
assert_eq!(vec.fragments()[1].as_slice(), &[4, 5, 6]);

// we can append another fragment directly
vec.append(vec![7, 8]);
assert_eq!(vec, &[0, 1, 2, 3, 4, 5, 6, 7, 8]);
assert_eq!(3, vec.fragments().len());
assert_eq!(vec.fragments()[0].as_slice(), &[0, 1, 2, 3]);
assert_eq!(vec.fragments()[1].as_slice(), &[4, 5, 6]);
assert_eq!(vec.fragments()[2].as_slice(), &[7, 8]);

pub fn clear(&mut self)

Clears the vector, removing all values.

This method:

• drops all fragments except for the first one, and
• clears the first fragment.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();
for _ in 0..10 {
    vec.push(4.2);
}

vec.clear();

assert!(vec.is_empty());

Trait Implementations

impl<T: Debug> Debug for ImpVec<T>

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

Formats the value using the given formatter.

impl<T> Default for ImpVec<T>

fn default() -> Self

Creates an empty imp-vector with the default FragmentGrowth strategy.

impl<T> Deref for ImpVec<T>

type Target = SplitVec<T>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T> DerefMut for ImpVec<T>

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<T> From<ImpVec<T>> for SplitVec<T>

fn from(value: ImpVec<T>) -> Self

Converts a ImpVec into a SplitVec by moving out the split vector from the imp-vector, without copying the data.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::SplitVec;

let imp_vec = ImpVec::default();
imp_vec.push(0);
imp_vec.push(1);

let mut split_vec: SplitVec<_> = imp_vec.into();
assert_eq!(split_vec, &[0, 1]);

split_vec.push(2);
assert_eq!(split_vec, &[0, 1, 2]);

impl<T> From<ImpVec<T>> for Vec<T>

fn from(value: ImpVec<T>) -> Self

Converts the ImpVec into a standard Vec with a contagious memory layout.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::FragmentGrowth;

let imp_vec = ImpVec::with_growth(FragmentGrowth::constant(4));
imp_vec.extend_from_slice(&['a', 'b', 'c']);

assert_eq!(1, imp_vec.fragments().len());

let vec: Vec<_> = imp_vec.into();
assert_eq!(vec, &['a', 'b', 'c']);

let imp_vec = ImpVec::with_growth(FragmentGrowth::constant(4));
for i in 0..10 {
    imp_vec.push(i);
}
assert_eq!(&[0, 1, 2, 3], imp_vec.fragments()[0].as_slice());
assert_eq!(&[4, 5, 6, 7], imp_vec.fragments()[1].as_slice());
assert_eq!(&[8, 9], imp_vec.fragments()[2].as_slice());

let vec: Vec<_> = imp_vec.into();
assert_eq!(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], vec.as_slice());

impl<T> From<SplitVec<T>> for ImpVec<T>

fn from(value: SplitVec<T>) -> Self

Converts a SplitVec into a ImpVec by moving the split-vector into the imp-vector, without copying the data.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::SplitVec;

let vec = vec!['a', 'b', 'c'];
let vec_capacity = vec.capacity();

let mut split_vec = SplitVec::default(); // required mut to push
split_vec.push(0);
split_vec.push(1);

let imp_vec: ImpVec<_> = split_vec.into(); // can push w/o mut ref
assert_eq!(imp_vec, &[0, 1]);

imp_vec.push(2);
assert_eq!(imp_vec, &[0, 1, 2]);

impl<T> From<Vec<T, Global>> for ImpVec<T>

fn from(value: Vec<T>) -> Self

Converts a Vec into a ImpVec by moving the vector into the split vector as the first fragment, without copying the data, and converting the split vector into an imp-vec.

Examples

use orx_imp_vec::ImpVec;

let vec = vec!['a', 'b', 'c'];
let vec_capacity = vec.capacity();

let imp_vec: ImpVec<_> = vec.into();

assert_eq!(imp_vec, &['a', 'b', 'c']);
assert_eq!(1, imp_vec.fragments().len());
assert_eq!(vec_capacity, imp_vec.fragments()[0].capacity());

impl<T: PartialEq> PartialEq<ImpVec<T>> for ImpVec<T>

fn eq(&self, other: &ImpVec<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 !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialEq, U> PartialEq<U> for ImpVec<T>where U: AsRef<[T]>,

fn eq(&self, other: &U) -> 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 !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialEq> Eq for ImpVec<T>