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, set, modify, insert, remove, push, pop, put, clear, len, with_one, assign, and into_iter.

For bidirectional maps, there are also variants of the get and remove operations by left and right key: get_by_left, get_by_right, remove_by_left, remove_by_right.

For brevity and convenience, we also provide Scalarlike, Maplike, Setlike, Arraylike, and Veclike traits, which represent complete abstract containers that join together traits of multiple operations.

Basically, this is Python's collections.abc, 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) by the author, who uses has it as a dependency for

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, 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:

[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)] 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 is enough to abstract over vectors, arrays, and maps alike.

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 joins together (Get, Set, Push, Pop, Clear, Len, and Index), thus allowing code that is generic over Vec, tinyvec::ArrayVec, and tinyvec::TinyVec.

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, 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;
Option, not feature-gated;
Vec, 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, gated by the bidimap feature flag, and bidimap::BiHashMap, which is also gated by the std feature flag. bidimap is a maintained fork of the currently unmaintained bimap crate;
rstar::RTree, gated by the rstar feature flag;
rstared::RTreed, gated by the rstared feature flag;
stable_vec::StableVec, gated by the stable-vec feature flag;
thunderdome::Arena, gated by the thunderdome feature flag;
tinyvec::ArrayVec, and tinyvec::TinyVec, gated by the tinyvec feature flag.

For examples, see examples directory of the undoredo crate.

Unsupported collections

Standard library's VecDeque is unsupported.

Among stable vector data structures, Slab, SlotMap, 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() 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.

For Slab, an interface to insert at an arbitrary key 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.

maplike 0.11.2