Struct orx_imp_vec::ImpVec

pub struct ImpVec<T, G = LinearGrowth>where
    G: SplitVecGrowth<T>,{ /* private fields */ }

ImpVec stands for ‘immutable-push-vec’.

It uses orx_split_vec::SplitVec as the underlying data structure, and hence, has 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.

In addition, it allows to push/extend the vector with an immutable reference.

This allows to hold on the references of already pushed elements while building the collection.

Implementations

impl<T: Clone, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

pub fn extend_from_slice(&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.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::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<'a, T: Clone + 'a, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

pub fn extend<I: IntoIterator<Item = &'a T>>(&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.

Unlike std::vec::Vec or orx_split_vec::SplitVec; extend operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::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 sec_vec = ImpVec::default();
sec_vec.extend(vec.into_iter());
assert_eq!(sec_vec, [1, 2, 3, 4, 5, 6, 7]);

impl<T, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

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

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

Examples

use orx_imp_vec::ImpVec;

let imp_vec = ImpVec::with_linear_growth(4);
imp_vec.extend_from_slice(&['a', 'b', 'c']);

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

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

let imp_vec = ImpVec::with_linear_growth(4);
for i in 0..10 {
    imp_vec.push(i);
}
assert_eq!(&[0, 1, 2, 3], imp_vec.fragments()[0].as_slice());
assert_eq!(&[4, 5, 6, 7], imp_vec.fragments()[1].as_slice());
assert_eq!(&[8, 9], imp_vec.fragments()[2].as_slice());

let vec = imp_vec.to_vec();
assert_eq!(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], vec.as_slice());

impl<T, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

pub fn with_growth(growth: G) -> Self

Creates an empty imp-vector with the given growth strategy.

impl<T> ImpVec<T, LinearGrowth>

pub fn with_linear_growth(constant_fragment_capacity: usize) -> Self

Creates an imp-vector with linear growth and given constant_fragment_capacity.

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

Panics

Panics if constant_fragment_capacity is zero.

Examples

use orx_imp_vec::ImpVec;

// ImpVec<usize, LinearGrowth>
let vec = ImpVec::with_linear_growth(16);

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> ImpVec<T, DoublingGrowth>

pub fn with_doubling_growth(first_fragment_capacity: usize) -> Self

Creates an imp-vector with doubling growth which creates 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 underlying SplitVec struct smaller.

Panics

Panics if first_fragment_capacity is zero.

Examples

use orx_imp_vec::ImpVec;

// ImpVec<usize, DoublingGrowth>
let vec = ImpVec::with_doubling_growth(2);

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, 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> ImpVec<T, ExponentialGrowth>

pub fn with_exponential_growth( first_fragment_capacity: usize, growth_coefficient: f32 ) -> Self

Creates an imp-vector 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.

Panics

Panics if first_fragment_capacity is zero, or if growth_coefficient is less than 1.0.

Examples

use orx_imp_vec::ImpVec;

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

impl<T> ImpVec<T, CustomGrowth<T>>

pub fn with_custom_growth_function( get_capacity_of_new_fragment: Rc<dyn Fn(&[Fragment<T>]) -> usize> ) -> Self

Creates an imp vector with the custom grwoth strategy defined by the function get_capacity_of_new_fragment.

Examples

use orx_split_vec::Fragment;
use orx_imp_vec::ImpVec;
use std::rc::Rc;

// vec: SplitVec<usize, CustomGrowth<usize>>
let vec =
    ImpVec::with_custom_growth_function(Rc::new(|fragments: &[Fragment<_>]| {
        if fragments.len() % 2 == 0 {
            2
        } else {
            8
        }
    }));

    for i in 0..100 {
        vec.push(i);
    }

    vec.into_iter().zip(0..100).all(|(l, r)| *l == r);
     
    for (f, fragment) in vec.fragments().iter().enumerate() {
        if f % 2 == 0 {
            assert_eq!(2, fragment.capacity());
        } else {
            assert_eq!(8, fragment.capacity());
        }
    }

impl<T> ImpVec<T, FixedCapacity>

pub fn with_fixed_capacity(fixed_capacity: usize) -> Self

Creates an imp-vector with the given fixed_capacity.

This capacity is the hard limit and the vector cannot grow beyond it. Attempts to exceed this limit will lead to the code to panic.

The benefit of this strategy, on the other hand, is its faster access by index operations; which must be inlined and have a comparable performance with regular slice access by index.

Further, the pinned-memory-location of already pushed elements feature is maintained.

