Struct orx_split_vec::SplitVec

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

A split vector; i.e., a vector of fragments.

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: 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 fn with_growth(growth: FragmentGrowth) -> Self

Creates an empty split vector with the given growth strategy.

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.

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.

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

Trait Implementations

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

Returns the “default value” for a type.

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