Struct Recursive

pub struct Recursive;

Equivalent to Doubling strategy except for the following:

• enables zero-cost (no-ops) append operation:
  • we can append standard vectors, vectors of vectors, split vectors, etc., any data that implements IntoFragments trait,
  • by simply accepting it as a whole fragment,
  • according to benchmarks documented in the crate definition:
    • SplitVec<_, Recursive> is infinitely faster than other growth strategies or standard vector :)
    • since its time complexity is independent of size of the data to be appended.
• at the expense of providing slower random-access performance:
  • random access time complexity of Doubling strategy is constant time;
  • that of Recursive strategy is linear in the number of fragments;
  • according to benchmarks documented in the crate definition:
    • SplitVec<_, Doubling> or standard vector are around 4 to 7 times faster than SplitVec<_, Recursive>,
    • and 1.5 times faster when the elements get very large (16 x u64).

Note that other operations such as serial access are equivalent to Doubling strategy.

Examples

use orx_split_vec::*;

// SplitVec<usize, Recursive>
let mut vec = SplitVec::with_recursive_growth();

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

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

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

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

Trait Implementations

impl Clone for Recursive

fn clone(&self) -> Recursive

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Recursive

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

Formats the value using the given formatter.

impl Default for Recursive

fn default() -> Recursive

Returns the “default value” for a type.

impl Growth for Recursive

fn new_fragment_capacity_from( &self, fragment_capacities: impl ExactSizeIterator<Item = usize>, ) -> usize

Given that the split vector contains fragments with the given fragment_capacities, returns the capacity of the next fragment.

fn maximum_concurrent_capacity<T>( &self, fragments: &[Fragment<T>], fragments_capacity: usize, ) -> usize

Returns the maximum number of elements that can safely be stored in a concurrent program.

fn required_fragments_len<T>( &self, fragments: &[Fragment<T>], maximum_capacity: usize, ) -> Result<usize, String>

Returns the number of fragments with this growth strategy in order to be able to reach a capacity of maximum_capacity of elements. Returns the error if it the growth strategy does not allow the required number of fragments.

fn maximum_concurrent_capacity_bound<T>( &self, fragments: &[Fragment<T>], fragments_capacity: usize, ) -> usize

Returns the maximum possible bound on concurrent capacity.

fn first_fragment_capacity(&self) -> usize

Given that the split vector has no fragments yet, returns the capacity of the first fragment.

fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize

Given that the split vector contains the given fragments, returns the capacity of the next fragment.

fn get_fragment_and_inner_indices<T>( &self, _vec_len: usize, fragments: &[Fragment<T>], element_index: usize, ) -> Option<(usize, usize)>

O(fragments.len()) Returns the location of the element with the given element_index on the split vector as a tuple of (fragment-index, index-within-fragment).

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

O(fragments.len()) Returns a mutable reference to the index-th element of the split vector of the fragments.

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

O(fragments.len()) Returns a mutable reference to the index-th element of the split vector of the fragments.

fn get_ptr_and_indices<T>( &self, fragments: &[Fragment<T>], index: usize, ) -> Option<(*const T, usize, usize)>

O(fragments.len()) Returns a mutable reference to the index-th element of the split vector of the fragments together with the index of the fragment that the element belongs to and index of the element withing the respective fragment.

fn get_ptr_mut_and_indices<T>( &self, fragments: &mut [Fragment<T>], index: usize, ) -> Option<(*mut T, usize, usize)>

O(fragments.len()) Returns a mutable reference to the index-th element of the split vector of the fragments together with the index of the fragment that the element belongs to and index of the element withing the respective fragment.

impl JaggedIndexer for Recursive

unsafe fn jagged_index_unchecked<'a, T>( &self, arrays: &impl Slices<'a, T>, flat_index: usize, ) -> JaggedIndex

where T: 'a,

Returns the jagged index of the element flat_index-th position if the raw jagged array defined by the arrays collection would have been flattened.

unsafe fn jagged_index_unchecked_from_slice<'a, T>( &self, arrays: &[impl AsRawSlice<T>], flat_index: usize, ) -> JaggedIndex

where T: 'a,

Returns the jagged index of the element flat_index-th position if the raw jagged array defined by the arrays collection would have been flattened.

impl PartialEq for Recursive

fn eq(&self, other: &Recursive) -> 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 PseudoDefault for Recursive

fn pseudo_default() -> Recursive

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

impl StructuralPartialEq for Recursive