Struct orx_split_vec::SplitVec

pub struct SplitVec<T> {
    pub growth: FragmentGrowth,
    /* private fields */
}

A split vector; i.e., a vector of fragments, with 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.

Fields

growth: FragmentGrowth

Fragment growth strategy of the split vector.

Implementations

impl<T> SplitVec<T>

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

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

Examples

use orx_split_vec::{FragmentGrowth, SplitVec};

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

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

let vec = split_vec.to_vec(); // no mem-copies
assert_eq!(vec, &['a', 'b', 'c']);

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

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

impl<T> SplitVec<T>

pub fn with_growth(growth: FragmentGrowth) -> Self

Creates an empty split vector with the given growth strategy.

impl<T: Clone> 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]);

impl<T> SplitVec<T>

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

impl<T> SplitVec<T>

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

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

impl<T> SplitVec<T>

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

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

impl<T> SplitVec<T>

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: Clone> Clone for SplitVec<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SplitVec<T>

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

Formats the value using the given formatter.

impl<T> Default for SplitVec<T>

fn default() -> Self

Creates an empty split vector with the default FragmentGrowth strategy.

impl<'a, T: Clone + 'a> Extend<&'a T> for SplitVec<T>

fn extend<I: IntoIterator<Item = &'a T>>(&mut 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.

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(&[4, 5, 6, 7]);
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

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

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> Extend<T> for SplitVec<T>

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

Extends a collection with the contents of an iterator.

Iterates over the iter, moves and appends each element to this vector.

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(vec![4, 5, 6, 7].into_iter());
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T> From<&'a SplitVec<T>> for SplitVecIterator<'a, T>

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

Converts to this type from the input type.

impl<T> From<SplitVec<T>> for Vec<T>

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

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

Examples

use orx_split_vec::{FragmentGrowth, SplitVec};

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

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

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

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

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

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

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

Converts a Vec into a SplitVec by moving the vector into the split vector as the first fragment, without copying the data.

Examples

use orx_split_vec::SplitVec;

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

let split_vec: SplitVec<_> = vec.into();

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

impl<T> Index<(usize, usize)> for SplitVec<T>

fn index(&self, fragment_and_inner_index: (usize, usize)) -> &Self::Output

One can treat the split vector as a jagged array and access an item with (fragment_index, inner_fragment_index) if these numbers are known.

Panics

Panics if:

• fragment_and_inner_index.0 is not a valid fragment index; i.e., not within 0..self.fragments().len(), or
• fragment_and_inner_index.1 is not a valid index for the corresponding fragment; i.e., not within 0..self.fragments()[fragment_and_inner_index.0].len().

Examples

Assume that we create a split vector with a constant growth of N elements. This means that each fraction will have a capacity and max-length of N.

Then, the fragment and inner index of the element with index i can be computed as (i / N, i % N).

use orx_split_vec::{FragmentGrowth, SplitVec};

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

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

// layout of the data will be as follows:
// fragment-0: [0, 1, 2, 3]
// fragment-1: [4, 5, 6, 7]
// fragment-2: [8, 9]

assert_eq!(1, vec[(0, 1)]);
assert_eq!(7, vec[(1, 3)]);
assert_eq!(8, vec[(2, 0)]);

// since we know the layout, we can define the index transformer for direct access
fn fragment_and_inner_idx(index: usize) -> (usize, usize) {
    (index / 4, index % 4)
}

for index in 0..vec.len() {
    let split_access = &vec[index];
    let direct_access = &vec[fragment_and_inner_idx(index)];
    assert_eq!(split_access, direct_access);
}

type Output = T

The returned type after indexing.

impl<T> Index<usize> for SplitVec<T>

fn index(&self, index: usize) -> &Self::Output

Returns a reference to the index-th item of the vector.

Panics

Panics if index is out of bounds.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();

vec.extend_from_slice(&[0, 1, 2, 3]);

assert_eq!(&1, &vec[1]);
assert_eq!(&3, &vec[3]);
// let x = &vec[4]; // panics!

type Output = T

The returned type after indexing.

impl<T> IndexMut<(usize, usize)> for SplitVec<T>

fn index_mut( &mut self, fragment_and_inner_index: (usize, usize) ) -> &mut Self::Output

One can treat the split vector as a jagged array and access an item with (fragment_index, inner_fragment_index) if these numbers are known.

Panics

Panics if:

• fragment_and_inner_index.0 is not a valid fragment index; i.e., not within 0..self.fragments().len(), or
• fragment_and_inner_index.1 is not a valid index for the corresponding fragment; i.e., not within 0..self.fragments()[fragment_and_inner_index.0].len().

Examples

Assume that we create a split vector with a constant growth of N elements. This means that each fraction will have a capacity and max-length of N.

Then, the fragment and inner index of the element with index i can be computed as (i / N, i % N).

use orx_split_vec::{FragmentGrowth, SplitVec};

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

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

// layout of the data will be as follows:
// fragment-0: [0, 1, 2, 3]
// fragment-1: [4, 5, 6, 7]
// fragment-2: [8, 9]

vec[(0, 1)] += 100; // 1 -> 101
vec[(1, 3)] += 100; // 7 -> 107
vec[(2, 0)] += 100; // 8 -> 108
assert_eq!(vec, &[0, 101, 2, 3, 4, 5, 6, 107, 108, 9]);

// since we know the layout, we can define the index transformer for direct access
fn fragment_and_inner_idx(index: usize) -> (usize, usize) {
    (index / 4, index % 4)
}

for index in 0..vec.len() {
    let direct_access = &mut vec[fragment_and_inner_idx(index)];
    if *direct_access < 100 {
        *direct_access += 100;
    }
}
assert_eq!(vec, &[100, 101, 102, 103, 104, 105, 106, 107, 108, 109]);

impl<T> IndexMut<usize> for SplitVec<T>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Returns a mutable reference to the index-th item of the vector.

Panics

Panics if index is out of bounds.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::default();

vec.extend_from_slice(&[0, 1, 2, 3]);

let item2 = &mut vec[2];
*item2 = 42;
assert_eq!(vec, &[0, 1, 42, 3]);

// let x = &mut vec[4]; // panics!

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

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = SplitVecIterator<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq<SplitVec<T>> for SplitVec<T>

fn eq(&self, other: &SplitVec<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 SplitVec<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 SplitVec<T>