maplike/
lib.rs

1// SPDX-FileCopyrightText: 2025 maplike contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5#![doc(html_root_url = "https://docs.rs/maplike")]
6#![doc = include_str!("../README.md")]
7#![deny(missing_docs)]
8#![forbid(unsafe_code)]
9#![no_std]
10
11#[cfg(feature = "std")]
12extern crate std as _std;
13
14// No feature for `alloc` because it would be always enabled anyway.
15extern crate alloc as _alloc;
16
17/// A keyed collection without any operations defined.
18///
19/// A keyed collection is just a key-value map. We however use the name
20/// `KeyedCollection` instead of `Map` to distinguish maps from vectors and
21/// stable vectors, which also are keyed collections but with slightly different
22/// sets of operations.
23pub trait KeyedCollection {
24    /// Type of the keys in the keyed collection.
25    type Key;
26    /// Type of the values in the keyed collection.
27    type Value;
28}
29
30/// Returns a reference to the value corresponding to the key.
31pub trait Get<K>: KeyedCollection {
32    /// Returns a reference to the value corresponding to the key.
33    fn get(&self, key: &K) -> Option<&Self::Value>;
34}
35
36/// Set the value of an already existing element under a key.
37pub trait Set<K>: KeyedCollection {
38    /// Set the value of an already existing element under a key.
39    fn set(&mut self, key: K, value: Self::Value);
40}
41
42/// Insert a new key-value pair into the collection at an arbitrary key.
43pub trait Insert<K>: KeyedCollection {
44    /// Insert a new key-value pair into the collection at an arbitrary key.
45    fn insert(&mut self, key: K, value: Self::Value);
46}
47
48/// Remove an element under a key from the collection, returning the value at
49/// the key if the key was previously in the map.
50pub trait Remove<K>: KeyedCollection {
51    /// Remove an element from the collection, returning the value at the key if
52    /// the key was previously in the map.
53    fn remove(&mut self, key: &K) -> Option<Self::Value>;
54}
55
56/// Removing an element under a key using [`Remove::remove()`] does not
57/// invalidate any other key.
58///
59/// Plain vectors such as [`Vec`] cannot implement this trait because
60/// removing elements invalidates keys of other elements. Some contiguous data
61/// structures, such as [`stable_vec::StableVec`] and [`thunderdome::Arena`],
62/// bypass this limitation by placing a tombstone element in place of the
63/// removed element.
64pub trait StableRemove<K>: Remove<K> {}
65
66/// Insert a value into the collection without specifying a key, returning
67/// the key that was automatically generated.
68pub trait Push<K>: KeyedCollection {
69    /// Insert a value into the collection without specifying a key, returning
70    /// the key that was automatically generated.
71    fn push(&mut self, value: Self::Value) -> K;
72}
73
74/// Remove the last element of the collection, returning it.
75///
76/// If `Push` is also implemented, calling `Pop` should revert the previous
77/// pushes in their reversed order.
78pub trait Pop: KeyedCollection {
79    /// Remove the last element of the collection, returning it.
80    fn pop(&mut self) -> Option<Self::Value>;
81}
82
83/// Consume the collection and yield owned key-value pairs.
84pub trait IntoIter<K>: KeyedCollection {
85    /// Iterator that consumes the collection.
86    type IntoIter: Iterator<Item = (K, Self::Value)>;
87
88    /// Consume the collection and yield owned key-value pairs.
89    fn into_iter(self) -> Self::IntoIter;
90}
91
92/// A keyed collection with stable removes.
93pub trait Map<K>: Get<K> + Insert<K> + StableRemove<K> {}
94impl<K, T: Get<K> + Insert<K> + StableRemove<K>> Map<K> for T {}
95
96/// A keyed collection with pushes.
97pub trait Vec<K>: Get<K> + Insert<K> + Remove<K> + Push<K> {}
98impl<K, T: Get<K> + Insert<K> + Remove<K> + Push<K>> Vec<K> for T {}
99
100/// A keyed collection with stable removes and pushes.
101pub trait StableVec<K>: Vec<K> + StableRemove<K> {}
102impl<K, T: Vec<K> + StableRemove<K>> StableVec<K> for T {}
103
104#[cfg(feature = "std")]
105mod std;
106
107// No feature for alloc because it would be always enabled anyway.
108mod alloc;
109
110#[cfg(feature = "stable-vec")]
111mod stable_vec;
112
113#[cfg(feature = "thunderdome")]
114mod thunderdome;
115
116#[cfg(feature = "rstar")]
117mod rstar;
maplike/lib.rs

maplike/
lib.rs
