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

jam_types/
vec_map.rs