Examples

use orx_imp_vec::ImpVec;

// SplitVec<usize, FixedCapacity>
let vec = ImpVec::with_fixed_capacity(4);

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

// push 4 elements to fill the vector completely
for i in 0..4 {
    vec.push(i);
}
assert_eq!(1, vec.fragments().len());

// the next push exceeding the fixed_capacity will panic.
// vec.push(4);

impl<T, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

pub fn push(&self, value: T)

Appends an element to the back of a collection.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::default();
vec.push(1);
vec.push(2);

// since push does not require a mut reference,
// it is legal to hold on to other immutable references
// while pushing elements.
let ref_elem = &vec[1];
let ref_elem_addr = ref_elem as *const i32;
assert_eq!(2, *ref_elem);

vec.push(3);
vec.push(4);
vec.push(5);

assert_eq!(2, *ref_elem);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[1] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

pub fn push_get_ref(&self, value: T) -> &T

Appends an element to the back of a collection and returns a reference to it.

The reference will always be valid unless the collection is mutated; note that methods that grows the vector do not require a mutable reference, such as, push, push_get_ref, extend or extend_from_slice methods.

Examples

Hold on to valid references while pushing new items, as long as the collection is not mutated with methods such as insert, remove or pop.

use orx_imp_vec::ImpVec;

let vec = ImpVec::with_linear_growth(4);
let ref1 = vec.push_get_ref(1);
let ref_elem_addr = ref1 as *const i32;

vec.push(2);
vec.push(3);
let ref4 = vec.push_get_ref(4);

// capacity is expaneded here from 4 to 8; however, in chunks;
// therefore, data is not moved around and the references remain valid.
let ref5 = vec.push_get_ref(5);


assert_eq!(ref1, &1);
assert_eq!(ref4, &4);
assert_eq!(ref5, &5);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[0] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

As you may see below, any mutable method that can possibly invalidate the references are not allowed.

use orx_imp_vec::ImpVec;

let mut vec = ImpVec::default(); // mut required for the `insert`
let ref1 = vec.push_get_ref(1);
vec.push(2);
vec.push(3);

assert_eq!(ref1, &1);
assert_eq!(vec, [1, 2, 3]);

vec.insert(0, 42);
assert_eq!(vec, [42, 1, 2, 3]);

// below line does not compile as the 'insert' call breaks reference 'ref1'
// let value1 = *ref1;

impl<T, G> ImpVec<T, G>where G: SplitVecGrowth<T>,

pub unsafe fn get_mut(&self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element at the given index, returns None if the index is out of bounds.

Unlike standard vector or SplitVec, this operation does not require a mut reference.

Safety

The following are the reasons why the access is safe:

• Due to the guarantees of the underlying SplitVec, pushed elements are pinned to their memory location unless a method requiring a mut reference to the vector is called. These are the methods that would lead to changing positions of existing elements such as insert, remove, pop or clear. On the other hand, pushing to or extending the imp-vec does not affect already added elements’ memory locations. Therefore, whenever, we access an element with the given index, we are sure that we are accessing the correct element. Further, we are sure that the obtained mutable reference will be valid and targeting the correct data.

• Mutation of the element is handled over an internal RefCell which would provide the guarantees that there will only be one mutable borrow at a time; the code will panic otherwise.

The method is still marked unsafe due to the following reasons:

• It makes it easy to have cyclic references which is often useful in cyclic data structures. However, the implementer needs to be careful for certain errors. Default implementations of traits such as Debug or PartialEq could easily lead to stackoverflows. See ImpNode struct which is a wrapper around the data to be stored in an imp-vec while avoiding such problems.

• It is possible to hold an immutable reference to, say, the i-th element of the vector. Assume that the value of the element is ‘x’ at the time the reference is created. At the same time, it is also possible to get a mutable reference to the i-th element and mutate its value to ‘y’. Finally, we can dereference the prior immutable reference just to read the data as ‘y’. This is confusing, and hence, scope of these mutations should be kept limited; ideally, only while building a data structure which requires this feature. On the other hand, it is safe to dereference the prior immutable reference, the reference cannot be invalid due to the guarantees discussed above. A similar example is demonstrated below.

Examples

use orx_imp_vec::ImpVec;

let vec = ImpVec::with_linear_growth(4);

for i in 0..21 {
    vec.push(i);
}
let immut_ref_7 = &vec[7];
assert_eq!(7, *immut_ref_7);

for i in 0..21 {
    *unsafe{ vec.get_mut(i) }.unwrap() *= 100;
}

for i in 0..21 {
    assert_eq!(100 * i, vec[i]);
}
assert_eq!(700, *immut_ref_7);

Methods from Deref<Target = SplitVec<T, G>>

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

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::with_linear_growth(16);
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::with_linear_growth(16);
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::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]);

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

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::{SplitVec, SplitVecSlice};

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

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], Global>

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::{SplitVec, SplitVecSlice};

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

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

