`prefix-sum-vec`

<div align="center">
  <h1><code>prefix-sum-vec</code></h1>

  <p>
    <strong>A Rust crate for compressed storage of highly repeating elements, with <code>O(log n)</code> lookups</strong>
  </p>
</div>

# What is this?

The data structure provided by this crate allow users to space-efficiently store repeating
sequences of the same value. An example of this sort of data comes up in WebAssembly, where the
locals for a function are represented as a sequence of types and their repetition count. The binary
encoding of function locals such as these

```wast
(locals i32 i32 i32 i32 i64 i64 f64)
```

is actually encoded as a sequence along the lines of `0x04 i32 0x02 i64 0x01 f64`. Were the decoded
representation of the locals naively stuff everything into a vector, a potential denial-of-service
hazard could arise. A crafted input with a representation of millions of locals in just a couple
of bytes of encoded space would force a naive implementation to allocate gigabytes of memory space.

The data structure provided by this crate stores just one copy of the repeating element alongside
with a prefix-sum of the indices at which the element can be found. So, given the locals example
above, the storage would look something like this:

```text
[(4, i32), (6, i64), (7, f64)]
```

From there on, looking up an element with an index 5 is a binary search away over the prefix-sum
indices.

# Usage

First, specify this crate in your `Cargo.toml`:

```toml
[dependencies]
prefix-sum-vec = "0.1"
```

This crate aims to be extremely lightweight and straightforward. As such there are no optional
features to enable at this time. Then, refer to the documentation of the `PrefixSumVec` type to
discover its usage in your code.

# License

This project is licensed under the Apache 2.0 OR BSD 3-clause license at your choice.