jam_types/
vec_map.rs

1use super::*;
2use alloc::borrow::Borrow;
3use codec::Error as DecodeError;
4use core::fmt;
5
6/// A data-structure providing the storage and lookup of key/value pairs with exclusive keys.
7pub trait MapLike<K, V> {
8	/// Insert pair into the mapping.
9	///
10	/// Inserts some pair (`k`, `v`) into the mapping, replacing the existing pair whose key is `k`,
11	/// if any.
12	///
13	/// Returns [Some] value which was replaced, if any.
14	fn insert(&mut self, k: K, v: V) -> Option<V>;
15	/// Insert multiple pairs from an iterator.
16	///
17	/// Replaces any existing pairs which share a key with an element of the iterator.
18	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>);
19	/// Check if a key is in the mapping.
20	///
21	/// Returns `true` iff the mapping contains a pair whose key equals `k`.
22	fn contains_key(&self, k: &K) -> bool;
23	/// Remove an item from the mapping by key.
24	///
25	/// Removes the item with key equal to `k` from the mapping.
26	///
27	/// Returns the value of the item removed, if any.
28	fn remove(&mut self, k: &K) -> Option<V>;
29	/// Get the value of the pair with a particular key.
30	///
31	/// Returns a reference the value of the item in the mapping whose key equals `k`.
32	fn get(&self, k: &K) -> Option<&V>;
33	/// Get a mutable reference to the value of the pair with a particular key.
34	///
35	/// Returns a mutable reference the value of the item in the mapping whose key equals `k`.
36	fn get_mut(&mut self, k: &K) -> Option<&mut V>;
37	/// Get an iterator to all keys in the mapping.
38	///
39	/// No order is guaranteed.
40	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
41	where
42		K: 'a;
43}
44
45#[cfg(feature = "std")]
46impl<K: Eq + std::hash::Hash, V> MapLike<K, V> for std::collections::HashMap<K, V> {
47	fn insert(&mut self, k: K, v: V) -> Option<V> {
48		std::collections::HashMap::<K, V>::insert(self, k, v)
49	}
50	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
51		<std::collections::HashMap<K, V> as Extend<(K, V)>>::extend(self, iter)
52	}
53	fn contains_key(&self, k: &K) -> bool {
54		std::collections::HashMap::<K, V>::contains_key(self, k)
55	}
56	fn remove(&mut self, k: &K) -> Option<V> {
57		std::collections::HashMap::<K, V>::remove(self, k)
58	}
59	fn get(&self, k: &K) -> Option<&V> {
60		std::collections::HashMap::<K, V>::get(self, k)
61	}
62	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
63		std::collections::HashMap::<K, V>::get_mut(self, k)
64	}
65	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
66	where
67		K: 'a,
68	{
69		std::collections::HashMap::<K, V>::keys(self)
70	}
71}
72
73impl<K: Eq + PartialEq + Ord + PartialOrd, V> MapLike<K, V> for alloc::collections::BTreeMap<K, V> {
74	fn insert(&mut self, k: K, v: V) -> Option<V> {
75		alloc::collections::BTreeMap::<K, V>::insert(self, k, v)
76	}
77	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
78		<alloc::collections::BTreeMap<K, V> as Extend<(K, V)>>::extend(self, iter)
79	}
80	fn contains_key(&self, k: &K) -> bool {
81		alloc::collections::BTreeMap::<K, V>::contains_key(self, k)
82	}
83	fn remove(&mut self, k: &K) -> Option<V> {
84		alloc::collections::BTreeMap::<K, V>::remove(self, k)
85	}
86	fn get(&self, k: &K) -> Option<&V> {
87		alloc::collections::BTreeMap::<K, V>::get(self, k)
88	}
89	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
90		alloc::collections::BTreeMap::<K, V>::get_mut(self, k)
91	}
92	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
93	where
94		K: 'a,
95	{
96		alloc::collections::BTreeMap::<K, V>::keys(self)
97	}
98}
99
100/// An mapping of key/value pairs stored as pairs ordered by their key in a [Vec].
101///
102/// This is always efficient for small sizes of mappings, and efficient for large sizes when
103/// insertion is not needed (i.e. items are placed into the mapping in bulk).
104#[derive(Clone, Encode, Eq, PartialEq, Ord, PartialOrd)]
105pub struct VecMap<K, V>(Vec<(K, V)>);
106impl<K: Eq + PartialEq + Ord + PartialOrd, V> VecMap<K, V> {
107	/// Create a new, empty instance.
108	pub const fn new() -> Self {
109		Self(Vec::new())
110	}
111	/// Create a new instance from a sorted [Vec].
112	///
113	/// Returns [Ok] with an instance containing the same items as `v`, or [Err] if `v` is unsorted.
114	pub fn from_sorted(v: Vec<(K, V)>) -> Result<Self, ()> {
115		let Some((first, _)) = v.first() else { return Ok(Self::new()) };
116		v.iter()
117			.skip(1)
118			.try_fold(first, |a, (e, _)| if a < e { Some(e) } else { None })
119			.ok_or(())?;
120		Ok(Self(v))
121	}
122	/// Return the number of items this mapping contains.
123	pub fn len(&self) -> usize {
124		self.0.len()
125	}
126	/// Return `true` if this mapping is empty.
127	pub fn is_empty(&self) -> bool {
128		self.0.is_empty()
129	}
130	/// Return an iterator over the key/value pairs in this mapping in order.
131	pub fn iter(&self) -> core::slice::Iter<'_, (K, V)> {
132		self.0.iter()
133	}
134	/// Return an iterator over the keys in this mapping in order.
135	pub fn keys(&self) -> impl Iterator<Item = &K> {
136		self.0.iter().map(|(k, _)| k)
137	}
138	/// Return an iterator over the values in this mapping in order of their corresponding key.
139	pub fn values(&self) -> impl Iterator<Item = &V> {
140		self.0.iter().map(|(_, v)| v)
141	}
142	/// Get the value of the pair with a particular key.
143	///
144	/// Returns a reference the value of the item in the mapping whose key equals `k`.
145	pub fn get<Q>(&self, k: &Q) -> Option<&V>
146	where
147		K: Borrow<Q>,
148		Q: Ord + ?Sized,
149	{
150		self.0.binary_search_by(|x| x.0.borrow().cmp(k)).ok().map(|i| &self.0[i].1)
151	}
152
153	/// Get a mutable reference to the value of the pair with a particular key.
154	///
155	/// Returns a mutable reference the value of the item in the mapping whose key equals `k`.
156	pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
157	where
158		K: Borrow<Q>,
159		Q: Ord + ?Sized,
160	{
161		self.0
162			.binary_search_by(|x| x.0.borrow().cmp(k))
163			.ok()
164			.map(move |i| &mut self.0[i].1)
165	}
166	/// Consume this mapping and return a [Vec] of transformed pairs.
167	///
168	/// Returns the [Vec] of the resultant values of applying `f` to each pair in the mapping in
169	/// order.
170	pub fn map<U>(self, mut f: impl FnMut(K, V) -> U) -> Vec<U> {
171		self.0.into_iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
172	}
173	/// Transform all pairs by reference and return a [Vec] with the results.
174	///
175	/// Returns the [Vec] of the resultant values of applying `f` to each pair by reference in the
176	/// mapping in order.
177	pub fn map_ref<U>(&self, mut f: impl FnMut(&K, &V) -> U) -> Vec<U> {
178		self.0.iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
179	}
180	/// Return a [Vec] of sorted key/value pairs by cloning this mapping.
181	pub fn to_vec(&self) -> Vec<(K, V)>
182	where
183		K: Clone,
184		V: Clone,
185	{
186		self.0.clone()
187	}
188	/// Return the [Vec] of sorted key/value pairs by consuming this mapping.
189	pub fn into_vec(self) -> Vec<(K, V)> {
190		self.0
191	}
192	/// Insert pair into the mapping.
193	///
194	/// Inserts some pair (`k`, `v`) into the mapping, replacing the existing pair whose key is `k`,
195	/// if any.
196	///
197	/// Returns [Some] value which was replaced, if any.
198	///
199	/// NOTE: This does an ordered insert and thus is slow. If you're inserting multiple items, use
200	/// [Self::extend] which is much more efficient or consider using an alternative data structure
201	/// if you're doing this a lot.
202	pub fn insert(&mut self, k: K, v: V) -> Option<(K, V)> {
203		match self.0.binary_search_by(|x| x.0.cmp(&k)) {
204			Ok(i) => Some(core::mem::replace(&mut self.0[i], (k, v))),
205			Err(i) => {
206				self.0.insert(i, (k, v));
207				None
208			},
209		}
210	}
211	/// Insert multiple pairs from an iterator.
212	///
213	/// Replaces any existing pairs which share a key with an element of the iterator.
214	pub fn extend(&mut self, iter: impl IntoIterator<Item = (K, V)>) {
215		self.0.splice(0..0, iter);
216		self.0.sort_by(|x, y| x.0.cmp(&y.0));
217		self.0.dedup_by(|x, y| x.0 == y.0);
218	}
219	/// Check if a key is in the mapping.
220	///
221	/// Returns `true` iff the mapping contains a pair whose key equals `k`.
222	pub fn contains_key<Q>(&self, k: &Q) -> bool
223	where
224		K: Borrow<Q>,
225		Q: Ord + ?Sized,
226	{
227		self.0.binary_search_by(|x| x.0.borrow().cmp(k)).is_ok()
228	}
229	/// Remove an item from the mapping by key.
230	///
231	/// Removes the item with key equal to `k` from the mapping.
232	///
233	/// Returns the value of the item removed, if any.
234	pub fn remove<Q>(&mut self, k: &Q) -> Option<(K, V)>
235	where
236		K: Borrow<Q>,
237		Q: Ord + ?Sized,
238	{
239		match self.0.binary_search_by(|x| x.0.borrow().cmp(k)) {
240			Ok(i) => Some(self.0.remove(i)),
241			Err(_) => None,
242		}
243	}
244	/// Filter items from the mapping.
245	///
246	/// Removes all pairs from the mapping for which `f` returns `false`.
247	pub fn retain(&mut self, mut f: impl FnMut(&K, &V) -> bool) {
248		self.0.retain(|x| f(&x.0, &x.1));
249	}
250	/// Remove all elements.
251	pub fn clear(&mut self) {
252		self.0.clear();
253	}
254	// TODO: Create traits `OrderedSetLike`/`OrderedMapLike` and make work with them.
255	/// Compares the pairs in two mappings.
256	///
257	/// Returns `true` iff every pair in the mapping is not found in `other`.
258	pub fn is_disjoint(&self, other: &VecMap<K, V>) -> bool
259	where
260		V: Ord,
261	{
262		vec_set::is_disjoint(self.iter(), other.iter())
263	}
264	/// Compares the keys in two mappings.
265	///
266	/// Returns `true` iff every key in the mapping is not found in the keys of `other`.
267	pub fn keys_disjoint<W>(&self, other: &VecMap<K, W>) -> bool {
268		vec_set::is_disjoint(self.keys(), other.keys())
269	}
270	/// Compares the keys in this mapping with the values in a set.
271	///
272	/// Returns `true` iff every key in the mapping is not found in `other`.
273	pub fn keys_disjoint_with_set(&self, other: &VecSet<K>) -> bool {
274		vec_set::is_disjoint(self.keys(), other.iter())
275	}
276}
277
278impl<K: Eq + PartialEq + Ord + PartialOrd, V> MapLike<K, V> for VecMap<K, V> {
279	fn insert(&mut self, k: K, v: V) -> Option<V> {
280		VecMap::<K, V>::insert(self, k, v).map(|(_, v)| v)
281	}
282	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
283		VecMap::<K, V>::extend(self, iter)
284	}
285	fn contains_key(&self, k: &K) -> bool {
286		VecMap::<K, V>::contains_key(self, k)
287	}
288	fn remove(&mut self, k: &K) -> Option<V> {
289		VecMap::<K, V>::remove(self, k).map(|x| x.1)
290	}
291	fn get(&self, k: &K) -> Option<&V> {
292		VecMap::<K, V>::get(self, k)
293	}
294	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
295		VecMap::<K, V>::get_mut(self, k)
296	}
297	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
298	where
299		K: 'a,
300	{
301		VecMap::<K, V>::keys(self)
302	}
303}
304
305impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for VecMap<K, V> {
306	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307		match self.0.len() {
308			0 => write!(f, "[]"),
309			_ => {
310				write!(f, "[{:?}=>{:?}", self.0[0].0, self.0[0].1)?;
311				for i in 1..self.0.len() {
312					write!(f, ", {:?}=>{:?}", self.0[i].0, self.0[i].1)?;
313				}
314				write!(f, "]")
315			},
316		}
317	}
318}
319
320impl<K: fmt::Display, V: fmt::Display> fmt::Display for VecMap<K, V> {
321	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
322		match self.0.len() {
323			0 => write!(f, "[]"),
324			_ => {
325				write!(f, "[{}=>{}", self.0[0].0, self.0[0].1)?;
326				for i in 1..self.0.len() {
327					write!(f, ", {}=>{}", self.0[i].0, self.0[i].1)?;
328				}
329				write!(f, "]")
330			},
331		}
332	}
333}
334
335impl<K: Decode + Eq + PartialEq + Ord + PartialOrd, V: Decode> Decode for VecMap<K, V> {
336	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, DecodeError> {
337		Ok(Self::from_sorted(Vec::<(K, V)>::decode(input)?).map_err(|()| "set out-of-order")?)
338	}
339}
340
341impl<K, V> Default for VecMap<K, V> {
342	fn default() -> Self {
343		Self(Vec::new())
344	}
345}
346impl<K, V> AsRef<[(K, V)]> for VecMap<K, V> {
347	fn as_ref(&self) -> &[(K, V)] {
348		&self.0[..]
349	}
350}
351impl<K, V> AsMut<[(K, V)]> for VecMap<K, V> {
352	fn as_mut(&mut self) -> &mut [(K, V)] {
353		&mut self.0[..]
354	}
355}
356
357impl<K, V> From<VecMap<K, V>> for Vec<(K, V)> {
358	fn from(s: VecMap<K, V>) -> Vec<(K, V)> {
359		s.0
360	}
361}
362impl<K: Eq + PartialEq + Ord + PartialOrd, V> From<Vec<(K, V)>> for VecMap<K, V> {
363	fn from(mut v: Vec<(K, V)>) -> Self {
364		v.sort_by(|x, y| x.0.cmp(&y.0));
365		v.dedup_by(|x, y| x.0 == y.0);
366		Self(v)
367	}
368}
369impl<K: Eq + PartialEq + Ord + PartialOrd, V> FromIterator<(K, V)> for VecMap<K, V> {
370	fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
371		Vec::<(K, V)>::from_iter(iter).into()
372	}
373}
374impl<K: Eq + PartialEq + Ord + PartialOrd, V> Extend<(K, V)> for VecMap<K, V> {
375	fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
376		VecMap::<K, V>::extend(self, iter)
377	}
378}
379impl<K: Eq + PartialEq + Ord + PartialOrd, V> IntoIterator for VecMap<K, V> {
380	type Item = (K, V);
381	type IntoIter = <Vec<(K, V)> as IntoIterator>::IntoIter;
382
383	fn into_iter(self) -> Self::IntoIter {
384		self.0.into_iter()
385	}
386}
387
388#[cfg(test)]
389mod tests {
390	use super::*;
391	#[test]
392	fn encode_decode_works() {
393		let v = VecMap::<u32, u32>::from_iter((0..100).map(|j| ((j * 97) % 101, j)));
394		println!("{v}");
395		let e = v.encode();
396		let d = VecMap::<u32, u32>::decode(&mut &e[..]).unwrap();
397		assert_eq!(v, d);
398	}
399}
jam_types/vec_map.rs

jam_types/
vec_map.rs