pub unsafe fn fragments_mut(&mut self) -> &mut Vec<Fragment<T>, Global>

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

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

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

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

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 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::with_linear_growth(8);
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::with_linear_growth(2);
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::with_doubling_growth(4);
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());

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::with_linear_growth(32);
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::with_linear_growth(32);
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 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::SplitVec;

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

vec.clear();

assert!(vec.is_empty());

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.

This method is not available for SplitVec<_, LinearGrowth> and SplitVec<_, DoublingGrowth> since those variants exploit the closed form formula to speed up element accesses by index.

Examples

use orx_split_vec::SplitVec;

let mut vec = SplitVec::with_exponential_growth(8, 1.5);

// 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, G> Debug for ImpVec<T, G>where G: SplitVecGrowth<T> + Debug,

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

Formats the value using the given formatter.

impl<T> Default for ImpVec<T>

fn default() -> Self

Creates an empty imp-vector with the default FragmentGrowth strategy.

impl<T, G> Deref for ImpVec<T, G>where G: SplitVecGrowth<T>,

type Target = SplitVec<T, G>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T, G> DerefMut for ImpVec<T, G>where G: SplitVecGrowth<T>,

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<T, G> From<ImpVec<T, G>> for SplitVec<T, G>where G: SplitVecGrowth<T>,

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

Converts an ImpVec into a SplitVec by simply moving out the split vector from the imp-vector without copying the data.

Growth strategy is preserved.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::{SplitVec, LinearGrowth};

let imp_vec = ImpVec::with_linear_growth(10);
imp_vec.push(0);
imp_vec.push(1);

let mut split_vec: SplitVec<_, LinearGrowth> = imp_vec.into();
assert_eq!(split_vec, &[0, 1]);

split_vec.push(2);
assert_eq!(split_vec, &[0, 1, 2]);

impl<T, G> From<ImpVec<T, G>> for Vec<T>where G: SplitVecGrowth<T>,

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

Converts the ImpVec into a standard std::vec::Vec with a contagious memory layout.

Examples

use orx_imp_vec::ImpVec;

let imp_vec = ImpVec::with_linear_growth(4);
imp_vec.extend_from_slice(&['a', 'b', 'c']);

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

let vec: Vec<_> = imp_vec.into();
assert_eq!(vec, &['a', 'b', 'c']);

let imp_vec = ImpVec::with_linear_growth(4);
for i in 0..10 {
    imp_vec.push(i);
}
assert_eq!(&[0, 1, 2, 3], imp_vec.fragments()[0].as_slice());
assert_eq!(&[4, 5, 6, 7], imp_vec.fragments()[1].as_slice());
assert_eq!(&[8, 9], imp_vec.fragments()[2].as_slice());

let vec: Vec<_> = imp_vec.into();
assert_eq!(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], vec.as_slice());

impl<T, G> From<SplitVec<T, G>> for ImpVec<T, G>where G: SplitVecGrowth<T>,

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

Converts a SplitVec into a ImpVec by moving the split-vector into the imp-vector, without copying the data.

Examples

use orx_imp_vec::ImpVec;
use orx_split_vec::SplitVec;

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

let mut split_vec = SplitVec::default(); // required mut to push
split_vec.push(0);
split_vec.push(1);

let imp_vec: ImpVec<_> = split_vec.into(); // can push w/o mut ref
assert_eq!(imp_vec, &[0, 1]);

imp_vec.push(2);
assert_eq!(imp_vec, &[0, 1, 2]);

impl<T, G> From<Vec<T, Global>> for ImpVec<T, G>where G: SplitVecGrowth<T>, SplitVec<T, G>: From<Vec<T>>,

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

Converts a Vec into an ImpVec by first moving the vector into the underlying split vector as the first fragment without copying the data, and then converting the SplitVec into ImpVec.

Examples

use orx_imp_vec::ImpVec;

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

let split_vec: ImpVec<_> = 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: PartialEq> PartialEq<ImpVec<T, LinearGrowth>> for ImpVec<T>

fn eq(&self, other: &ImpVec<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 ImpVec<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 ImpVec<T>