Struct orx_split_vec::ExponentialGrowth

pub struct ExponentialGrowth { /* private fields */ }

Stategy which allows new fragments grow exponentially.

The capacity of the n-th fragment is computed as cap0 * pow(growth_coefficient, n) where cap0 is the capacity of the first fragment.

Note that DoublingGrowth is a special case of ExponentialGrowth with growth_coefficient equal to 2, while providing a faster access by index.

On the other hand, exponential growth allows for fitting growth strategies for fitting situations which could be a better choice when memory allocation is more important than index access complexity.

As you may see in the example below, it is especially useful in providing exponential growth rates slower than the doubling.

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

Examples

use orx_split_vec::SplitVec;

// SplitVec<usize, ExponentialGrowth>
let mut vec = SplitVec::with_exponential_growth(2, 1.5);

assert_eq!(1, vec.fragments().len());
assert_eq!(Some(2), 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![2, 3, 4, 6, 9, 13];
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((13 as f32 * 1.5) as usize));
assert_eq!(vec.fragments().last().map(|f| f.len()), Some(1));

Implementations

impl ExponentialGrowth

pub fn new(growth_coefficient: f32) -> Self

Creates a new exponential growth strategy with the given growth_coefficient.

The capacity of the n-th fragment is computed as cap0 * pow(growth_coefficient, n) where cap0 is the capacity of the first fragment.

Panics

Panics if growth_coefficient is less than 1.0.

pub fn growth_coefficient(&self) -> f32

Returns the coefficient of the exponential growth strategy.

Trait Implementations

impl Clone for ExponentialGrowth

fn clone(&self) -> ExponentialGrowth

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ExponentialGrowth

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

Formats the value using the given formatter.

impl Default for ExponentialGrowth

fn default() -> Self

Creates a default exponential growth strategy with growth_coefficient being equal to 1.5.

impl PartialEq<ExponentialGrowth> for ExponentialGrowth

fn eq(&self, other: &ExponentialGrowth) -> 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> SplitVecGrowth<T> for ExponentialGrowth

fn new_fragment_capacity(&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( &self, fragments: &[Fragment<T>], element_index: usize ) -> Option<(usize, usize)>

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

impl StructuralPartialEq for ExponentialGrowth