Struct orx_split_vec::SplitVec

pub struct SplitVec<T, G = Doubling>
where
    G: Growth,
{
    pub growth: G,
    /* 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: G

Growth strategy of the split vector.

Note that allocated data of split vector is pinned and allocated in fragments. Therefore, growth does not require copying data.

The growth stratety determines the capacity of each fragment that will be added to the split vector when needed.

Furthermore, it has an impact on index-access to the elements. See below for the complexities:

• LinearGrowth (SplitVec::with_linear_growth) -> O(1)
• DoublingGrowth (SplitVec::with_doubling_growth) -> O(1), however slower than linear
• ExponentialGrowth (SplitVec::with_exponential_growth) -> O(f) where f is the number of fragments
• CustomGrowth (SplitVec::with_custom_growth) -> O(f) where f is the number of fragments

Implementations

impl<T> SplitVec<T, Doubling>

pub fn with_doubling_growth() -> Self

Stategy which allows to create a fragment with double the capacity of the prior fragment every time the split vector needs to expand.

Assuming it is the common case compared to empty vector scenarios, it immediately allocates the first fragment to keep the SplitVec struct smaller.

Panics

Panics if first_fragment_capacity is zero.

Examples

use orx_split_vec::prelude::*;

// SplitVec<usize, DoublingGrowth>
let mut vec = SplitVec::with_doubling_growth();

assert_eq!(1, vec.fragments().len());
assert_eq!(Some(4), vec.fragments().first().map(|f| f.capacity()));
assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));

// fill the first 5 fragments
let expected_fragment_capacities = vec![4, 8, 16, 32];
let num_items: usize = expected_fragment_capacities.iter().sum();
for i in 0..num_items {
    vec.push(i);
}

assert_eq!(
    expected_fragment_capacities,
    vec.fragments()
    .iter()
    .map(|f| f.capacity())
    .collect::<Vec<_>>()
);
assert_eq!(
    expected_fragment_capacities,
    vec.fragments().iter().map(|f| f.len()).collect::<Vec<_>>()
);

// create the 6-th fragment doubling the capacity
vec.push(42);
assert_eq!(
    vec.fragments().len(),
    expected_fragment_capacities.len() + 1
);

assert_eq!(vec.fragments().last().map(|f| f.capacity()), Some(32 * 2));
assert_eq!(vec.fragments().last().map(|f| f.len()), Some(1));

impl<T> SplitVec<T, Linear>

pub fn with_linear_growth(constant_fragment_capacity_exponent: usize) -> Self

Creates a split vector with linear growth where each fragment will have a capacity of 2 ^ constant_fragment_capacity_exponent.

Assuming it is the common case compared to empty vector scenarios, it immediately allocates the first fragment to keep the SplitVec struct smaller.

Panics

Panics if constant_fragment_capacity_exponent is zero.

Examples

use orx_split_vec::prelude::*;

// SplitVec<usize, LinearGrowth>
let mut vec = SplitVec::with_linear_growth(4);

assert_eq!(1, vec.fragments().len());
assert_eq!(Some(16), vec.fragments().first().map(|f| f.capacity()));
assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));

// push 160 elements
for i in 0..10 * 16 {
    vec.push(i);
}

assert_eq!(10, vec.fragments().len());
for fragment in vec.fragments() {
    assert_eq!(16, fragment.len());
    assert_eq!(16, fragment.capacity());
}

// push the 161-st element
vec.push(42);
assert_eq!(11, vec.fragments().len());
assert_eq!(Some(16), vec.fragments().last().map(|f| f.capacity()));
assert_eq!(Some(1), vec.fragments().last().map(|f| f.len()));

impl<T, G> SplitVec<T, G>

where G: Growth, T: NotSelfRefVecItem,

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

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

Examples

use orx_split_vec::prelude::*;

let mut split_vec = SplitVec::with_linear_growth(2);
split_vec.extend_from_slice(&['a', 'b', 'c']);

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

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

let mut split_vec = SplitVec::with_linear_growth(2);
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, G> SplitVec<T, G>

where G: Growth, T: NotSelfRefVecItem + Clone,

pub fn collect_fixed_vec(&self) -> FixedVec<T>

Collects the split vector into a fixed vector with a fixed capacity being exactly equal to the length of this split vector.

Safety

Since T: NotSelfRefVecItem, it is safe to clone the data of the elements.

Examples

use orx_split_vec::prelude::*;

// SplitVec with dynamic capacity and configurable growth strategy.
let mut split = SplitVec::with_linear_growth(5);
for i in 0..35 {
    split.push(i);
}
assert_eq!(35, split.len());
assert_eq!(2, split.fragments().len());
assert_eq!(32, split.fragments()[0].len());
assert_eq!(3, split.fragments()[1].len());

// FixedVec with std::vec::Vec complexity & performance.
let fixed = split.collect_fixed_vec();
assert_eq!(35, fixed.len());
assert_eq!(fixed, split);

impl<T, G> SplitVec<T, G>

where G: Growth, T: Clone,

pub unsafe fn unsafe_collect_fixed_vec(&self) -> FixedVec<T>

Collects the split vector into a fixed vector with a fixed capacity being exactly equal to the length of this split vector.

Safety

Since T is not a NotSelfRefVecItem, it is assumed as a SelfRefVecItem to be conservative. A naive clone of a vector of SelfRefVecItem elements is unsafe due to the following scenario:

• say the vector contains two elements ['a', 'b'] where 'a' holds a reference to 'b'.
• when we clone this vector, element 'a' of the second vector will be pointing to element 'b' of the first vector, which is already incorrect.
• furthermore, if the first vector is dropped, the abovementioned reference will be an dangling reference leading to UB.

Therefore, cloning elements of a vector where elements are not NotSelfRefVecItem is unsafe.

impl<T> SplitVec<T>

pub fn new() -> Self

Creates an empty split vector with default growth strategy.

Default growth strategy is Doubling with initial capacity of 4.

Examples

use orx_split_vec::*;

let vec: SplitVec<f32> = SplitVec::new();

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

impl<T, G> SplitVec<T, G>

where G: Growth,

pub fn with_growth(growth: G) -> Self

Creates an empty split vector with the given growth strategy.

This constructor is especially useful to define custom growth strategies.

Examples

use orx_split_vec::prelude::*;

#[derive(Clone)]
pub struct DoubleEverySecondFragment(usize); // any custom growth strategy
impl Growth for DoubleEverySecondFragment {
    fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize {
        fragments
            .last()
            .map(|f| {
                let do_double = fragments.len() % 2 == 0;
                if do_double {
                    f.capacity() * 2
                } else {
                    f.capacity()
                }
            })
            .unwrap_or(self.0)
    }
}
let mut vec = SplitVec::with_growth(DoubleEverySecondFragment(8));
for i in 0..17 {
    vec.push(i);
}

assert_eq!(3, vec.fragments().len());

assert_eq!(8, vec.fragments()[0].capacity());
assert_eq!(8, vec.fragments()[0].len());

assert_eq!(8, vec.fragments()[1].capacity());
assert_eq!(8, vec.fragments()[1].len());

assert_eq!(16, vec.fragments()[2].capacity());
assert_eq!(1, vec.fragments()[2].len());

impl<T, G: Growth> SplitVec<T, G>

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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, G> SplitVec<T, G>

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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 get_fragment_and_inner_indices( &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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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.get_fragment_and_inner_indices(0));
assert_eq!(Some((0, 1)), vec.get_fragment_and_inner_indices(1));
assert_eq!(Some((0, 2)), vec.get_fragment_and_inner_indices(2));
assert_eq!(Some((0, 3)), vec.get_fragment_and_inner_indices(3));

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

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

Trait Implementations

impl<T, G> Debug for SplitVec<T, G>

where T: Debug, G: Growth,

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

Formats the value using the given formatter.

impl<T, G> Default for SplitVec<T, G>

where G: Growth + Default,

fn default() -> Self

Creates an empty split vector with the default FragmentGrowth strategy.

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

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(4);
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::with_linear_growth(4);
sec_vec.extend(vec.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, G> Extend<T> for SplitVec<T, G>

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(4);
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<T, G> From<SplitVec<T, G>> for Vec<T>

where G: Growth, T: NotSelfRefVecItem,

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

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

Examples

use orx_split_vec::prelude::*;

let mut split_vec = SplitVec::with_linear_growth(2);
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_linear_growth(2);
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: Clone> From<Vec<T>> for SplitVec<T, Doubling>

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

Converts a Vec into a SplitVec.

Examples

use orx_split_vec::prelude::*;

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

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

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

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

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::prelude::*;

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

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

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

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

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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, G> Index<usize> for SplitVec<T, G>

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(4);

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, G> IndexMut<(usize, usize)> for SplitVec<T, G>

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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, G> IndexMut<usize> for SplitVec<T, G>

where G: Growth,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);

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<T: PartialEq, G> PartialEq<SplitVec<T, G>> for [T]

where G: Growth,

fn eq(&self, other: &SplitVec<T, G>) -> 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, G, const N: usize> PartialEq<SplitVec<T, G>> for [T; N]

where G: Growth,

fn eq(&self, other: &SplitVec<T, G>) -> 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, G: Growth> PartialEq<SplitVec<T, G>> for FixedVec<T>

fn eq(&self, other: &SplitVec<T, G>) -> 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, G> PartialEq<SplitVec<T, G>> for Vec<T>

where G: Growth,

fn eq(&self, other: &SplitVec<T, G>) -> 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, G, U> PartialEq<U> for SplitVec<T, G>

where U: AsRef<[T]>, T: PartialEq, G: Growth,

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, G> PartialEq for SplitVec<T, G>

where G: Growth,

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

where G: Growth,

fn index_of(&self, element: &T) -> Option<usize>

Returns the index of the element with the given reference. This method has O(f) time complexity where f is the number of fragments.

Note that T: Eq is not required; reference equality is used.

Safety

Since SplitVec implements PinnedVec, the underlying memory of the vector stays pinned; i.e., is not carried to different memory locations. Therefore, it is possible and safe to compare an element’s reference to find its position in the vector.

Examples

use orx_split_vec::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);
for i in 0..4 {
    vec.push(10 * i);
}

assert_eq!(Some(0), vec.index_of(&vec[0]));
assert_eq!(Some(1), vec.index_of(&vec[1]));
assert_eq!(Some(2), vec.index_of(&vec[2]));
assert_eq!(Some(3), vec.index_of(&vec[3]));

// the following does not compile since vec[4] is out of bounds
// assert_eq!(Some(3), vec.index_of(&vec[4]));

// num certainly does not belong to `vec`
let num = 42;
assert_eq!(None, vec.index_of(&num));

// even if its value belongs
let num = 20;
assert_eq!(None, vec.index_of(&num));

// as expected, querying elements of another vector will also fail
let eq_vec = vec![0, 10, 20, 30];
for i in 0..4 {
    assert_eq!(None, vec.index_of(&eq_vec[i]));
}

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::prelude::*;

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

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

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

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::prelude::*;

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

vec.clear();

assert!(vec.is_empty());

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

where T: Clone,

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(4);
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]);

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::prelude::*;

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

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::prelude::*;

let mut vec = SplitVec::with_linear_growth(5);
vec.extend_from_slice(&[0, 1, 2]);

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

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

unsafe fn get_unchecked(&self, index: usize) -> &T

Returns a reference to an element or subslice, without doing bounds checking.

For a safe alternative see get.

Safety

Calling this method with an out-of-bounds index is [undefined behavior] even if the resulting reference is not used.

unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T

Returns a mutable reference to an element or subslice, without doing bounds checking.

For a safe alternative see get_mut.

Safety

Calling this method with an out-of-bounds index is [undefined behavior] even if the resulting reference is not used.

unsafe fn unsafe_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::prelude::*;

let mut vec = SplitVec::with_linear_growth(16);
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]);

Safety

If the element type is not a NotSelfRefVecItem; in other words, if the elements hold references of each other, insert method might invalidate the references. This method is then called unsafe_insert.

Consider the following struct which is not a NotSelfRefVecItem:

struct Node<'a, T> {
    value: T,
    related_to: Option<&'a Node<'a, T>>,
}

Further, assume we build a vector of two nodes [x, y], where each node is related to the other x <--> y.

If we insert another node w at index 0, the vector takes the form [w, x, y] causing the following problems:

• x is related to the node at position 1, which is itself: x -> x.
• y is realted to the node at position 0, which is w: y -> w.

Both relations are wrong after insertion.

For this reason, insertions when T is a self-referencing-vector-item are unsafe and the caller is responsible for correcting the references if it needs to use this method.

fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Examples

use orx_split_vec::prelude::*;

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

fn len(&self) -> usize

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

Examples

use orx_split_vec::prelude::*;

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

unsafe fn unsafe_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::prelude::*;

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

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

Safety

If the element type is not a NotSelfRefVecItem; in other words, if the elements hold references of each other, pop method might invalidate the references. This method is then called unsafe_pop.

Consider the following struct which is not a NotSelfRefVecItem:

struct Node<'a, T> {
    value: T,
    related_to: Option<&'a Node<'a, T>>,
}

Further, assume we build a vector of two nodes [x, y], where each node is related to the other x <--> y.

If we pop y from the vector, leaving the vector as [x]:

• y still correctly points to the node at position 0, which is x.
• However, y points to the node at position 1 which is does not belong to the vector now causing an undefined behavior.

For this reason, popping when T is a self-referencing-vector-item is unsafe and the caller is responsible for correcting the references if it needs to use this method.

fn push(&mut self, value: T)

Appends an element to the back of a collection.

Examples

use orx_split_vec::prelude::*;

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

unsafe fn unsafe_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::prelude::*;

let mut vec = SplitVec::with_linear_growth(16);
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]);

Safety

If the element type is not a NotSelfRefVecItem; in other words, if the elements hold references of each other, remove method might invalidate the references. This method is then called unsafe_remove.

Consider the following struct which is not a NotSelfRefVecItem:

struct Node<'a, T> {
    value: T,
    related_to: Option<&'a Node<'a, T>>,
}

Further, assume we build a vector of two nodes [x, y], where each node is related to the other x <--> y.

If we remove the element at position 0; i.e., x from the vector, leaving the vector as [y]:

• y points to the node at position 0, which is itself: y -> y.
• Furthermore, x points to the node at position 1 which is does not belong to the vector now causing an undefined behavior.

For this reason, removals when T is a self-referencing-vector-item are unsafe and the caller is responsible for correcting the references if it needs to use this method.

unsafe fn unsafe_swap(&mut self, a: usize, b: usize)

Swaps the two elements of the vector with at the given positions ‘a’ and ‘b’.

Panics

Panics if either of the indices a or ‘b’ is out of bounds.

Examples

use orx_split_vec::prelude::*;

let mut vec = SplitVec::with_linear_growth(2);
vec.push(1);    // fragment 0
vec.push(2);    // fragment 0
vec.push(10);   // fragment 1
vec.push(20);   // fragment 1
vec.push(100);  // fragment 2
assert_eq!(vec, [1, 2, 10, 20, 100]);

// this is a regular vec.swap
vec.swap(0, 1);
assert_eq!(vec, [2, 1, 10, 20, 100]);

// this is inter-fragments swap; i.e., mem:swap
vec.swap(1, 4);
assert_eq!(vec, [2, 100, 10, 20, 1]);

Safety

If the element type is not a NotSelfRefVecItem; in other words, if the elements hold references of each other, swap method might invalidate the references. This method is then called unsafe_remove.

Consider the following struct which is not a NotSelfRefVecItem:

struct Node<'a, T> {
    value: T,
    related_to: Option<&'a Node<'a, T>>,
}

Further, assume we build a vector of two nodes [x, y, z], where each node is related to the next one: x --> y --> z.

If we swap elements at positions 1 and 2, the vector becomes [x, z, y]. But now,

• x still points to position 1 which is now occupied by z;
• y still points to position 2 which is now occupied by itself.

This does not cause an undefined behavior in the classical sense; however, the meaning of the vector and relations are broken.

For this reason, swaps when T is a self-referencing-vector-item are unsafe and the caller is responsible for correcting the references if it needs to use this method.

unsafe fn unsafe_truncate(&mut self, len: usize)

Shortens the vector, keeping the first len elements and dropping the rest.

If len is greater than the vector’s current length, this has no effect.

Examples

use orx_split_vec::prelude::*;

fn get_vec() -> SplitVec<usize, Linear> {
    let mut vec = SplitVec::with_linear_growth(4);
    for i in 0..11 {
        vec.push(i);
    }
    // [ [0,1,2,3], [4,5,6,7], [8,9,10] ]
    vec
}

let mut vec = get_vec();
vec.truncate(100);
assert_eq!(vec, (0..11).collect::<Vec<_>>());

for i in 0..11 {
    let mut vec = get_vec();
    vec.truncate(i);
    assert_eq!(vec, (0..i).collect::<Vec<_>>());
}

Safety

This operation is unsafe when T is not NotSelfRefVecItem. To pick the conservative approach, every T which does not implement NotSelfRefVecItem is assumed to be a vector item referencing other vector items.

truncate is unsafe since it is possible that remaining elements are referencing to elements which are dropped by the truncate method.

On the other hand, any vector implementing PinnedVec<T> where T: NotSelfRefVecItem implements PinnedVecSimple<T> which implements the safe version of this method.

type Iter<'a> = Iter<'a, T> where T: 'a, Self: 'a

Iterator yielding references to the elements of the vector.

fn partial_eq<S>(&self, other: S) -> bool

where S: AsRef<[T]>, T: PartialEq,

This method tests for self and other values to be equal, and is used by ==.

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

where T: Debug,

Formats the value using the given formatter.

unsafe fn unsafe_clone(&self) -> Self

where T: Clone,

Creates and returns a clone of the vector.

fn iter(&self) -> Self::Iter<'_>

Returns an iterator to elements of the vector.

impl<T: PartialEq, G: Growth> Eq for SplitVec<T, G>