Struct cuml_map::ExtensibleFenwickTree

pub struct ExtensibleFenwickTree<V> { /* fields omitted */ }

An extensible version of the Fenwick Tree. ExtensibleFenwickTree uses a FenwickTree internally, but applies an offset to any keys inserted or queried, allowing it to take negative keys. If a key is inserted that is outside the bounds of the underlying FenwickTree, then a new FenwickTree is created with sufficient capacity, all entries from the old tree are inserted into the new tree, and the old tree is dropped.

Methods

impl<V> ExtensibleFenwickTree<V> where     V: Add<Output = V> + Sub<Output = V> + Zero + Copy + Ord + Debug,

pub fn new() -> Self

Creates an empty tree with zero initial capacity.

pub fn with_capacity(c: usize) -> Self

Creates an empty tree with fixed initial capacity.

pub fn with_extent(o: i64, c: usize) -> Self

Creates an empty tree with a capacity c and offset o, such that the tree initially covers the range of keys [o, o+c).

pub fn ensure_contains(&mut self, key: i64)

Ensures that the tree will cover key key, in addition to all keys previously covered. Reallocates and rebuilds the tree if necessary.

Trait Implementations

impl<V> CumlMap for ExtensibleFenwickTree<V> where     V: Add<Output = V> + Sub<Output = V> + Zero + Copy + Ord + Debug,

type Key = i64

Type for the keys in this mapping.

type Value = V

Type for the values in this mapping.

fn insert(&mut self, key: Self::Key, val: Self::Value)

Insert an entry into the mapping.

fn get_cuml(&self, key: Self::Key) -> Self::Value

Get the cumulative value up to and including the specified key.

fn get_single(&self, key: Self::Key) -> Self::Value

Get the value at the specified key (not the cumulative value).

fn get_quantile(&self, quant: Self::Value) -> Option<Self::Key>

Get the first key at which the cumulative value equals or exceeds the specified value, if such a key exists. Note that if the result of this function is only defined if the cumulative value is non-decreasing. If you start putting negative values into your mappings, you will get strange results from this function.