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, empty instance with specified capacity.
112	pub fn with_capacity(capacity: usize) -> Self {
113		Self(Vec::with_capacity(capacity))
114	}
115	/// Create a new instance from a sorted [Vec].
116	///
117	/// Returns [Ok] with an instance containing the same items as `v`, or [Err] if `v` is unsorted.
118	pub fn from_sorted(v: Vec<(K, V)>) -> Result<Self, ()> {
119		let Some((first, _)) = v.first() else { return Ok(Self::new()) };
120		v.iter()
121			.skip(1)
122			.try_fold(first, |a, (e, _)| if a < e { Some(e) } else { None })
123			.ok_or(())?;
124		Ok(Self(v))
125	}
126	/// Return the number of items this mapping contains.
127	pub fn len(&self) -> usize {
128		self.0.len()
129	}
130	/// Return `true` if this mapping is empty.
131	pub fn is_empty(&self) -> bool {
132		self.0.is_empty()
133	}
134	/// Return an iterator over the key/value pairs in this mapping in order.
135	pub fn iter(&self) -> core::slice::Iter<'_, (K, V)> {
136		self.0.iter()
137	}
138	/// Return an iterator over the key/value pairs in this mapping in order, with mutable
139	/// references to the values.
140	pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
141		self.0.iter_mut().map(|(k, v)| (&*k, v))
142	}
143	/// Return an iterator over the keys in this mapping in order.
144	pub fn keys(&self) -> impl Iterator<Item = &K> {
145		self.0.iter().map(|(k, _)| k)
146	}
147	/// Return an iterator over the values in this mapping in order of their corresponding key.
148	pub fn values(&self) -> impl Iterator<Item = &V> {
149		self.0.iter().map(|(_, v)| v)
150	}
151	/// Return an iterator over the mutable values in this mapping in order of their corresponding
152	/// key.
153	pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
154		self.0.iter_mut().map(|(_, v)| v)
155	}
156	/// Get the value of the pair with a particular key.
157	///
158	/// Returns a reference the value of the item in the mapping whose key equals `k`.
159	pub fn get<Q>(&self, k: &Q) -> Option<&V>
160	where
161		K: Borrow<Q>,
162		Q: Ord + ?Sized,
163	{
164		self.0.binary_search_by(|x| x.0.borrow().cmp(k)).ok().map(|i| &self.0[i].1)
165	}
166
167	/// Get a mutable reference to the value of the pair with a particular key.
168	///
169	/// Returns a mutable reference the value of the item in the mapping whose key equals `k`.
170	pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
171	where
172		K: Borrow<Q>,
173		Q: Ord + ?Sized,
174	{
175		self.0
176			.binary_search_by(|x| x.0.borrow().cmp(k))
177			.ok()
178			.map(move |i| &mut self.0[i].1)
179	}
180	/// Consume this mapping and return a [Vec] of transformed pairs.
181	///
182	/// Returns the [Vec] of the resultant values of applying `f` to each pair in the mapping in
183	/// order.
184	pub fn map<U>(self, mut f: impl FnMut(K, V) -> U) -> Vec<U> {
185		self.0.into_iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
186	}
187	/// Transform all pairs by reference and return a [Vec] with the results.
188	///
189	/// Returns the [Vec] of the resultant values of applying `f` to each pair by reference in the
190	/// mapping in order.
191	pub fn map_ref<U>(&self, mut f: impl FnMut(&K, &V) -> U) -> Vec<U> {
192		self.0.iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
193	}
194	/// Return a [Vec] of sorted key/value pairs by cloning this mapping.
195	pub fn to_vec(&self) -> Vec<(K, V)>
196	where
197		K: Clone,
198		V: Clone,
199	{
200		self.0.clone()
201	}
202	/// Return the [Vec] of sorted key/value pairs by consuming this mapping.
203	pub fn into_vec(self) -> Vec<(K, V)> {
204		self.0
205	}
206	/// Insert pair into the mapping.
207	///
208	/// Inserts some pair (`k`, `v`) into the mapping, replacing the existing pair whose key is `k`,
209	/// if any.
210	///
211	/// Returns [Some] value which was replaced, if any.
212	///
213	/// NOTE: This does an ordered insert and thus is slow. If you're inserting multiple items, use
214	/// [Self::extend] which is much more efficient or consider using an alternative data structure
215	/// if you're doing this a lot.
216	pub fn insert(&mut self, k: K, v: V) -> Option<(K, V)> {
217		match self.0.binary_search_by(|x| x.0.cmp(&k)) {
218			Ok(i) => Some(core::mem::replace(&mut self.0[i], (k, v))),
219			Err(i) => {
220				self.0.insert(i, (k, v));
221				None
222			},
223		}
224	}
225	/// Insert multiple pairs from an iterator.
226	///
227	/// Replaces any existing pairs which share a key with an element of the iterator.
228	pub fn extend(&mut self, iter: impl IntoIterator<Item = (K, V)>) {
229		self.0.splice(0..0, iter);
230		self.0.sort_by(|x, y| x.0.cmp(&y.0));
231		self.0.dedup_by(|x, y| x.0 == y.0);
232	}
233	/// Check if a key is in the mapping.
234	///
235	/// Returns `true` iff the mapping contains a pair whose key equals `k`.
236	pub fn contains_key<Q>(&self, k: &Q) -> bool
237	where
238		K: Borrow<Q>,
239		Q: Ord + ?Sized,
240	{
241		self.0.binary_search_by(|x| x.0.borrow().cmp(k)).is_ok()
242	}
243	/// Remove an item from the mapping by key.
244	///
245	/// Removes the item with key equal to `k` from the mapping.
246	///
247	/// Returns the value of the item removed, if any.
248	pub fn remove<Q>(&mut self, k: &Q) -> Option<(K, V)>
249	where
250		K: Borrow<Q>,
251		Q: Ord + ?Sized,
252	{
253		match self.0.binary_search_by(|x| x.0.borrow().cmp(k)) {
254			Ok(i) => Some(self.0.remove(i)),
255			Err(_) => None,
256		}
257	}
258	/// Filter items from the mapping.
259	///
260	/// Removes all pairs from the mapping for which `f` returns `false`.
261	pub fn retain(&mut self, mut f: impl FnMut(&K, &V) -> bool) {
262		self.0.retain(|x| f(&x.0, &x.1));
263	}
264	/// Remove all elements.
265	pub fn clear(&mut self) {
266		self.0.clear();
267	}
268	// TODO: Create traits `OrderedSetLike`/`OrderedMapLike` and make work with them.
269	/// Compares the pairs in two mappings.
270	///
271	/// Returns `true` iff every pair in the mapping is not found in `other`.
272	pub fn is_disjoint(&self, other: &VecMap<K, V>) -> bool
273	where
274		V: Ord,
275	{
276		vec_set::is_disjoint(self.iter(), other.iter())
277	}
278	/// Compares the keys in two mappings.
279	///
280	/// Returns `true` iff every key in the mapping is not found in the keys of `other`.
281	pub fn keys_disjoint<W>(&self, other: &VecMap<K, W>) -> bool {
282		vec_set::is_disjoint(self.keys(), other.keys())
283	}
284	/// Compares the keys in this mapping with the values in a set.
285	///
286	/// Returns `true` iff every key in the mapping is not found in `other`.
287	pub fn keys_disjoint_with_set(&self, other: &VecSet<K>) -> bool {
288		vec_set::is_disjoint(self.keys(), other.iter())
289	}
290}
291
292impl<K: Eq + PartialEq + Ord + PartialOrd, V> MapLike<K, V> for VecMap<K, V> {
293	fn insert(&mut self, k: K, v: V) -> Option<V> {
294		VecMap::<K, V>::insert(self, k, v).map(|(_, v)| v)
295	}
296	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
297		VecMap::<K, V>::extend(self, iter)
298	}
299	fn contains_key(&self, k: &K) -> bool {
300		VecMap::<K, V>::contains_key(self, k)
301	}
302	fn remove(&mut self, k: &K) -> Option<V> {
303		VecMap::<K, V>::remove(self, k).map(|x| x.1)
304	}
305	fn get(&self, k: &K) -> Option<&V> {
306		VecMap::<K, V>::get(self, k)
307	}
308	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
309		VecMap::<K, V>::get_mut(self, k)
310	}
311	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
312	where
313		K: 'a,
314	{
315		VecMap::<K, V>::keys(self)
316	}
317}
318
319impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for VecMap<K, V> {
320	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
321		match self.0.len() {
322			0 => write!(f, "[]"),
323			_ => {
324				write!(f, "[{:?}=>{:?}", self.0[0].0, self.0[0].1)?;
325				for i in 1..self.0.len() {
326					write!(f, ", {:?}=>{:?}", self.0[i].0, self.0[i].1)?;
327				}
328				write!(f, "]")
329			},
330		}
331	}
332}
333
334impl<K: fmt::Display, V: fmt::Display> fmt::Display for VecMap<K, V> {
335	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
336		match self.0.len() {
337			0 => write!(f, "[]"),
338			_ => {
339				write!(f, "[{}=>{}", self.0[0].0, self.0[0].1)?;
340				for i in 1..self.0.len() {
341					write!(f, ", {}=>{}", self.0[i].0, self.0[i].1)?;
342				}
343				write!(f, "]")
344			},
345		}
346	}
347}
348
349impl<K: Decode + Eq + PartialEq + Ord + PartialOrd, V: Decode> Decode for VecMap<K, V> {
350	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, DecodeError> {
351		Ok(Self::from_sorted(Vec::<(K, V)>::decode(input)?).map_err(|()| "set out-of-order")?)
352	}
353}
354
355impl<K, V> Default for VecMap<K, V> {
356	fn default() -> Self {
357		Self(Vec::new())
358	}
359}
360impl<K, V> AsRef<[(K, V)]> for VecMap<K, V> {
361	fn as_ref(&self) -> &[(K, V)] {
362		&self.0[..]
363	}
364}
365impl<K, V> From<VecMap<K, V>> for Vec<(K, V)> {
366	fn from(s: VecMap<K, V>) -> Vec<(K, V)> {
367		s.0
368	}
369}
370impl<K: Eq + PartialEq + Ord + PartialOrd, V> From<Vec<(K, V)>> for VecMap<K, V> {
371	fn from(mut v: Vec<(K, V)>) -> Self {
372		v.sort_by(|x, y| x.0.cmp(&y.0));
373		v.dedup_by(|x, y| x.0 == y.0);
374		Self(v)
375	}
376}
377impl<K: Eq + PartialEq + Ord + PartialOrd, V> FromIterator<(K, V)> for VecMap<K, V> {
378	fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
379		Vec::<(K, V)>::from_iter(iter).into()
380	}
381}
382impl<K: Eq + PartialEq + Ord + PartialOrd, V> Extend<(K, V)> for VecMap<K, V> {
383	fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
384		VecMap::<K, V>::extend(self, iter)
385	}
386}
387impl<K: Eq + PartialEq + Ord + PartialOrd, V> IntoIterator for VecMap<K, V> {
388	type Item = (K, V);
389	type IntoIter = <Vec<(K, V)> as IntoIterator>::IntoIter;
390
391	fn into_iter(self) -> Self::IntoIter {
392		self.0.into_iter()
393	}
394}
395
396#[cfg(test)]
397mod tests {
398	use super::*;
399	#[test]
400	fn encode_decode_works() {
401		let v = VecMap::<u32, u32>::from_iter((0..100).map(|j| ((j * 97) % 101, j)));
402		println!("{v}");
403		let e = v.encode();
404		let d = VecMap::<u32, u32>::decode(&mut &e[..]).unwrap();
405		assert_eq!(v, d);
406	}
407}
jam_types/vec_map.rs

jam_types/
vec_map.rs
