maplike 0.3.0

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, gated by the std feature (enabled by default);
• HashSet, gated by the std feature (enabled by default);
• BTreeMap, not feature-gated;
• BTreeSet, 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, gated by the stable-vec feature; (example usage: examples/stable_vec.rs),
• thunderdome::Arena, gated by the thunderdome feature; (example usage: examples/thunderdome.rs),
• rstar::RTree, gated by the rstar feature. (example usage: examples/rstar.rs).
• rstared::RTreed, 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() method. For thunderdome::Arena, we insert at arbitrary key directly via the .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, SlotMap, 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 the freelist 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.