Struct ArrayStump

pub struct ArrayStump<T, C>
where
    C: Fn(&T, &T) -> Ordering,
{ /* private fields */ }

The core data structure representing a two-level sorted stump.

Implementations

impl<T, C> ArrayStump<T, C>

where C: Fn(&T, &T) -> Ordering, T: Clone + Debug,

pub fn new(comparator: C) -> ArrayStump<T, C>

Creates a new ArrayStump instance.

pub fn new_explicit(comparator: C, init_capacity: u16) -> ArrayStump<T, C>

Creates a new ArrayStump instance with explicit control over internal parameters.

pub fn len(&self) -> usize

Returns the length (i.e., number of elements stored).

pub fn insert(&mut self, t: T) -> Option<Index>

Insert a value.

pub fn remove(&mut self, t: &T) -> bool

Remove a value.

pub fn remove_by_index(&mut self, idx: Index)

Remove a value by its index.

pub fn find(&self, t: &T) -> Option<Index>

Try to find an existing value.

pub fn get_by_index(&self, idx: Index) -> &T

Returns the element at a given index. Caution: An index that has been obtained before mutating the data structure is an invalid index. Calling this function with an invalid index may panic with index out of bounds.

pub fn next_index(&self, idx: Index) -> Option<Index>

Returns the index of the next element if there is one.

pub fn prev_index(&self, idx: Index) -> Option<Index>

Returns the index of the previous element if there is one.

pub fn min(&self) -> Option<&T>

Returns the minimum value.

pub fn max(&self) -> Option<&T>

Returns the maximum value.

pub fn traverse<F>(&self, f: F)

where F: FnMut(usize, &T),

Traverse collection given a callback.

pub fn collect(&self) -> Vec<T>

Collect collection into a vector.

pub fn get_leaf_fill_ratio(&self) -> f64

Get the average fill ratio of leafs, i.e., a value of 0.5 means that leafs are on average half full.

This is an O(1) operation.

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

Get the minimum number of elements in a leaf.

This requires iterating all blocks, and thus, is an O(sqrt N) operation.

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

Get the maximum number of elements in a leaf.

This requires iterating all blocks, and thus, is an O(sqrt N) operation.

pub fn get_capacity(&self) -> u16

Get the current max leaf capacity.

pub fn get_num_blocks(&self) -> usize

Get the current number of blocks.

pub fn debug(&self)

Internal debug helper function.

pub fn debug_order(&self)

pub fn fix_index(&self, transition: IndexTransition, idx: Index) -> Index

pub fn wiggle(&mut self, idx: Index) -> Option<IndexTransition>