Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_core/src/map.rs

12.6 KiB, 7 runs

created by r1870400018:108, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Generic map traits and implementations.
2//!
3//! This module provides trait abstractions over different map types like `HashMap` and `BTreeMap`,
4//! allowing for backend-agnostic map usage. It includes basic map operations, error handling, and
5//! recursive map lookups.
6//!
7//! # Note on `Borrow` Support
8//! Currently, the `get` method on the `Map` trait cannot support the full flexibility of
9//! `std::borrow::Borrow` (e.g., using `&str` to look up `String` keys). This is because
10//! `HashMap::get` requires the borrowed type to implement `Hash`, while `BTreeMap::get` requires
11//! `Ord`. Without specialization (currently unstable in Rust), we cannot have different trait bounds
12//! for different implementations of the same trait method.
13//!
14//! This limitation will be addressed once specialization becomes available in stable Rust, allowing
15//! for more flexible key lookups while maintaining the efficiency of the underlying map implementations.
16//!
17//! # Examples
18//! ```
19//! use std::collections::HashMap;
20//! use crate::map::Map;
21//!
22//! let mut map = HashMap::new();
23//! map.insert("key".to_string(), 42);
24//!
25//! // Currently must use String for lookup, &str not supported yet
26//! assert_eq!(map.get(&"key".to_string()), Some(&42));
27//! ```
28use crate::{
29 prelude::*,
30};
31
32use std::{
33 //borrow::Borrow,
34 collections::{
35 btree_map,
36 hash_map,
37 BTreeMap,
38 HashMap,
39 },
40 fmt::Display,
41 hash::Hash,
42 marker::PhantomData,
43};
44
45
46pub trait GetOrErr<K, V> {
47 fn get_or_err(&self, k: &K) -> Outcome<&V>;
48}
49
50impl< K: Display + Hash + Eq, V> GetOrErr<K, V> for HashMap<K, V> {
51
52 #[inline(always)]
53 fn get_or_err(&self, k: &K) -> Outcome<&V> {
54 match self.get(k) {
55 Some(v) => Ok(v),
56 None => Err(err!(
57 "Map missing {}", k;
58 Missing, Key)),
59 }
60 }
61}
62
63impl< K: Display + Ord, V> GetOrErr<K, V> for BTreeMap<K, V> {
64
65 #[inline(always)]
66 fn get_or_err(&self, k: &K) -> Outcome<&V> {
67 match self.get(k) {
68 Some(v) => Ok(v),
69 None => Err(err!(
70 "Map missing {}", k;
71 Missing, Key)),
72 }
73 }
74}
75
76//======= Generic Maps ========================================================
77//
78// Inspired by https://github.com/bbqsrc/collections and
79// https://jackh726.github.io/rust/2022/05/04/a-shiny-future-with-gats.html
80//
81pub trait Map<K, V> {
82
83 type Iter<'iter>: Iterator<Item = (&'iter K, &'iter V)>
84 where Self: 'iter, K: 'iter, V: 'iter;
85
86 fn empty() -> Self;
87 fn len(&self) -> usize;
88 fn get(&self, k: &K) -> Option<&V>;
89 fn contains_key(&self, k: &K) -> bool;
90 fn iter<'a>(&'a self) -> Self::Iter<'a>;
91}
92
93pub trait MapMut<K, V>: Map<K, V> {
94
95 type IterMut<'iter>: Iterator<Item = (&'iter K, &'iter mut V)>
96 where Self: 'iter, K: 'iter, V: 'iter;
97
98 fn get_mut(&mut self, k: &K) -> Option<&mut V>;
99 fn insert(&mut self, k: K, v: V) -> Option<V>;
100 fn remove(&mut self, k: &K) -> Option<V>;
101 fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F);
102 fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a>;
103}
104
105impl<K: Hash + Eq, V> Map<K, V> for HashMap<K, V> {
106
107 type Iter<'iter> = hash_map::Iter<'iter, K, V> where Self: 'iter;
108
109 #[inline(always)]
110 fn empty() -> Self { HashMap::new() }
111 #[inline(always)]
112 fn len(&self) -> usize { self.len() }
113 #[inline(always)]
114 fn get(&self, k: &K) -> Option<&V> { self.get(k) }
115 #[inline(always)]
116 fn contains_key(&self, k: &K) -> bool { self.contains_key(k) }
117 #[inline(always)]
118 fn iter<'a>(&'a self) -> Self::Iter<'a> { self.iter() }
119}
120
121impl<K: Hash + Eq, V> MapMut<K, V> for HashMap<K, V> {
122
123 type IterMut <'iter> = hash_map::IterMut<'iter, K, V> where Self: 'iter;
124
125 #[inline(always)]
126 fn get_mut(&mut self, k: &K) -> Option<&mut V> { self.get_mut(k) }
127 #[inline(always)]
128 fn insert(&mut self, k: K, v: V) -> Option<V> { self.insert(k, v) }
129 #[inline(always)]
130 fn remove(&mut self, k: &K) -> Option<V> { self.remove(k) }
131 #[inline(always)]
132 fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) { self.retain(f); }
133 #[inline(always)]
134 fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a> { self.iter_mut() }
135}
136
137impl<K: Ord, V> Map<K, V> for BTreeMap<K, V> {
138
139 type Iter<'iter> = btree_map::Iter<'iter, K, V> where Self: 'iter;
140
141 #[inline(always)]
142 fn empty() -> Self { BTreeMap::new() }
143 #[inline(always)]
144 fn len(&self) -> usize { self.len() }
145 #[inline(always)]
146 fn get(&self, k: &K) -> Option<&V> { self.get(k) }
147 #[inline(always)]
148 fn contains_key(&self, k: &K) -> bool { self.contains_key(k) }
149 #[inline(always)]
150 fn iter<'a>(&'a self) -> Self::Iter<'a> { self.iter() }
151}
152
153impl<K: Ord, V> MapMut<K, V> for BTreeMap<K, V> {
154
155 type IterMut <'iter> = btree_map::IterMut<'iter, K, V> where Self: 'iter;
156
157 #[inline(always)]
158 fn get_mut(&mut self, k: &K) -> Option<&mut V> { self.get_mut(k) }
159 #[inline(always)]
160 fn insert(&mut self, k: K, v: V) -> Option<V> { self.insert(k, v) }
161 #[inline(always)]
162 fn remove(&mut self, k: &K) -> Option<V> { self.remove(k) }
163 #[inline(always)]
164 fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) { self.retain(f); }
165 #[inline(always)]
166 fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a> { self.iter_mut() }
167}
168
169impl<K: 'static, V: 'static> Map<K, V> for () {
170 type Iter<'a> = EmptyIter<'a, K, V>;
171
172 #[inline(always)]
173 fn empty() -> Self { () }
174 #[inline(always)]
175 fn len(&self) -> usize { 0 }
176 #[inline(always)]
177 fn get(&self, _k: &K) -> Option<&V> { None }
178 #[inline(always)]
179 fn contains_key(&self, _k: &K) -> bool { false }
180 #[inline(always)]
181 fn iter<'a>(&'a self) -> Self::Iter<'a> {
182 EmptyIter(
183 PhantomData::<&()>,
184 PhantomData::<K>,
185 PhantomData::<V>,
186 )
187 }
188}
189
190impl<K: 'static, V: 'static> MapMut<K, V> for () {
191 type IterMut<'a> = EmptyIterMut<'a, K, V>;
192
193 #[inline(always)]
194 fn get_mut(&mut self, _k: &K) -> Option<&mut V> { None }
195 #[inline(always)]
196 fn insert(&mut self, _k: K, _v: V) -> Option<V> { None }
197 #[inline(always)]
198 fn remove(&mut self, _k: &K) -> Option<V> { None }
199 #[inline(always)]
200 fn retain<F>(&mut self, _f: F) where F: FnMut(&K, &mut V) -> bool, { }
201 #[inline(always)]
202 fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a> {
203 EmptyIterMut(
204 PhantomData::<&mut ()>,
205 PhantomData::<K>,
206 PhantomData::<V>,
207 )
208 }
209}
210
211pub struct EmptyIter<'a, K, V>(
212 PhantomData<&'a ()>,
213 PhantomData<K>,
214 PhantomData<V>,
215);
216
217impl<'a, K: 'a, V: 'a> Iterator for EmptyIter<'a, K, V> {
218 type Item = (&'a K, &'a V);
219
220 fn next(&mut self) -> Option<Self::Item> { None }
221}
222
223pub struct EmptyIterMut<'a, K, V>(
224 PhantomData<&'a mut ()>,
225 PhantomData<K>,
226 PhantomData<V>,
227);
228
229impl<'a, K: 'a, V: 'a> Iterator for EmptyIterMut<'a, K, V> {
230 type Item = (&'a K, &'a mut V);
231
232 fn next(&mut self) -> Option<Self::Item> { None }
233}
234
235//======= Recursive Maps ======================================================
236// Basically works by wrapping every value in an enum, delineating it as a value or another key for
237// recursive dereferncing.
238//
239
240pub trait KeyOrVal<K, V> {
241 fn key(&self) -> Option<&K>;
242 fn val(&self) -> Option<&V>;
243}
244
245pub trait MapRec<'a, K, V, KV>: Map<K, KV> where KV: KeyOrVal<K, V> + 'a {
246 fn get_recursive(&'a self, k: &K) -> Option<&'a V> {
247 match self.get(k) {
248 Some(kv) => match kv.key() {
249 Some(k2) => self.get_recursive(k2),
250 None => kv.val(),
251 },
252 None => None,
253 }
254 }
255}
256
257impl<'a, K: Hash + Eq, V, KV> MapRec<'a, K, V, KV> for HashMap<K, KV> where KV: KeyOrVal<K, V> + 'a {}
258impl<'a, K: Ord, V, KV> MapRec<'a, K, V, KV> for BTreeMap<K, KV> where KV: KeyOrVal<K, V> + 'a {}
259
260#[derive(Clone, Debug)]
261pub enum Recursive<K, V> {
262 Key(K),
263 Val(V),
264}
265
266impl<K, V> KeyOrVal<K, V> for Recursive<K, V> {
267 fn key(&self) -> Option<&K> {
268 match self {
269 Self::Key(k) => Some(k),
270 Self::Val(_) => None,
271 }
272 }
273 fn val(&self) -> Option<&V> {
274 match self {
275 Self::Key(_) => None,
276 Self::Val(v) => Some(v),
277 }
278 }
279}
280
281
282//// Old...
283//pub trait HashMapKey: Debug + Eq + Hash {}
284//pub trait BTreeMapKey: Debug + Eq + Ord {}
285//
286//#[derive(Clone, Debug, Hash)]
287//pub enum HashMapEntry<K, V>
288//where
289// K: HashMapKey,
290//{
291// Key(K),
292// Value(V),
293//}
294//
295//pub trait RecursiveHashMapEntry<K, V>
296//where
297// K: HashMapKey,
298//{
299// fn as_entry(&self) -> &HashMapEntry<K, V>;
300//}
301//
302//impl<K, V> RecursiveHashMapEntry<K, V> for HashMapEntry<K, V>
303//where
304// K: HashMapKey,
305//{
306// fn as_entry(&self) -> &Self {
307// self
308// }
309//}
310//
311//pub trait RecursiveHashMap<K, V>
312//where
313// K: HashMapKey,
314//{
315// fn get_recursive<Q: ?Sized>(&self, k: &Q) -> Option<&V>
316// where
317// K: Borrow<Q>,
318// Q: HashMapKey;
319//}
320//
321//impl<K, V1, V2> RecursiveHashMap<K, V2> for HashMap<K, V1>
322//where
323// K: HashMapKey,
324// V1: RecursiveHashMapEntry<K, V2>,
325//{
326// fn get_recursive<Q: ?Sized>(&self, k: &Q) -> Option<&V2>
327// where
328// K: Borrow<Q>,
329// Q: HashMapKey,
330// {
331// match self.get(k) {
332// Some(e) => match e.as_entry() {
333// HashMapEntry::Key(k) => self.get_recursive(k.borrow()),
334// HashMapEntry::Value(v) => Some(v),
335// },
336// None => None,
337// }
338// }
339//}
340//
341//#[derive(Clone, Debug)]
342//pub enum BTreeMapEntry<K, V>
343//where
344// K: BTreeMapKey,
345//{
346// Key(K),
347// Value(V),
348//}
349//
350//pub trait RecursiveBTreeMapEntry<K, V>
351//where
352// K: BTreeMapKey,
353//{
354// fn as_entry(&self) -> &BTreeMapEntry<K, V>;
355//}
356//
357//impl<K, V> RecursiveBTreeMapEntry<K, V> for BTreeMapEntry<K, V>
358//where
359// K: BTreeMapKey,
360//{
361// fn as_entry(&self) -> &Self {
362// self
363// }
364//}
365//
366//pub trait RecursiveBTreeMap<K, V>
367//where
368// K: BTreeMapKey,
369//{
370// fn get_recursive<Q: ?Sized>(&self, k: &Q) -> Option<&V>
371// where
372// K: Borrow<Q>,
373// Q: BTreeMapKey;
374//}
375//
376//impl<K, V1, V2> RecursiveBTreeMap<K, V2> for BTreeMap<K, V1>
377//where
378// K: BTreeMapKey,
379// V1: RecursiveBTreeMapEntry<K, V2>,
380//{
381// fn get_recursive<Q: ?Sized>(&self, k: &Q) -> Option<&V2>
382// where
383// K: Borrow<Q>,
384// Q: BTreeMapKey,
385// {
386// match self.get(k) {
387// Some(e) => match e.as_entry() {
388// BTreeMapEntry::Key(k) => self.get_recursive(k.borrow()),
389// BTreeMapEntry::Value(v) => Some(v),
390// },
391// None => None,
392// }
393// }
394//}
395//
396//impl HashMapKey for String {}
397//impl HashMapKey for str {}
398//impl HashMapKey for &'static str {}
399//impl HashMapKey for u8 {}
400//impl HashMapKey for u16 {}
401//impl HashMapKey for u32 {}
402//impl HashMapKey for u64 {}
403//
404//impl BTreeMapKey for String {}
405//impl BTreeMapKey for str {}
406//impl BTreeMapKey for &'static str {}
407//impl BTreeMapKey for u8 {}
408//impl BTreeMapKey for u16 {}
409//impl BTreeMapKey for u32 {}
410//impl BTreeMapKey for u64 {}
411////impl BTreeMapKey for [u8; 32] {}
412
413//#[cfg(test)]
414//mod tests {
415// use super::*;
416// use crate::prelude::*;
417//
418// //#[test]
419// //fn test_recursive_hashmap_simple_get() -> Outcome<()> {
420// // let mut map: HashMap<u8, HashMapEntry<u8, u8>> = HashMap::new();
421// // map.insert(1, HashMapEntry::Value(1));
422// // map.insert(2, HashMapEntry::Value(2));
423// // map.insert(3, HashMapEntry::Key(1));
424// // assert_eq!(map.get_recursive(&3), Some(&1));
425// // Ok(())
426// //}
427//
428// //#[test]
429// //fn test_recursive_btreemap_simple_get() -> Outcome<()> {
430// // let mut map: BTreeMap<u8, BTreeMapEntry<u8, u8>> = BTreeMap::new();
431// // map.insert(1, BTreeMapEntry::Value(1));
432// // map.insert(2, BTreeMapEntry::Value(2));
433// // map.insert(3, BTreeMapEntry::Key(1));
434// // assert_eq!(map.get_recursive(&3), Some(&1));
435// // Ok(())
436// //}
437//
438// #[test]
439// fn test_generic_recursive_map_00() -> Outcome<()> {
440// let mut map: BTreeMap<u8, Recursive<u8, u8>> = BTreeMap::new();
441// map.insert(1, Recursive::Val(1));
442// map.insert(2, Recursive::Val(2));
443// map.insert(3, Recursive::Key(1));
444// assert_eq!(map.get_recursive(&3), Some(&1));
445// Ok(())
446// }
447//
448// #[test]
449// fn test_generic_recursive_map_01() -> Outcome<()> {
450// let mut map: HashMap<u8, Recursive<u8, u8>> = HashMap::new();
451// map.insert(1, Recursive::Val(1));
452// map.insert(2, Recursive::Val(2));
453// map.insert(3, Recursive::Key(1));
454// assert_eq!(map.get_recursive(&3), Some(&1));
455// Ok(())
456// }
457//}