btree-indexmap 1.4.0

BTree-based map data structure with stable indexes.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

# 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.