Crate cuml_map

This crate provides a trait, CumlMap, representing a mapping between keys and cumulative values. That is, an object implementing CumlMap should be able to store key-value mappings, and efficiently retrive the sum of all values with a key less than or equal to a given key.

This crate also provides three implementations of the CumlMap trait: FenwickTree, ExtensibleFenwickTree, and CumlTree. FenwickTree is the most restricted in terms of what keys and values it can accept, but also the most performant in those restricted cases.

FenwickTree accepts only non-negative keys, allocates all memory in advance, and its capacity is fixed at creation time and cannot be changed. If you need to get around any of these limitations then use the ExtensibleFenwickTree object instead.

Both FenwickTree and ExtensibleFenwickTree may be a poor choice for sparse keys. Both structures must allocate space for at least every possible key between the smallest and largest keys. To get around this limitation use the CumlMap structure, which dynamically allocates mappings, at the expense of insertion and lookup performance.

Structs

CumlTree	The CumlTree type. An unbounded mapping between ordered keys and cumulative values, represented as a red-black tree.
ExtensibleFenwickTree	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.
FenwickTree	A Fenwick Tree[^fn] structure, useful for very quickly mapping a non-negative integer key to a cumulative value.

Traits

CumlMap

Trait for building and querying mappings between keys and cumulative values.