This create provides traits for common operations over maps and stable vectors:
insert, remove and push.
## Supported collections
Rust's standard library maps and sets are supported via built-in convenience
implementations:
- [`HashMap`](https://doc.rust-lang.org/std/collections/struct.HashMap.html), gated by the `std` feature (enabled by default);
- [`HashSet`](https://doc.rust-lang.org/stable/std/collections/struct.HashSet.html), gated by the `std` feature (enabled by default);
- [`BTreeMap`](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html), not feature-gated;
- [`BTreeSet`](https://doc.rust-lang.org/stable/std/collections/struct.BTreeSet.html), not feature-gated.
### Third-party types
In addition to the standard library, `undoredo` has built-in feature-gated
convenience implementations for data structures from certain external crates:
- [`stable_vec::StableVec`](https://docs.rs/stable-vec/latest/stable_vec/),
gated by the `stable-vec` feature; (example usage:
[examples/stable_vec.rs](./examples/stable_vec.rs)),
- [`thunderdome::Arena`](https://docs.rs/thunderdome/latest/thunderdome/),
gated by the `thunderdome` feature; (example usage:
[examples/thunderdome.rs](./examples/thunderdome.rs)),
- [`rstar::RTree`](https://docs.rs/rstar/0.12.2/rstar/index.html), gated by the
`rstar` feature. (example usage: [examples/rstar.rs](./examples/rstar.rs)).
- [`rstared::RTreed`](https://docs.rs/rstared/latest/rstared/), gated by the
`rstared` feature.
**Technical sidenote:** Unlike maps and sets, not all stable vector data
structures allow insertion and removal at arbitrary indexes regardless of
whether they are vacant, occupied or out of bounds. For `StableVec`, we managed
to implement inserting at out-of-bound indexes by changing the length before
insertion using the
[`.reserve_for()`](https://docs.rs/stable-vec/latest/stable_vec/struct.StableVecFacade.html#method.reserve_for)
method. For `thunderdome::Arena`, we insert at arbitrary key directly via the
[`.insert_at()`](https://docs.rs/thunderdome/latest/thunderdome/struct.Arena.html#method.insert_at)
method. Collections for which we could not achieve this are documented in the
section below.
## Unsupported collections
Standard library's `Vec` and `VecDeque` cannot be supported because they lack
an interface to remove elements without invalidating indexes of other elements.
Stable vectors do not have this limitation.
Among stable vector data structures,
[`Slab`](https://docs.rs/slab/latest/slab/),
[`SlotMap`](https://docs.rs/slotmap/latest/slotmap/),
[`generational-arena`](https://docs.rs/generational-arena/latest/generational_arena/)
cannot be supported because they lack interfaces for insertion at an arbitrary
key.
**Technical sidenote:** For `Slab`, such interface is missing apparently
[because](https://github.com/tokio-rs/slab/issues/117#issuecomment-1159741097)
the [freelist](https://en.wikipedia.org/wiki/Free_list) `Slab` uses to keep
track of its vacant indexes is only singly-linked, not doubly-linked. Inserting
an element at an arbitrary vacant index would require removing that index from
the freelist. But since there is no backwards link available at a given key,
doing so would require traversing the freelist from the beginning to find the
position of the previous node, which would incur an overly slow `O(n)` time
cost.