Crate cuml_map[−][src]
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 |
ExtensibleFenwickTree |
An extensible version of the Fenwick Tree. |
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. |