Struct orx_split_vec::prelude::SplitVec

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

Implementations

impl<T> SplitVec<T, Doubling>

pub fn with_doubling_growth() -> Self

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

// SplitVec<usize, Doubling>
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));

pub fn with_doubling_growth_and_fragments_capacity( fragments_capacity: usize, ) -> Self

Creates a new split vector with Doubling growth and initial fragments_capacity.

This method differs from SplitVec::with_doubling_growth only by the pre-allocation of fragments collection. Note that this (only) important for concurrent programs:

• SplitVec already keeps all elements pinned to their locations;
• Creating a buffer for storing the meta information is important for keeping the meta information pinned as well. This is relevant and important for concurrent programs.

Panics

Panics if fragments_capacity == 0.

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 not within:

• 1..32 for 64-bit platforms, or
• 1..29 for 32-bit platforms.

Examples

use orx_split_vec::*;

// SplitVec<usize, Linear>
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()));

pub fn with_linear_growth_and_fragments_capacity( constant_fragment_capacity_exponent: usize, fragments_capacity: usize, ) -> Self

Creates a new split vector with Linear growth and initial fragments_capacity.

This method differs from SplitVec::with_linear_growth only by the pre-allocation of fragments collection. Note that this (only) important for concurrent programs:

• SplitVec already keeps all elements pinned to their locations;
• Creating a buffer for storing the meta information is important for keeping the meta information pinned as well. This is relevant and important for concurrent programs.

Panics

Panics if fragments_capacity == 0.

impl<T> SplitVec<T, Recursive>

pub fn append<I: IntoFragments<T>>(&mut self, other: I)

Consumes and appends other vector into this vector in constant time without memory copies.

Example

use orx_split_vec::*;

let mut recursive = SplitVec::with_recursive_growth();

recursive.push('a');
assert_eq!(recursive, &['a']);

recursive.append(vec!['b', 'c']);
assert_eq!(recursive, &['a', 'b', 'c']);

recursive.append(vec![vec!['d'], vec!['e', 'f']]);
assert_eq!(recursive, &['a', 'b', 'c', 'd', 'e', 'f']);

let other_split_vec: SplitVec<_> = vec!['g', 'h'].into();
recursive.append(other_split_vec);
assert_eq!(recursive, &['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);

impl<T> SplitVec<T, Recursive>

pub fn with_recursive_growth() -> Self

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

Notice that this is similar to the Doubling growth strategy. However, Recursive and Doubling strategies have the two following important differences in terms of performance:

• Random access by indices is much faster with Doubling.
• Recursive strategy enables copy-free append method which merges another vector to this vector in constant time.

All other operations are expected to have similar complexity.

Random Access

• Doubling strategy provides a constant time access by random indices.
• Recursive strategy provides a random access time complexity that is linear in the number of fragments. Note that this is significantly faster than the linear-in-number-of-elements complexity of linked lists; however, significantly slower than the Doubling strategy’s constant time.

Append

• Recursive strategy provides append operation which allows merging two vectors in constant time without copies.

SplitVec::append method should not be confused with std::vec::Vec::append method:

• The split vector version consumes the vector to be appended. It takes advantage of its split nature and appends the other vector simply by owning its pointer. In other words, the other vector is appended to this vector with no cost and no copies.
• The standard vector version mutates the vector to be appended, moving all its element to the first vector leaving the latter empty. This operation is carried out by memory copies.

Examples

use orx_split_vec::*;

// SplitVec<usize, Doubling>
let mut vec = SplitVec::with_recursive_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));

pub fn with_recursive_growth_and_fragments_capacity( fragments_capacity: usize, ) -> Self

Creates a new split vector with Recursive growth and initial fragments_capacity.

This method differs from SplitVec::with_recursive_growth only by the pre-allocation of fragments collection. Note that this (only) important for concurrent programs:

• SplitVec already keeps all elements pinned to their locations;
• Creating a buffer for storing the meta information is important for keeping the meta information pinned as well. This is relevant and important for concurrent programs.

Panics

Panics if fragments_capacity == 0.

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

where G: Growth,

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

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

Examples

use orx_split_vec::*;

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

#[derive(Clone)]
pub struct DoubleEverySecondFragment(usize); // any custom growth strategy

impl PseudoDefault for DoubleEverySecondFragment {
    fn pseudo_default() -> Self {
        DoubleEverySecondFragment(1)
    }
}

