[](https://docs.rs/maplike/)
[](https://crates.io/crates/maplike)
[](#licence)
# maplike
Traits for abstract containers and operations over them.
This crate provides traits for common operations over map-like, set-like, and
vec-like data structures:
[`get`](https://docs.rs/maplike/latest/maplike/trait.Get.html#tymethod.get),
[`set`](https://docs.rs/maplike/latest/maplike/trait.Set.html#tymethod.set),
[`modify`](https://docs.rs/maplike/latest/maplike/trait.Modify.html#tymethod.modify),
[`insert`](https://docs.rs/maplike/latest/maplike/trait.Insert.html#tymethod.insert),
[`remove`](https://docs.rs/maplike/latest/maplike/trait.Remove.html#tymethod.remove),
[`push`](https://docs.rs/maplike/latest/maplike/trait.Push.html#tymethod.push),
[`pop`](https://docs.rs/maplike/latest/maplike/trait.Pop.html#tymethod.pop),
[`put`](https://docs.rs/maplike/latest/maplike/trait.Put.html#tymethod.put),
[`clear`](https://docs.rs/maplike/latest/maplike/trait.Clear.html#tymethod.clear),
[`len`](https://docs.rs/maplike/latest/maplike/trait.Len.html#tymethod.len),
[`with_one`](https://docs.rs/maplike/latest/maplike/trait.WithOne#tymethod.with_one),
[`assign`](https://docs.rs/maplike/latest/maplike/trait.Assign.html#tymethod.assign), and
[`into_iter`](https://docs.rs/maplike/latest/maplike/trait.IntoIter.html#tymethod.into_iter).
For bidirectional maps, there are also variants of the get and remove operations
by left and right key:
[`get_by_left`](https://docs.rs/maplike/latest/maplike/trait.GetByLeft.html#tymethod.get_by_left),
[`get_by_right`](https://docs.rs/maplike/latest/maplike/trait.GetByRight.html#tymethod.get_by_right),
[`remove_by_left`](https://docs.rs/maplike/latest/maplike/trait.RemoveByLeft.html#tymethod.remove_by_left),
[`remove_by_right`](https://docs.rs/maplike/latest/maplike/trait.RemoveByRight.html#tymethod.remove_by_right).
For brevity and convenience, we also provide
[`Scalarlike`](https://docs.rs/maplike/latest/maplike/trait.Scalarlike.html),
[`Maplike`](https://docs.rs/maplike/latest/maplike/trait.Maplike.html),
[`Setlike`](https://docs.rs/maplike/latest/maplike/trait.Setlike.html),
[`Arraylike`](https://docs.rs/maplike/latest/maplike/trait.Arraylike.html), and
[`Veclike`](https://docs.rs/maplike/latest/maplike/trait.Veclike.html) traits,
which represent complete abstract containers that join together traits of
multiple operations.
Basically, this is Python's
[collections.abc](https://docs.python.org/3/library/collections.abc.html), but
in Rust, and with traits not only for different kinds of containers, but also
for each operation.
This library is maintained and champaigned (aka.
[dogfooded](https://en.wikipedia.org/wiki/Eating_your_own_dog_food)) by the
author, who uses has it as a dependency for
- [`undoredo`](https://github.com/mikwielgus/undoredo), a versatile crate for
implementing Undo/Redo and non-linear history tree using sparse deltas (diffs),
snapshots, or commands on arbitrary data structures;
- [`dcel`](https://github.com/mikwielgus/dcel), a crate that implements the
half-edge data structure (aka. doubly connected edge list, DCEL) generically
over its underlying containers.
## Usage
### Adding dependency
First, add `maplike` as a dependency to your Cargo.toml:
```toml
[dependencies]
maplike = { version = "0.11.2", features = ["derive"] }
```
The `derive` feature flag is only needed if you want to
derive `Assign` or `Container` traits using derive macros:
[`#[derive(Assign)]`](https://docs.rs/maplike/latest/maplike/derive.Assign.html)
or
[`#[derive(Container)]`](https://docs.rs/maplike/latest/maplike/derive.Container
.html).
### Usage examples
`maplike`'s traits allow you to write functions that are generic over many
different collection types. A single trait like
[`Get`](https://docs.rs/maplike/latest/maplike/trait.Get.html) is enough to
abstract over vectors, arrays, and maps alike.
```rust
use std::collections::BTreeMap;
use maplike::Get;
// Generic over any collection implementing the `Get` trait.
fn get_second_element<C: Get<usize>>(collection: &C) -> Option<&C::Value> {
collection.get(&1)
}
// `get_second_element()` works for `Vec`s, arrays, and maps with the very
// same code.
assert_eq!(get_second_element(&vec![10, 20, 30]), Some(&20));
assert_eq!(get_second_element(&[10, 20, 30]), Some(&20));
assert_eq!(get_second_element(&BTreeMap::from([(0, 10), (1, 20)])), Some(&20));
```
An abstract container trait can bundle together several traits
for container methods together in one short bound. For example,
[`Veclike`](https://docs.rs/maplike/latest/maplike/trait.Veclike.html) joins
together
([`Get`](https://docs.rs/maplike/latest/maplike/trait.Get.html),
[`Set`](https://docs.rs/maplike/latest/maplike/trait.Set.html),
[`Push`](https://docs.rs/maplike/latest/maplike/trait.Push.html),
[`Pop`](https://docs.rs/maplike/latest/maplike/trait.Pop.html),
[`Clear`](https://docs.rs/maplike/latest/maplike/trait.Clear.html),
[`Len`](https://docs.rs/maplike/latest/maplike/trait.Len.html), and
[`Index`](https://doc.rust-lang.org/std/ops/trait.Index.html)), thus allowing
code that is generic over
[`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html),
[`tinyvec::ArrayVec`](https://docs.rs/tinyvec/latest/tinyvec/struct.ArrayVec.html),
and [`tinyvec::TinyVec`](https://docs.rs/tinyvec/latest/tinyvec/enum.TinyVec.html).
```rust
use maplike::{Clear, Push, Veclike};
use tinyvec::{ArrayVec, TinyVec};
// This function is generic over any `Veclike` collection. The `Veclike` bound
// provides `.clear()`, `.push()` and many other methods at once.
fn replace_all<C: Veclike<usize, Value = i32>>(collection: &mut C, values: &[i32]) {
collection.clear();
for &value in values {
collection.push(value);
}
}
// `replace_all()` now works for any `Veclike` collection.
// Works on `Vec`,
let mut vec = Vec::new();
replace_all(&mut vec, &[1, 2, 3]);
assert_eq!(vec, [1, 2, 3]);
replace_all(&mut vec, &[4, 5, 6]);
assert_eq!(vec, [4, 5, 6]);
// Works on `tinyvec::ArrayVec`.
let mut array_vec: ArrayVec<[i32; 8]> = ArrayVec::new();
replace_all(&mut array_vec, &[7, 8, 9]);
assert_eq!(array_vec.as_slice(), [7, 8, 9]);
// Works on `tinyvec::TinyVec`.
let mut tiny_vec: TinyVec<[i32; 8]> = TinyVec::new();
replace_all(&mut tiny_vec, &[10, 11, 12]);
assert_eq!(tiny_vec.as_slice(), [10, 11, 12]);
```
## Supported collections
### Standard library
Rust's standard library containers 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;
- [`Option`](https://doc.rust-lang.org/std/option/enum.Option.html), not feature-gated;
- [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html), not feature-gated.
### Third-party types
In addition to the standard library, `maplike` has built-in feature-gated
convenience implementations for data structures from certain external crates:
- [`bidimap::BiBTreeMap`](https://docs.rs/bidimap/latest/bidimap/), gated by
the `bidimap` feature flag, and
[`bidimap::BiHashMap`](https://docs.rs/bidimap/latest/bidimap/), which is also
gated by the `std` feature flag.
[`bidimap`](https://github.com/urschrei/bidimap)
is a maintained fork of the currently unmaintained
[`bimap`](https://github.com/brson/bimap) crate;
- [`rstar::RTree`](https://docs.rs/rstar/0.12.2/rstar/index.html), gated by the
`rstar` feature flag;
- [`rstared::RTreed`](https://docs.rs/rstared/latest/rstared/), gated by the
`rstared` feature flag;
- [`stable_vec::StableVec`](https://docs.rs/stable-vec/latest/stable_vec/),
gated by the `stable-vec` feature flag;
- [`thunderdome::Arena`](https://docs.rs/thunderdome/latest/thunderdome/),
gated by the `thunderdome` feature flag;
- [`tinyvec::ArrayVec`](https://docs.rs/tinyvec/latest/tinyvec/struct.ArrayVec.html),
and [`tinyvec::TinyVec`](https://docs.rs/tinyvec/latest/tinyvec/enum.TinyVec.html),
gated by the `tinyvec` feature flag.
For examples, see
[examples](https://github.com/mikwielgus/undoredo/tree/develop/examples)
directory of the [`undoredo`](https://github.com/mikwielgus/undoredo) crate.
## Unsupported collections
Standard library's `VecDeque` is unsupported.
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 sidenotes
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.
For `Slab`, an interface to insert at an arbitrary key 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.