# Tiered Vector
## Overview
This Rust crate provides an implementation of a tiered vector as described in the paper **Tiered Vector** by Goodrich and Kloss II, published in 1998 (and subsequently in 1999).
* https://www.researchgate.net/publication/225174363_Tiered_Vectors_Efficient_Dynamic_Arrays_for_Rank-Based_Sequences
This data structure supports efficient get and update operations with a running time of O(1) as well as insert and remove operations on the order of O(√N). It uses a collection of circular buffers to achieve this with a space overhead on the order of O(√N).
## Performance
Expect random remove/insert operations on a tiered vector to be orders of magnitude faster than a standard vector. Note that the benchmarks use different values because using an equal number for both data structures would take much too long.
## Examples
A simple example copied from the unit tests.
```rust
let mut tiered = Vector::<usize>::new();
assert!(tiered.is_empty());
for value in (1..=16).rev() {
tiered.insert(0, value);
}
assert!(!tiered.is_empty());
for (index, value) in (1..=16).enumerate() {
assert_eq!(tiered[index], value);
}
```
## Supported Rust Versions
The Rust edition is set to `2024` and hence version `1.85.0` is the minimum supported version.
## Troubleshooting
### Memory Leaks
Finding memory leaks with [Address Sanitizer](https://clang.llvm.org/docs/AddressSanitizer.html) is fairly [easy](https://doc.rust-lang.org/beta/unstable-book/compiler-flags/sanitizer.html) and seems to work best on Linux. A Docker container with bash access and [Rust](https://rust-lang.org) nightly installed can be found in the `containers` directory.
```shell
cd containers
docker compose build --pull
docker compose run leaktest
sh leak.sh
```
If no problems were detected, a single line of output will appear. When done, clean up the docker artifacts.
```shell
exit
docker compose down
```
## References
* \[1\]: [Tiered Vector (1998)](https://cs.brown.edu/cgc/jdsl/papers/tiered-vector.pdf)
- There is a 1999 version that lacks psuedo-code but is largely the same.
## Other Implementations
* [mettienne/tiered-vector](https://github.com/mettienne/tiered-vector)
- C++ templates variation by Bille, Christiansen, Ettienne, and Gørtz from their **Fast Dynamic Arrays** paper.
* [PhilipCramer/Tiered-Vector](https://github.com/PhilipCramer/Tiered-Vector)
- Rust implementation with a different underlying structure.
* [art-w/varray](https://github.com/art-w/varray) (OCaml)
* [taitaisama/TieredVector](https://github.com/taitaisama/TieredVector) (D)
* [layesUddin/Tiered-Vector](https://github.com/layesUddin/Tiered-Vector) (C)
* [igushev/IgushArray](https://github.com/igushev/IgushArray) (C/C++)
- No reference to tiered vectors but appears to be the same thing.