Struct sized_chunks::sparse_chunk::SparseChunk

pub struct SparseChunk<A, N: Bits + ChunkLength<A> = U64> { /* private fields */ }

A fixed capacity sparse array.

An inline sparse array of up to N items of type A, where N is an Unsigned type level numeral. You can think of it as an array of Option<A>, where the discriminant (whether the value is Some<A> or None) is kept in a bitmap instead of adjacent to the value.

Because the bitmap is kept in a primitive type, the maximum value of N is currently 128, corresponding to a type of u128. The type of the bitmap will be the minimum unsigned integer type required to fit the number of bits required. Thus, disregarding memory alignment rules, the allocated size of a SparseChunk will be uX + A * N where uX is the type of the discriminant bitmap, either u8, u16, u32, u64 or u128.

Examples

// Construct a chunk with a 20 item capacity
let mut chunk = SparseChunk::<i32, U20>::new();
// Set the 18th index to the value 5.
chunk.insert(18, 5);
// Set the 5th index to the value 23.
chunk.insert(5, 23);

assert_eq!(chunk.len(), 2);
assert_eq!(chunk.get(5), Some(&23));
assert_eq!(chunk.get(6), None);
assert_eq!(chunk.get(18), Some(&5));

Implementations

impl<A, N> SparseChunk<A, N> where
    N: Bits + ChunkLength<A>, 

pub const CAPACITY: usize

The maximum number of elements a SparseChunk can contain.

pub fn new() -> Self

Construct a new empty chunk.

pub fn unit(index: usize, value: A) -> Self

Construct a new chunk with one item.

pub fn pair(index1: usize, value1: A, index2: usize, value2: A) -> Self

Construct a new chunk with two items.

pub fn len(&self) -> usize

Get the length of the chunk.

pub fn is_empty(&self) -> bool

Test if the chunk is empty.

pub fn is_full(&self) -> bool

Test if the chunk is at capacity.

pub fn insert(&mut self, index: usize, value: A) -> Option<A>

Insert a new value at a given index.

Returns the previous value at that index, if any.

pub fn remove(&mut self, index: usize) -> Option<A>

Remove the value at a given index.

Returns the value, or None if the index had no value.

pub fn pop(&mut self) -> Option<A>

Remove the first value present in the array.

Returns the value that was removed, or None if the array was empty.

pub fn get(&self, index: usize) -> Option<&A>

Get the value at a given index.

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

Get a mutable reference to the value at a given index.

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

Get an unchecked reference to the value at a given index.

Safety

Uninhabited indices contain uninitialised data, so make sure you validate the index before using this method.

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

Get an unchecked mutable reference to the value at a given index.

Safety

Uninhabited indices contain uninitialised data, so make sure you validate the index before using this method.

pub fn indices(&self) -> BitmapIter<'_, N>

Make an iterator over the indices which contain values.

pub fn first_index(&self) -> Option<usize>

Find the first index which contains a value.

pub fn iter(&self) -> Iter<'_, A, N>

Make an iterator of references to the values contained in the array.

pub fn iter_mut(&mut self) -> IterMut<'_, A, N>

Make an iterator of mutable references to the values contained in the array.

pub fn drain(self) -> Drain<A, N>

Turn the chunk into an iterator over the values contained within it.

pub fn entries(&self) -> impl Iterator<Item = (usize, &A)>

Make an iterator of pairs of indices and references to the values contained in the array.

pub fn option_iter(&self) -> OptionIter<'_, A, N>

Make an iterator of Options of references to the values contained in the array.

Iterates over every index in the SparseChunk, from zero to its full capacity, returning an Option<&A> for each index.

pub fn option_iter_mut(&mut self) -> OptionIterMut<'_, A, N>

Make an iterator of Options of mutable references to the values contained in the array.

Iterates over every index in the SparseChunk, from zero to its full capacity, returning an Option<&mut A> for each index.

pub fn option_drain(self) -> OptionDrain<A, N>

Make a draining iterator of `Option’s of the values contained in the array.

Iterates over every index in the SparseChunk, from zero to its full capacity, returning an Option<A> for each index.

Trait Implementations

impl<A: Clone, N: Bits + ChunkLength<A>> Clone for SparseChunk<A, N>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A, N> Debug for SparseChunk<A, N> where
    A: Debug,
    N: Bits + ChunkLength<A>, 

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

Formats the value using the given formatter.

impl<A, N: Bits + ChunkLength<A>> Default for SparseChunk<A, N>

fn default() -> Self

Returns the “default value” for a type.

impl<A, N: Bits + ChunkLength<A>> Drop for SparseChunk<A, N>

fn drop(&mut self)

Executes the destructor for this type.

impl<A, N: Bits + ChunkLength<A>> FromIterator<Option<A>> for SparseChunk<A, N>

fn from_iter<I>(iter: I) -> Self where
    I: IntoIterator<Item = Option<A>>, 

Creates a value from an iterator.

impl<A, N: Bits + ChunkLength<A>> Index<usize> for SparseChunk<A, N>

type Output = A

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<A, N: Bits + ChunkLength<A>> IndexMut<usize> for SparseChunk<A, N>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<A, N: Bits + ChunkLength<A>> IntoIterator for SparseChunk<A, N>

type Item = A

The type of the elements being iterated over.

type IntoIter = Drain<A, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A, N> PartialEq<BTreeMap<usize, A>> for SparseChunk<A, N> where
    A: PartialEq,
    N: Bits + ChunkLength<A>, 

fn eq(&self, other: &BTreeMap<usize, A>) -> 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 !=.

impl<A, N> PartialEq<HashMap<usize, A, RandomState>> for SparseChunk<A, N> where
    A: PartialEq,
    N: Bits + ChunkLength<A>, 

fn eq(&self, other: &HashMap<usize, A>) -> 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 !=.

impl<A, N> PartialEq<SparseChunk<A, N>> for SparseChunk<A, N> where
    A: PartialEq,
    N: Bits + ChunkLength<A>, 

fn eq(&self, other: &Self) -> 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 !=.

impl<A, N> Eq for SparseChunk<A, N> where
    A: Eq,
    N: Bits + ChunkLength<A>,