impl Growth for DoubleEverySecondFragment {
    fn new_fragment_capacity_from(&self, fragment_capacities: impl ExactSizeIterator<Item = usize>) -> usize {
        let num_fragments = fragment_capacities.len();
        fragment_capacities
            .last()
            .map(|f| {
                let do_double = num_fragments % 2 == 0;
                if do_double {
                    f * 2
                } else {
                    f
                }
            })
            .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<R: RangeBounds<usize>>( &self, range: R, ) -> 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::*;

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

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

where G: Growth,

pub fn growth(&self) -> &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 strategy 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:

• Linear (SplitVec::with_linear_growth) -> O(1)
• Doubling (SplitVec::with_doubling_growth) -> O(1)
• Recursive (SplitVec::with_recursive_growth) -> O(f) where f is the number of fragments; and O(1) append time complexity

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

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 maximum_concurrent_capacity(&self) -> usize

Maximum capacity that can safely be reached by the vector in a concurrent program. This value is often related with the capacity of the container holding meta information about allocations. Note that the split vector can naturally grow beyond this number, this bound is only relevant when the vector is Synced among threads.

pub fn concurrent_reserve( &mut self, maximum_capacity: usize, ) -> Result<usize, String>

Makes sure that the split vector can safely reach the given maximum_capacity in a concurrent program.

• returns Ok of the new maximum capacity if the vector succeeds to reserve.
• returns the corresponding error message otherwise.

Note that this method does not allocate the maximum_capacity, it only ensures that the concurrent growth to this capacity is safe. In order to achieve this, it might need to extend allocation of the fragments collection. However, note that by definition number of fragments is insignificant in a split vector.

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

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

pub fn reserve_maximum_concurrent_capacity( &mut self, new_maximum_capacity: usize, ) -> usize

Makes sure that the split vector can safely reach the given maximum_capacity in a concurrent program.

Returns new maximum capacity.

Note that this method does not allocate the maximum_capacity, it only ensures that the concurrent growth to this capacity is safe. In order to achieve this, it might need to extend allocation of the fragments collection. However, note that by definition number of fragments is insignificant in a split vector.

Trait Implementations

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

where T: Clone, G: Growth,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

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> From<SplitVec<T>> for SplitVec<T, Recursive>

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

Converts a SplitVec<T, Doubling> into a SplitVec<T, Recursive> with no cost.

• The benefit of Doubling growth strategy is its constant random access time.
• On the other hand, the benefit of Recursive growth strategy is the constant time expand operation.

Note that this is a one-way conversion:

• it is possible to convert any split vec SplitVec<T, Doubling> into SplitVec<T, Recursive>;
• however, not the other way around, since constant random access time requirements of Doubling are not satisfied.

Examples

use orx_split_vec::*;

let mut split_vec_doubling = SplitVec::with_doubling_growth();
split_vec_doubling.extend_from_slice(&['a', 'b', 'c']);
assert_eq!(split_vec_doubling, &['a', 'b', 'c']);

let split_vec_recursive: SplitVec<_, Recursive> = split_vec_doubling.into();
assert_eq!(split_vec_recursive, &['a', 'b', 'c']);

impl<T, G: GrowthWithConstantTimeAccess> From<SplitVec<T, G>> for ConcurrentSplitVec<T, G>

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

Converts to this type from the input type.

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

where G: Growth,

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

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

If the split vector is composed of only one fragment, it is immediately returned as a Vec without any cost.

Examples

use orx_split_vec::*;

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> From<SplitVec<T, Linear>> for SplitVec<T, Recursive>

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

Converts a SplitVec<T, Doubling> into a SplitVec<T, Recursive> with no cost.

• The benefit of Doubling growth strategy is its constant random access time.
• On the other hand, the benefit of Recursive growth strategy is the constant time expand operation.

Note that this is a one-way conversion:

• it is possible to convert any split vec SplitVec<T, Doubling> into SplitVec<T, Recursive>;
• however, not the other way around, since constant random access time requirements of Doubling are not satisfied.

Examples

use orx_split_vec::*;

let mut split_vec_linear = SplitVec::with_linear_growth(4);
split_vec_linear.extend_from_slice(&['a', 'b', 'c']);
assert_eq!(split_vec_linear, &['a', 'b', 'c']);

let split_vec_recursive: SplitVec<_, Recursive> = split_vec_linear.into();
assert_eq!(split_vec_recursive, &['a', 'b', 'c']);

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

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

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: Clone> From<Vec<T>> for SplitVec<T, Recursive>

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

Converts a Vec into a SplitVec.

Examples

use orx_split_vec::*;

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

let split_vec: SplitVec<_, Recursive> = 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: Growth> FromIterator<T> for SplitVec<T, G>

where SplitVec<T, G>: Default,

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

Creates a value from an iterator.

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

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

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

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

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, G: GrowthWithConstantTimeAccess> IntoConcurrentPinnedVec<T> for SplitVec<T, G>

type ConPinnedVec = ConcurrentSplitVec<T, G>

Type of the concurrent pinned vector wrapper.

fn into_concurrent(self) -> Self::ConPinnedVec

Converts the pinned vector into its concurrent wrapper.

fn into_concurrent_filled_with<F>(self, fill_with: F) -> Self::ConPinnedVec

where F: Fn() -> T,

Converts the pinned vector into its concurrent wrapper. During conversion:

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

fn into_fragments(self) -> impl Iterator<Item = Fragment<T>>

Converts self into a collection of Fragments.

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

type Item = T

The type of the elements being iterated over.

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

where G: Growth,

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

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

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

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

impl<T: PartialEq, G, const N: usize> PartialEq<SplitVec<T, G>> for [T; N]

where G: Growth,

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

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

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

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

impl<T: PartialEq, G> PartialEq<SplitVec<T, G>> for Vec<T>

where G: Growth,

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

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

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

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

impl<T, G, U> PartialEq<U> for SplitVec<T, G>

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

fn eq(&self, other: &U) -> bool

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

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

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

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

where G: Growth,

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

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

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

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

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

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 << vec.len() 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::*;

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 index_of_ptr(&self, element_ptr: *const T) -> Option<usize>

Returns the index of the element of the vector that the element_ptr points to. This method has O(f) time complexity where f << vec.len() 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.

fn contains_reference(&self, element: &T) -> bool

Returns whether or not the element with the given reference belongs to the vector. This method has O(f) time complexity where f << vec.len() is the number of fragments.

Note that T: Eq is not required; memory address is used.

Safety

Since FixedVec 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::*;

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

assert!(vec.contains_reference(&vec[0]));
assert!(vec.contains_reference(&vec[1]));
assert!(vec.contains_reference(&vec[2]));
assert!(vec.contains_reference(&vec[3]));

// num certainly does not belong to `vec`
let num = 42;
assert!(!vec.contains_reference(&num));

// even if its value belongs
let num = 20;
assert!(!vec.contains_reference(&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!(!vec.contains_reference(&eq_vec[i]));
}

fn contains_ptr(&self, element_ptr: *const T) -> bool

Returns whether or not the element with the given pointer belongs to the vector. This method has O(f) time complexity where f << vec.len() is the number of fragments.

Note that T: Eq is not required; memory address is used.

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

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

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

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

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

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 sub-slice, 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 sub-slice, 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.

fn first(&self) -> Option<&T>

Returns a reference to the first element of the vector; returns None if the vector is empty.

Examples

use orx_split_vec::*;

let mut vec = SplitVec::new();
assert!(vec.first().is_none());

vec.push(42);
assert_eq!(Some(&42), vec.first());

vec.push(864121);
assert_eq!(Some(&42), vec.first());

vec.insert(0, 7);
assert_eq!(Some(&7), vec.first());

fn last(&self) -> Option<&T>

Returns a reference to the last element of the vector; returns None if the vector is empty.

Examples

use orx_split_vec::*;

let mut vec = SplitVec::new();
assert!(vec.last().is_none());

vec.push(42);
assert_eq!(Some(&42), vec.last());

vec.push(7);
assert_eq!(Some(&7), vec.last());

vec.insert(0, 684321);
assert_eq!(Some(&7), vec.last());

fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Examples

use orx_split_vec::*;

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

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

fn push(&mut self, value: T)

Appends an element to the back of a collection.

Examples

use orx_split_vec::*;

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

fn slices<R: RangeBounds<usize>>(&self, range: R) -> Self::SliceIter<'_>

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

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

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

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

fn slices_mut<R: RangeBounds<usize>>( &mut self, range: R, ) -> Self::SliceMutIter<'_>

Returns a mutable 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!(vec.fragments()[0], &[0, 1, 2, 3]);
assert_eq!(vec.fragments()[1], &[4, 5, 6, 7]);
assert_eq!(vec.fragments()[2], &[8, 9]);

// single fragment
let mut slices = vec.slices_mut(0..4);
assert_eq!(slices.len(), 1);
assert_eq!(slices[0], &[0, 1, 2, 3]);
slices[0][1] *= 10;
assert_eq!(vec.fragments()[0], &[0, 10, 2, 3]);

// single fragment - partially
let mut slices = vec.slices_mut(5..7);
assert_eq!(slices.len(), 1);
assert_eq!(slices[0], &[5, 6]);
slices[0][1] *= 10;
assert_eq!(vec.fragments()[1], &[4, 5, 60, 7]);

// multiple fragments
let slices = vec.slices_mut(2..6);
assert_eq!(slices.len(), 2);
assert_eq!(slices[0], &[2, 3]);
assert_eq!(slices[1], &[4, 5]);
for s in slices {
    for x in s {
        *x *= 10;
    }
}

assert_eq!(vec.fragments()[0], &[0, 10, 20, 30]);
assert_eq!(vec.fragments()[1], &[40, 50, 60, 7]);
assert_eq!(vec.fragments()[2], &[8, 9]);

// out of bounds
assert!(vec.slices_mut(5..12).is_empty());
assert!(vec.slices_mut(10..11).is_empty());

fn get_ptr(&self, index: usize) -> Option<*const T>

Returns a pointer to the index-th element of the vector.

Returns None if index-th position does not belong to the vector; i.e., if index is out of capacity.

Time complexity of the method is:

• O(1) when G: GrowthWithConstantTimeAccess,
• O(f) for the general case G: Growth where f is the number of fragments in the split vector.

Safety

This method allows to write to a memory which is greater than the vector’s length. On the other hand, it will never return a pointer to a memory location that the vector does not own.

fn get_ptr_mut(&mut self, index: usize) -> Option<*mut T>

Returns a mutable pointer to the index-th element of the vector.

Returns None if index-th position does not belong to the vector; i.e., if index is out of capacity.

Time complexity of the method is:

• O(1) when G: GrowthWithConstantTimeAccess,
• O(f) for the general case G: Growth where f is the number of fragments in the split vector.

Safety

This method allows to write to a memory which is greater than the vector’s length. On the other hand, it will never return a pointer to a memory location that the vector does not own.

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

Iterator yielding references to the elements of the vector.

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

Iterator yielding mutable references to the elements of the vector.

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

Iterator yielding references to the elements of the vector.

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

Iterator yielding mutable references to the elements of the vector.

type SliceIter<'a> = Vec<&'a [T]> where T: 'a, Self: 'a

Iterator yielding slices corresponding to a range of indices, returned by the slice method.

type SliceMutIter<'a> = Vec<&'a mut [T]> where T: 'a, Self: 'a

Iterator yielding mutable slices corresponding to a range of indices, returned by the slice_mut and slice_mut_unchecked methods.

fn push_get_ptr(&mut self, value: T) -> *const T

Appends an element to the back of a collection and returns a pointer to its position in the vector.

unsafe fn iter_ptr<'v, 'i>(&'v self) -> impl Iterator<Item = *const T> + 'i

where T: 'i,

Creates an iterator of the pointers to the elements of the vec.

unsafe fn iter_ptr_rev<'v, 'i>(&'v self) -> impl Iterator<Item = *const T> + 'i

where T: 'i,

Creates a reverse iterator of the pointers to the elements of the vec, starting from the last element to the first.

fn capacity_state(&self) -> CapacityState

Provides detailed information of capacity state of the pinned vector.

unsafe fn first_unchecked(&self) -> &T

Returns a reference to the first element of the vector without bounds checking.

unsafe fn last_unchecked(&self) -> &T

Returns a reference to the last element of the vector without bounds checking.

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.

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

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

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.

fn swap(&mut self, a: usize, b: usize)

Swaps two elements in the slice.

fn truncate(&mut self, len: usize)

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

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

Returns an iterator to elements of the vector.

fn iter_mut(&mut self) -> Self::IterMut<'_>

Returns an iterator of mutable references to elements of the vector.

fn iter_rev(&self) -> Self::IterRev<'_>

Returns a reversed back-to-front iterator to elements of the vector.

fn iter_mut_rev(&mut self) -> Self::IterMutRev<'_>

Returns a reversed back-to-front iterator mutable references to elements of the vector.

unsafe fn set_len(&mut self, new_len: usize)

Forces the length of the vector to new_len.

fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>

where F: FnMut(&T) -> Ordering,

Binary searches vector slice with a comparator function.

fn sort(&mut self)

where T: Ord,

Sorts the vector.

fn sort_by<F>(&mut self, compare: F)

where F: FnMut(&T, &T) -> Ordering,

Sorts the slice with a comparator function.

fn sort_by_key<K, F>(&mut self, f: F)

where F: FnMut(&T) -> K, K: Ord,

Sorts the slice with a key extraction function.

fn binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize>

where F: FnMut(&T) -> B, B: Ord,

Binary searches this vector with a key extraction function.

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

fn pseudo_default() -> Self

PseudoDefault trait allows to create a cheap default instance of a type, which does not claim to be useful.

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