# BTree Index-map

[![Build](https://img.shields.io/github/actions/workflow/status/timothee-haudebourg/btree-indexmap/ci.yml?branch=main&style=flat-square)](https://github.com/timothee-haudebourg/btree-indexmap/actions)
[![Crate informations](https://img.shields.io/crates/v/btree-indexmap.svg?style=flat-square)](https://crates.io/crates/btree-indexmap)
[![License](https://img.shields.io/crates/l/btree-indexmap.svg?style=flat-square)](https://github.com/timothee-haudebourg/btree-indexmap#license)
[![Documentation](https://img.shields.io/badge/docs-latest-blue.svg?style=flat-square)](https://docs.rs/btree-indexmap)

<!-- cargo-rdme start -->

BTree-based maps and sets with stable entry indices.

This crate provides ordered map and set types that combine the
sorted-key lookup of a B-tree with stable integer indices backed by a
contiguous [`Vec`](https://doc.rust-lang.org/stable/alloc/vec/struct.Vec.html):

- [`BTreeIndexMap<K, V>`](https://docs.rs/btree-indexmap/latest/btree_indexmap/map/struct.BTreeIndexMap.html) — each key maps to exactly one value.
- [`BTreeIndexMultiMap<K, V>`](https://docs.rs/btree-indexmap/latest/btree_indexmap/multi_map/struct.BTreeIndexMultiMap.html) — each key may map to multiple values.
- [`BTreeIndexSet<T>`](https://docs.rs/btree-indexmap/latest/btree_indexmap/set/struct.BTreeIndexSet.html) — each value is stored at most once.
- [`BTreeIndexMultiSet<T>`](https://docs.rs/btree-indexmap/latest/btree_indexmap/multi_set/struct.BTreeIndexMultiSet.html) — each value may occur any number of times.

The set types are thin wrappers around their map counterparts
(`BTreeIndexMap<T, ()>` and `BTreeIndexMultiMap<T, ()>` respectively).

Entries are stored in a `Vec` and assigned a *stable index* equal to
their position in that `Vec`. The index of an entry does not change as
long as no entry is removed. A B-tree over the keys provides O(log n)
lookup, insertion, and removal, while the `Vec` backing allows O(1)
random access by index.

## Usage

### `BTreeIndexMap`

```rust
use btree_indexmap::BTreeIndexMap;

let mut map = BTreeIndexMap::new();

// Entries are stored in insertion order and assigned a stable index.
map.insert("banana", 3);
map.insert("apple", 5);

// O(1) access by index (insertion order).
assert_eq!(map.as_entries()[0], ("banana", 3));
assert_eq!(map.as_entries()[1], ("apple", 5));

// O(log n) lookup by key, returning the stable index alongside the value.
assert_eq!(map.get_full("apple"), Some((1, &"apple", &5)));

// Iterate in insertion order.
let by_insertion: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_insertion, [("banana", 3), ("apple", 5)]);

// Iterate in sorted key order.
let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_key, [("apple", 5), ("banana", 3)]);
```

### `BTreeIndexMultiMap`

```rust
use btree_indexmap::BTreeIndexMultiMap;

let mut map = BTreeIndexMultiMap::new();

// Multiple values per key, each with its own stable index.
map.push_back("fruit", "apple");
map.push_back("veggie", "carrot");
map.push_back("fruit", "banana");

assert_eq!(map.key_occurences("fruit"), 2);

let fruits: Vec<_> = map.get("fruit").copied().collect();
assert_eq!(fruits, ["apple", "banana"]);

// Iterate in sorted key order, values in position order within each key.
let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_key, [
    ("fruit", "apple"),
    ("fruit", "banana"),
    ("veggie", "carrot"),
]);
```

### `BTreeIndexSet`

```rust
use btree_indexmap::BTreeIndexSet;

let mut set = BTreeIndexSet::new();

// Values are stored in insertion order and assigned a stable index.
set.insert("banana");
set.insert("apple");

// O(1) access by index (insertion order).
assert_eq!(set.as_slice(), ["banana", "apple"]);

// O(log n) lookup, returning the stable index alongside the value.
assert_eq!(set.get_full("apple"), Some((1, &"apple")));
```

### `BTreeIndexMultiSet`

```rust
use btree_indexmap::BTreeIndexMultiSet;

let mut set = BTreeIndexMultiSet::new();

// Multiple occurrences of the same value, each with its own stable
// index.
set.push_back("apple");
set.push_back("carrot");
set.push_back("apple");

assert_eq!(set.count("apple"), 2);
```

<!-- cargo-rdme end -->

## License

Licensed under either of

 * Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
additional terms or conditions.
