lattices/
collections.rs

1//! Simple singleton or array collection with [`cc_traits`] implementations.
2
3#[cfg(feature = "alloc")]
4use alloc::collections::BTreeMap;
5#[cfg(feature = "alloc")]
6use alloc::vec::Vec;
7use core::borrow::Borrow;
8use core::hash::Hash;
9use core::marker::PhantomData;
10#[cfg(feature = "std")]
11use std::collections::HashMap;
12
13use cc_traits::{
14    Collection, CollectionMut, CollectionRef, Get, GetKeyValue, GetKeyValueMut, GetMut, Iter,
15    IterMut, Keyed, KeyedRef, Len, MapIter, MapIterMut, SimpleCollectionRef, SimpleKeyedRef,
16    covariant_item_mut, covariant_item_ref, covariant_key_ref, simple_collection_ref,
17    simple_keyed_ref,
18};
19
20/// Trait for transforming the values of a map without changing the overall type of the data structure.
21pub trait MapMapValues<OldVal> {
22    /// Output type, should be `Self` but with `OldVal` replaced with `NewVal`.
23    type MapValue<NewVal>;
24
25    /// Map the values into using the `map_fn`.
26    fn map_values<NewVal, MapFn>(self, map_fn: MapFn) -> Self::MapValue<NewVal>
27    where
28        MapFn: FnMut(OldVal) -> NewVal;
29}
30
31#[cfg(feature = "std")]
32impl<Key, OldVal> MapMapValues<OldVal> for HashMap<Key, OldVal>
33where
34    Key: Eq + Hash,
35{
36    type MapValue<NewVal> = HashMap<Key, NewVal>;
37
38    fn map_values<NewVal, MapFn>(self, mut map_fn: MapFn) -> Self::MapValue<NewVal>
39    where
40        MapFn: FnMut(OldVal) -> NewVal,
41    {
42        self.into_iter()
43            .map(|(k, val)| (k, (map_fn)(val)))
44            .collect()
45    }
46}
47
48#[cfg(feature = "alloc")]
49impl<Key, OldVal> MapMapValues<OldVal> for BTreeMap<Key, OldVal>
50where
51    Key: Eq + Ord,
52{
53    type MapValue<NewVal> = BTreeMap<Key, NewVal>;
54
55    fn map_values<NewVal, MapFn>(self, mut map_fn: MapFn) -> Self::MapValue<NewVal>
56    where
57        MapFn: FnMut(OldVal) -> NewVal,
58    {
59        self.into_iter()
60            .map(|(k, val)| (k, (map_fn)(val)))
61            .collect()
62    }
63}
64
65/// A [`Vec`]-wrapper representing a naively-implemented set.
66#[cfg(feature = "alloc")]
67#[repr(transparent)]
68#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
69#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
70pub struct VecSet<T>(pub Vec<T>);
71#[cfg(feature = "alloc")]
72impl<T> IntoIterator for VecSet<T> {
73    type Item = T;
74    type IntoIter = alloc::vec::IntoIter<T>;
75
76    fn into_iter(self) -> Self::IntoIter {
77        self.0.into_iter()
78    }
79}
80#[cfg(feature = "alloc")]
81impl<T> From<Vec<T>> for VecSet<T> {
82    fn from(value: Vec<T>) -> Self {
83        Self(value)
84    }
85}
86#[cfg(feature = "alloc")]
87impl<T> Collection for VecSet<T> {
88    type Item = T;
89}
90#[cfg(feature = "alloc")]
91impl<T> Len for VecSet<T> {
92    fn len(&self) -> usize {
93        self.0.len()
94    }
95
96    fn is_empty(&self) -> bool {
97        self.0.is_empty()
98    }
99}
100#[cfg(feature = "alloc")]
101impl<T> CollectionRef for VecSet<T> {
102    type ItemRef<'a>
103        = &'a Self::Item
104    where
105        Self: 'a;
106
107    covariant_item_ref!();
108}
109#[cfg(feature = "alloc")]
110impl<T> SimpleCollectionRef for VecSet<T> {
111    simple_collection_ref!();
112}
113#[cfg(feature = "alloc")]
114impl<'a, Q, T> Get<&'a Q> for VecSet<T>
115where
116    T: Borrow<Q>,
117    Q: Eq + ?Sized,
118{
119    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
120        self.0.iter().find(|&k| key == k.borrow())
121    }
122}
123#[cfg(feature = "alloc")]
124impl<T> CollectionMut for VecSet<T> {
125    type ItemMut<'a>
126        = &'a mut Self::Item
127    where
128        Self: 'a;
129
130    covariant_item_mut!();
131}
132#[cfg(feature = "alloc")]
133impl<'a, Q, T> GetMut<&'a Q> for VecSet<T>
134where
135    T: Borrow<Q>,
136    Q: Eq + ?Sized,
137{
138    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
139        self.0.iter_mut().find(|k| key == T::borrow(k))
140    }
141}
142#[cfg(feature = "alloc")]
143impl<T> Iter for VecSet<T> {
144    type Iter<'a>
145        = core::slice::Iter<'a, T>
146    where
147        Self: 'a;
148
149    fn iter(&self) -> Self::Iter<'_> {
150        self.0.iter()
151    }
152}
153#[cfg(feature = "alloc")]
154impl<T> IterMut for VecSet<T> {
155    type IterMut<'a>
156        = core::slice::IterMut<'a, T>
157    where
158        Self: 'a;
159
160    fn iter_mut(&mut self) -> Self::IterMut<'_> {
161        self.0.iter_mut()
162    }
163}
164
165/// A [`Vec`]-wrapper representing a naively implemented map.
166#[cfg(feature = "alloc")]
167#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
168#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
169pub struct VecMap<K, V> {
170    /// Keys, should be the same length as and correspond 1:1 to `vals`.
171    pub keys: Vec<K>,
172    /// Vals, should be the same length as and correspond 1:1 to `keys`.
173    pub vals: Vec<V>,
174}
175#[cfg(feature = "alloc")]
176impl<K, V> VecMap<K, V> {
177    /// Create a new `VecMap` from the separate `keys` and `vals` vecs.
178    ///
179    /// Panics if `keys` and `vals` are not the same length.
180    pub fn new(keys: Vec<K>, vals: Vec<V>) -> Self {
181        assert_eq!(keys.len(), vals.len());
182        Self { keys, vals }
183    }
184}
185#[cfg(feature = "alloc")]
186impl<K, V> IntoIterator for VecMap<K, V> {
187    type Item = (K, V);
188    type IntoIter = core::iter::Zip<alloc::vec::IntoIter<K>, alloc::vec::IntoIter<V>>;
189
190    fn into_iter(self) -> Self::IntoIter {
191        self.keys.into_iter().zip(self.vals)
192    }
193}
194#[cfg(feature = "alloc")]
195impl<K, V> Collection for VecMap<K, V> {
196    type Item = V;
197}
198#[cfg(feature = "alloc")]
199impl<K, V> Len for VecMap<K, V> {
200    fn len(&self) -> usize {
201        core::cmp::min(self.keys.len(), self.vals.len())
202    }
203
204    fn is_empty(&self) -> bool {
205        self.keys.is_empty() || self.vals.is_empty()
206    }
207}
208#[cfg(feature = "alloc")]
209impl<K, V> CollectionRef for VecMap<K, V> {
210    type ItemRef<'a>
211        = &'a Self::Item
212    where
213        Self: 'a;
214
215    covariant_item_ref!();
216}
217#[cfg(feature = "alloc")]
218impl<K, V> SimpleCollectionRef for VecMap<K, V> {
219    simple_collection_ref!();
220}
221#[cfg(feature = "alloc")]
222impl<'a, Q, K, V> Get<&'a Q> for VecMap<K, V>
223where
224    K: Borrow<Q>,
225    Q: Eq + ?Sized,
226{
227    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
228        self.keys
229            .iter()
230            .position(|k| key == k.borrow())
231            .and_then(|i| self.vals.get(i))
232    }
233}
234#[cfg(feature = "alloc")]
235impl<K, V> CollectionMut for VecMap<K, V> {
236    type ItemMut<'a>
237        = &'a mut Self::Item
238    where
239        Self: 'a;
240
241    covariant_item_mut!();
242}
243#[cfg(feature = "alloc")]
244impl<'a, Q, K, V> GetMut<&'a Q> for VecMap<K, V>
245where
246    K: Borrow<Q>,
247    Q: Eq + ?Sized,
248{
249    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
250        self.keys
251            .iter()
252            .position(|k| key == k.borrow())
253            .and_then(|i| self.vals.get_mut(i))
254    }
255}
256#[cfg(feature = "alloc")]
257impl<K, V> Keyed for VecMap<K, V> {
258    type Key = K;
259}
260#[cfg(feature = "alloc")]
261impl<K, V> KeyedRef for VecMap<K, V> {
262    type KeyRef<'a>
263        = &'a Self::Key
264    where
265        Self: 'a;
266
267    covariant_key_ref!();
268}
269#[cfg(feature = "alloc")]
270impl<'a, Q, K, V> GetKeyValue<&'a Q> for VecMap<K, V>
271where
272    K: Borrow<Q>,
273    Q: Eq + ?Sized,
274{
275    fn get_key_value(&self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemRef<'_>)> {
276        self.keys
277            .iter()
278            .zip(self.vals.iter())
279            .find(|(k, _v)| key == K::borrow(k))
280    }
281}
282#[cfg(feature = "alloc")]
283impl<'a, Q, K, V> GetKeyValueMut<&'a Q> for VecMap<K, V>
284where
285    K: Borrow<Q>,
286    Q: Eq + ?Sized,
287{
288    fn get_key_value_mut(&mut self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemMut<'_>)> {
289        self.keys
290            .iter()
291            .zip(self.vals.iter_mut())
292            .find(|(k, _v)| key == K::borrow(k))
293    }
294}
295#[cfg(feature = "alloc")]
296impl<K, V> SimpleKeyedRef for VecMap<K, V> {
297    simple_keyed_ref!();
298}
299#[cfg(feature = "alloc")]
300impl<K, V> MapIter for VecMap<K, V> {
301    type Iter<'a>
302        = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::Iter<'a, V>>
303    where
304        Self: 'a;
305
306    fn iter(&self) -> Self::Iter<'_> {
307        self.keys.iter().zip(self.vals.iter())
308    }
309}
310#[cfg(feature = "alloc")]
311impl<K, V> MapIterMut for VecMap<K, V> {
312    type IterMut<'a>
313        = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::IterMut<'a, V>>
314    where
315        Self: 'a;
316
317    fn iter_mut(&mut self) -> Self::IterMut<'_> {
318        self.keys.iter().zip(self.vals.iter_mut())
319    }
320}
321#[cfg(feature = "alloc")]
322impl<K, OldVal> MapMapValues<OldVal> for VecMap<K, OldVal> {
323    type MapValue<NewVal> = VecMap<K, NewVal>;
324
325    fn map_values<NewVal, MapFn>(self, map_fn: MapFn) -> Self::MapValue<NewVal>
326    where
327        MapFn: FnMut(OldVal) -> NewVal,
328    {
329        let Self { keys, vals } = self;
330        let vals = vals.into_iter().map(map_fn).collect();
331        VecMap { keys, vals }
332    }
333}
334
335/// A type that will always be an empty set.
336#[derive(Default, Debug, Clone, Copy, PartialOrd, Ord, Hash)]
337#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
338pub struct EmptySet<T> {
339    _x: PhantomData<T>,
340}
341
342impl<T, Rhs> PartialEq<Rhs> for EmptySet<T>
343where
344    Rhs: Len,
345{
346    fn eq(&self, other: &Rhs) -> bool {
347        other.is_empty()
348    }
349}
350
351impl<T> Eq for EmptySet<T> {}
352
353impl<T> Collection for EmptySet<T> {
354    type Item = T;
355}
356
357impl<T> CollectionRef for EmptySet<T> {
358    type ItemRef<'a>
359        = &'a Self::Item
360    where
361        Self::Item: 'a;
362
363    covariant_item_ref!();
364}
365impl<T> SimpleCollectionRef for EmptySet<T> {
366    simple_collection_ref!();
367}
368
369impl<'a, Q, T> Get<&'a Q> for EmptySet<T> {
370    fn get(&self, _key: &'a Q) -> Option<Self::ItemRef<'_>> {
371        None
372    }
373}
374
375impl<T> Len for EmptySet<T> {
376    fn len(&self) -> usize {
377        0
378    }
379}
380
381impl<T> Iter for EmptySet<T> {
382    type Iter<'a>
383        = core::iter::Empty<&'a T>
384    where
385        T: 'a;
386
387    fn iter(&self) -> Self::Iter<'_> {
388        core::iter::empty()
389    }
390}
391
392impl<T> IntoIterator for EmptySet<T> {
393    type Item = T;
394    type IntoIter = core::iter::Empty<T>;
395
396    fn into_iter(self) -> Self::IntoIter {
397        core::iter::empty()
398    }
399}
400
401/// A wrapper around an item, representing a singleton set.
402#[repr(transparent)]
403#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
404#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
405pub struct SingletonSet<T>(pub T);
406impl<T> IntoIterator for SingletonSet<T> {
407    type Item = T;
408    type IntoIter = core::iter::Once<T>;
409
410    fn into_iter(self) -> Self::IntoIter {
411        core::iter::once(self.0)
412    }
413}
414impl<T> From<T> for SingletonSet<T> {
415    fn from(value: T) -> Self {
416        Self(value)
417    }
418}
419impl<T> Collection for SingletonSet<T> {
420    type Item = T;
421}
422impl<T> Len for SingletonSet<T> {
423    fn len(&self) -> usize {
424        1
425    }
426}
427impl<T> CollectionRef for SingletonSet<T> {
428    type ItemRef<'a>
429        = &'a Self::Item
430    where
431        Self: 'a;
432
433    covariant_item_ref!();
434}
435impl<T> SimpleCollectionRef for SingletonSet<T> {
436    simple_collection_ref!();
437}
438impl<'a, Q, T> Get<&'a Q> for SingletonSet<T>
439where
440    T: Borrow<Q>,
441    Q: Eq + ?Sized,
442{
443    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
444        (key == self.0.borrow()).then_some(&self.0)
445    }
446}
447impl<T> CollectionMut for SingletonSet<T> {
448    type ItemMut<'a>
449        = &'a mut T
450    where
451        Self: 'a;
452
453    covariant_item_mut!();
454}
455impl<'a, Q, T> GetMut<&'a Q> for SingletonSet<T>
456where
457    T: Borrow<Q>,
458    Q: Eq + ?Sized,
459{
460    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
461        (key == self.0.borrow()).then_some(&mut self.0)
462    }
463}
464impl<T> Iter for SingletonSet<T> {
465    type Iter<'a>
466        = core::iter::Once<&'a T>
467    where
468        Self: 'a;
469
470    fn iter(&self) -> Self::Iter<'_> {
471        core::iter::once(&self.0)
472    }
473}
474impl<T> IterMut for SingletonSet<T> {
475    type IterMut<'a>
476        = core::iter::Once<&'a mut T>
477    where
478        Self: 'a;
479
480    fn iter_mut(&mut self) -> Self::IterMut<'_> {
481        core::iter::once(&mut self.0)
482    }
483}
484
485/// A key-value entry wrapper representing a singleton map.
486#[derive(Debug, Clone, Copy, PartialOrd, Ord, Hash, Default)]
487#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
488pub struct EmptyMap<K, V>(pub PhantomData<K>, pub PhantomData<V>);
489impl<K, V> IntoIterator for EmptyMap<K, V> {
490    type Item = (K, V);
491    type IntoIter = core::iter::Empty<(K, V)>;
492
493    fn into_iter(self) -> Self::IntoIter {
494        core::iter::empty()
495    }
496}
497
498impl<K, V, Rhs> PartialEq<Rhs> for EmptyMap<K, V>
499where
500    Rhs: Len,
501{
502    fn eq(&self, other: &Rhs) -> bool {
503        other.is_empty()
504    }
505}
506
507impl<K, V> Eq for EmptyMap<K, V> {}
508
509impl<K, V> Collection for EmptyMap<K, V> {
510    type Item = V;
511}
512impl<K, V> Len for EmptyMap<K, V> {
513    fn len(&self) -> usize {
514        0
515    }
516}
517impl<K, V> CollectionRef for EmptyMap<K, V> {
518    type ItemRef<'a>
519        = &'a Self::Item
520    where
521        Self: 'a;
522
523    covariant_item_ref!();
524}
525impl<K, V> SimpleCollectionRef for EmptyMap<K, V> {
526    simple_collection_ref!();
527}
528impl<'a, Q, K, V> Get<&'a Q> for EmptyMap<K, V>
529where
530    K: Borrow<Q>,
531    Q: Eq + ?Sized,
532{
533    fn get(&self, _key: &'a Q) -> Option<Self::ItemRef<'_>> {
534        None
535    }
536}
537impl<K, V> CollectionMut for EmptyMap<K, V> {
538    type ItemMut<'a>
539        = &'a mut Self::Item
540    where
541        Self: 'a;
542
543    covariant_item_mut!();
544}
545impl<'a, Q, K, V> GetMut<&'a Q> for EmptyMap<K, V>
546where
547    K: Borrow<Q>,
548    Q: Eq + ?Sized,
549{
550    fn get_mut(&mut self, _key: &'a Q) -> Option<Self::ItemMut<'_>> {
551        None
552    }
553}
554impl<K, V> Keyed for EmptyMap<K, V> {
555    type Key = K;
556}
557impl<K, V> KeyedRef for EmptyMap<K, V> {
558    type KeyRef<'a>
559        = &'a Self::Key
560    where
561        Self: 'a;
562
563    covariant_key_ref!();
564}
565impl<'a, Q, K, V> GetKeyValue<&'a Q> for EmptyMap<K, V>
566where
567    K: Borrow<Q>,
568    Q: Eq + ?Sized,
569{
570    fn get_key_value(&self, _key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemRef<'_>)> {
571        None
572    }
573}
574impl<'a, Q, K, V> GetKeyValueMut<&'a Q> for EmptyMap<K, V>
575where
576    K: Borrow<Q>,
577    Q: Eq + ?Sized,
578{
579    fn get_key_value_mut(&mut self, _key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemMut<'_>)> {
580        None
581    }
582}
583impl<K, V> Iter for EmptyMap<K, V> {
584    type Iter<'a>
585        = core::iter::Empty<&'a V>
586    where
587        Self: 'a;
588
589    fn iter(&self) -> Self::Iter<'_> {
590        core::iter::empty()
591    }
592}
593impl<K, V> SimpleKeyedRef for EmptyMap<K, V> {
594    simple_keyed_ref!();
595}
596impl<K, V> MapIter for EmptyMap<K, V> {
597    type Iter<'a>
598        = core::iter::Empty<(&'a K, &'a V)>
599    where
600        Self: 'a;
601
602    fn iter(&self) -> Self::Iter<'_> {
603        core::iter::empty()
604    }
605}
606impl<K, V> MapIterMut for EmptyMap<K, V> {
607    type IterMut<'a>
608        = core::iter::Empty<(&'a K, &'a mut V)>
609    where
610        Self: 'a;
611
612    fn iter_mut(&mut self) -> Self::IterMut<'_> {
613        core::iter::empty()
614    }
615}
616
617/// A key-value entry wrapper representing a singleton map.
618#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
619#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
620pub struct SingletonMap<K, V>(pub K, pub V);
621impl<K, V> IntoIterator for SingletonMap<K, V> {
622    type Item = (K, V);
623    type IntoIter = core::iter::Once<(K, V)>;
624
625    fn into_iter(self) -> Self::IntoIter {
626        core::iter::once((self.0, self.1))
627    }
628}
629impl<K, V> From<(K, V)> for SingletonMap<K, V> {
630    fn from((k, v): (K, V)) -> Self {
631        Self(k, v)
632    }
633}
634impl<K, V> Collection for SingletonMap<K, V> {
635    type Item = V;
636}
637impl<K, V> Len for SingletonMap<K, V> {
638    fn len(&self) -> usize {
639        1
640    }
641}
642impl<K, V> CollectionRef for SingletonMap<K, V> {
643    type ItemRef<'a>
644        = &'a Self::Item
645    where
646        Self: 'a;
647
648    covariant_item_ref!();
649}
650impl<K, V> SimpleCollectionRef for SingletonMap<K, V> {
651    simple_collection_ref!();
652}
653impl<'a, Q, K, V> Get<&'a Q> for SingletonMap<K, V>
654where
655    K: Borrow<Q>,
656    Q: Eq + ?Sized,
657{
658    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
659        (key == self.0.borrow()).then_some(&self.1)
660    }
661}
662impl<K, V> CollectionMut for SingletonMap<K, V> {
663    type ItemMut<'a>
664        = &'a mut Self::Item
665    where
666        Self: 'a;
667
668    covariant_item_mut!();
669}
670impl<'a, Q, K, V> GetMut<&'a Q> for SingletonMap<K, V>
671where
672    K: Borrow<Q>,
673    Q: Eq + ?Sized,
674{
675    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
676        (key == self.0.borrow()).then_some(&mut self.1)
677    }
678}
679impl<K, V> Keyed for SingletonMap<K, V> {
680    type Key = K;
681}
682impl<K, V> KeyedRef for SingletonMap<K, V> {
683    type KeyRef<'a>
684        = &'a Self::Key
685    where
686        Self: 'a;
687
688    covariant_key_ref!();
689}
690impl<'a, Q, K, V> GetKeyValue<&'a Q> for SingletonMap<K, V>
691where
692    K: Borrow<Q>,
693    Q: Eq + ?Sized,
694{
695    fn get_key_value(&self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemRef<'_>)> {
696        (key == self.0.borrow()).then_some((&self.0, &self.1))
697    }
698}
699impl<'a, Q, K, V> GetKeyValueMut<&'a Q> for SingletonMap<K, V>
700where
701    K: Borrow<Q>,
702    Q: Eq + ?Sized,
703{
704    fn get_key_value_mut(&mut self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemMut<'_>)> {
705        (key == self.0.borrow()).then_some((&self.0, &mut self.1))
706    }
707}
708impl<K, V> Iter for SingletonMap<K, V> {
709    type Iter<'a>
710        = core::iter::Once<&'a V>
711    where
712        Self: 'a;
713
714    fn iter(&self) -> Self::Iter<'_> {
715        core::iter::once(&self.1)
716    }
717}
718impl<K, V> SimpleKeyedRef for SingletonMap<K, V> {
719    simple_keyed_ref!();
720}
721impl<K, V> MapIter for SingletonMap<K, V> {
722    type Iter<'a>
723        = core::iter::Once<(&'a K, &'a V)>
724    where
725        Self: 'a;
726
727    fn iter(&self) -> Self::Iter<'_> {
728        core::iter::once((&self.0, &self.1))
729    }
730}
731impl<K, V> MapIterMut for SingletonMap<K, V> {
732    type IterMut<'a>
733        = core::iter::Once<(&'a K, &'a mut V)>
734    where
735        Self: 'a;
736
737    fn iter_mut(&mut self) -> Self::IterMut<'_> {
738        core::iter::once((&self.0, &mut self.1))
739    }
740}
741impl<K, OldVal> MapMapValues<OldVal> for SingletonMap<K, OldVal> {
742    type MapValue<NewVal> = SingletonMap<K, NewVal>;
743
744    fn map_values<NewVal, MapFn>(self, mut map_fn: MapFn) -> Self::MapValue<NewVal>
745    where
746        MapFn: FnMut(OldVal) -> NewVal,
747    {
748        let Self(key, val) = self;
749        let val = (map_fn)(val);
750        SingletonMap(key, val)
751    }
752}
753
754/// A wrapper around `Option`, representing either a singleton or empty set.
755#[repr(transparent)]
756#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
757#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
758pub struct OptionSet<T>(pub Option<T>);
759impl<T> Default for OptionSet<T> {
760    fn default() -> Self {
761        Self(None)
762    }
763}
764impl<T> IntoIterator for OptionSet<T> {
765    type Item = T;
766    type IntoIter = core::option::IntoIter<T>;
767
768    fn into_iter(self) -> Self::IntoIter {
769        self.0.into_iter()
770    }
771}
772impl<T, U> From<U> for OptionSet<T>
773where
774    U: Into<Option<T>>,
775{
776    fn from(value: U) -> Self {
777        Self(value.into())
778    }
779}
780impl<T> Collection for OptionSet<T> {
781    type Item = T;
782}
783impl<T> Len for OptionSet<T> {
784    fn len(&self) -> usize {
785        self.0.is_some() as usize
786    }
787}
788impl<T> CollectionRef for OptionSet<T> {
789    type ItemRef<'a>
790        = &'a Self::Item
791    where
792        Self: 'a;
793
794    covariant_item_ref!();
795}
796impl<T> SimpleCollectionRef for OptionSet<T> {
797    simple_collection_ref!();
798}
799impl<'a, Q, T> Get<&'a Q> for OptionSet<T>
800where
801    T: Borrow<Q>,
802    Q: Eq + ?Sized,
803{
804    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
805        self.0.as_ref().filter(|inner| key == (**inner).borrow())
806    }
807}
808impl<T> CollectionMut for OptionSet<T> {
809    type ItemMut<'a>
810        = &'a mut T
811    where
812        Self: 'a;
813
814    covariant_item_mut!();
815}
816impl<'a, Q, T> GetMut<&'a Q> for OptionSet<T>
817where
818    T: Borrow<Q>,
819    Q: Eq + ?Sized,
820{
821    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
822        self.0.as_mut().filter(|inner| key == (**inner).borrow())
823    }
824}
825impl<T> Iter for OptionSet<T> {
826    type Iter<'a>
827        = core::option::Iter<'a, T>
828    where
829        Self: 'a;
830
831    fn iter(&self) -> Self::Iter<'_> {
832        self.0.iter()
833    }
834}
835impl<T> IterMut for OptionSet<T> {
836    type IterMut<'a>
837        = core::option::IterMut<'a, T>
838    where
839        Self: 'a;
840
841    fn iter_mut(&mut self) -> Self::IterMut<'_> {
842        self.0.iter_mut()
843    }
844}
845
846/// A key-value entry wrapper around `Option<(K, V)>` representing a singleton or empty map.
847#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
848#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
849pub struct OptionMap<K, V>(pub Option<(K, V)>);
850impl<K, V> Default for OptionMap<K, V> {
851    fn default() -> Self {
852        Self(None)
853    }
854}
855impl<K, V> IntoIterator for OptionMap<K, V> {
856    type Item = (K, V);
857    type IntoIter = core::option::IntoIter<(K, V)>;
858
859    fn into_iter(self) -> Self::IntoIter {
860        self.0.into_iter()
861    }
862}
863impl<K, V, U> From<U> for OptionMap<K, V>
864where
865    U: Into<Option<(K, V)>>,
866{
867    fn from(kv: U) -> Self {
868        Self(kv.into())
869    }
870}
871impl<K, V> Collection for OptionMap<K, V> {
872    type Item = V;
873}
874impl<K, V> Len for OptionMap<K, V> {
875    fn len(&self) -> usize {
876        self.0.is_some() as usize
877    }
878}
879impl<K, V> CollectionRef for OptionMap<K, V> {
880    type ItemRef<'a>
881        = &'a Self::Item
882    where
883        Self: 'a;
884
885    covariant_item_ref!();
886}
887impl<K, V> SimpleCollectionRef for OptionMap<K, V> {
888    simple_collection_ref!();
889}
890impl<'a, Q, K, V> Get<&'a Q> for OptionMap<K, V>
891where
892    K: Borrow<Q>,
893    Q: Eq + ?Sized,
894{
895    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
896        self.0
897            .as_ref()
898            .filter(|(k, _v)| key == k.borrow())
899            .map(|(_k, v)| v)
900    }
901}
902impl<K, V> CollectionMut for OptionMap<K, V> {
903    type ItemMut<'a>
904        = &'a mut Self::Item
905    where
906        Self: 'a;
907
908    covariant_item_mut!();
909}
910impl<'a, Q, K, V> GetMut<&'a Q> for OptionMap<K, V>
911where
912    K: Borrow<Q>,
913    Q: Eq + ?Sized,
914{
915    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
916        self.0
917            .as_mut()
918            .filter(|(k, _v)| key == k.borrow())
919            .map(|(_k, v)| v)
920    }
921}
922impl<K, V> Keyed for OptionMap<K, V> {
923    type Key = K;
924}
925impl<K, V> KeyedRef for OptionMap<K, V> {
926    type KeyRef<'a>
927        = &'a Self::Key
928    where
929        Self: 'a;
930
931    covariant_key_ref!();
932}
933impl<'a, Q, K, V> GetKeyValue<&'a Q> for OptionMap<K, V>
934where
935    K: Borrow<Q>,
936    Q: Eq + ?Sized,
937{
938    fn get_key_value(&self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemRef<'_>)> {
939        self.0
940            .as_ref()
941            .filter(|(k, _v)| key == k.borrow())
942            .map(|(k, v)| (k, v))
943    }
944}
945impl<'a, Q, K, V> GetKeyValueMut<&'a Q> for OptionMap<K, V>
946where
947    K: Borrow<Q>,
948    Q: Eq + ?Sized,
949{
950    fn get_key_value_mut(&mut self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemMut<'_>)> {
951        self.0
952            .as_mut()
953            .filter(|(k, _v)| key == k.borrow())
954            .map(|(k, v)| (&*k, v))
955    }
956}
957impl<K, V> Iter for OptionMap<K, V> {
958    type Iter<'a>
959        = core::option::IntoIter<&'a V>
960    where
961        Self: 'a;
962
963    fn iter(&self) -> Self::Iter<'_> {
964        self.0.as_ref().map(|(_k, v)| v).into_iter()
965    }
966}
967impl<K, V> SimpleKeyedRef for OptionMap<K, V> {
968    simple_keyed_ref!();
969}
970impl<K, V> MapIter for OptionMap<K, V> {
971    type Iter<'a>
972        = core::option::IntoIter<(&'a K, &'a V)>
973    where
974        Self: 'a;
975
976    fn iter(&self) -> Self::Iter<'_> {
977        self.0.as_ref().map(|(k, v)| (k, v)).into_iter()
978    }
979}
980impl<K, V> MapIterMut for OptionMap<K, V> {
981    type IterMut<'a>
982        = core::option::IntoIter<(&'a K, &'a mut V)>
983    where
984        Self: 'a;
985
986    fn iter_mut(&mut self) -> Self::IterMut<'_> {
987        self.0.as_mut().map(|(k, v)| (&*k, v)).into_iter()
988    }
989}
990impl<K, OldVal> MapMapValues<OldVal> for OptionMap<K, OldVal> {
991    type MapValue<NewVal> = OptionMap<K, NewVal>;
992
993    fn map_values<NewVal, MapFn>(self, mut map_fn: MapFn) -> Self::MapValue<NewVal>
994    where
995        MapFn: FnMut(OldVal) -> NewVal,
996    {
997        OptionMap(self.0.map(|(key, val)| (key, (map_fn)(val))))
998    }
999}
1000
1001/// An array wrapper representing a fixed-size set (modulo duplicate items).
1002#[repr(transparent)]
1003#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1004// TODO(mingwei): #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] // https://stackoverflow.com/a/76695397/2398020
1005pub struct ArraySet<T, const N: usize>(pub [T; N]);
1006impl<T, const N: usize> IntoIterator for ArraySet<T, N> {
1007    type Item = T;
1008    type IntoIter = core::array::IntoIter<T, N>;
1009
1010    fn into_iter(self) -> Self::IntoIter {
1011        self.0.into_iter()
1012    }
1013}
1014impl<T, const N: usize> From<[T; N]> for ArraySet<T, N> {
1015    fn from(value: [T; N]) -> Self {
1016        Self(value)
1017    }
1018}
1019impl<T, const N: usize> Collection for ArraySet<T, N> {
1020    type Item = T;
1021}
1022impl<T, const N: usize> Len for ArraySet<T, N> {
1023    fn len(&self) -> usize {
1024        N
1025    }
1026}
1027impl<T, const N: usize> CollectionRef for ArraySet<T, N> {
1028    type ItemRef<'a>
1029        = &'a T
1030    where
1031        Self: 'a;
1032
1033    covariant_item_ref!();
1034}
1035impl<T, const N: usize> SimpleCollectionRef for ArraySet<T, N> {
1036    simple_collection_ref!();
1037}
1038impl<'a, Q, T, const N: usize> Get<&'a Q> for ArraySet<T, N>
1039where
1040    T: Borrow<Q>,
1041    Q: Eq + ?Sized,
1042{
1043    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
1044        self.0
1045            .iter()
1046            .position(|item| key == item.borrow())
1047            .map(|i| &self.0[i])
1048    }
1049}
1050impl<T, const N: usize> CollectionMut for ArraySet<T, N> {
1051    type ItemMut<'a>
1052        = &'a mut T
1053    where
1054        Self: 'a;
1055
1056    covariant_item_mut!();
1057}
1058impl<'a, Q, T, const N: usize> GetMut<&'a Q> for ArraySet<T, N>
1059where
1060    T: Borrow<Q>,
1061    Q: Eq + ?Sized,
1062{
1063    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
1064        self.0
1065            .iter()
1066            .position(|item| key == item.borrow())
1067            .map(|i| &mut self.0[i])
1068    }
1069}
1070impl<T, const N: usize> Iter for ArraySet<T, N> {
1071    type Iter<'a>
1072        = core::slice::Iter<'a, T>
1073    where
1074        Self: 'a;
1075
1076    fn iter(&self) -> Self::Iter<'_> {
1077        self.0.iter()
1078    }
1079}
1080
1081/// An array wrapper representing a fixed-size map.
1082#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1083// TODO(mingwei): #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] // https://stackoverflow.com/a/76695397/2398020
1084pub struct ArrayMap<K, V, const N: usize> {
1085    /// Keys, corresponding 1:1 with `vals`.
1086    pub keys: [K; N],
1087    /// Values, corresponding 1:1 with `keys`.
1088    pub vals: [V; N],
1089}
1090impl<K, V, const N: usize> IntoIterator for ArrayMap<K, V, N> {
1091    type Item = (K, V);
1092    type IntoIter = core::iter::Zip<core::array::IntoIter<K, N>, core::array::IntoIter<V, N>>;
1093
1094    fn into_iter(self) -> Self::IntoIter {
1095        self.keys.into_iter().zip(self.vals)
1096    }
1097}
1098impl<K, V, const N: usize> From<[(K, V); N]> for ArrayMap<K, V, N> {
1099    fn from(value: [(K, V); N]) -> Self {
1100        let mut value = value.map(|(k, v)| (Some(k), v));
1101        let keys = value.each_mut().map(|(k, _)| k.take().unwrap());
1102        let vals = value.map(|(_, v)| v);
1103        Self { keys, vals }
1104    }
1105}
1106impl<K, V, const N: usize> Collection for ArrayMap<K, V, N> {
1107    type Item = V;
1108}
1109impl<K, V, const N: usize> Len for ArrayMap<K, V, N> {
1110    fn len(&self) -> usize {
1111        N
1112    }
1113}
1114impl<K, V, const N: usize> CollectionRef for ArrayMap<K, V, N> {
1115    type ItemRef<'a>
1116        = &'a Self::Item
1117    where
1118        Self: 'a;
1119
1120    covariant_item_ref!();
1121}
1122impl<K, V, const N: usize> SimpleCollectionRef for ArrayMap<K, V, N> {
1123    simple_collection_ref!();
1124}
1125impl<'a, Q, K, V, const N: usize> Get<&'a Q> for ArrayMap<K, V, N>
1126where
1127    K: Borrow<Q>,
1128    Q: Eq + ?Sized,
1129{
1130    fn get(&self, key: &'a Q) -> Option<Self::ItemRef<'_>> {
1131        self.keys
1132            .iter()
1133            .position(|k| key == k.borrow())
1134            .map(|i| &self.vals[i])
1135    }
1136}
1137impl<K, V, const N: usize> CollectionMut for ArrayMap<K, V, N> {
1138    type ItemMut<'a>
1139        = &'a mut Self::Item
1140    where
1141        Self: 'a;
1142
1143    covariant_item_mut!();
1144}
1145impl<'a, Q, K, V, const N: usize> GetMut<&'a Q> for ArrayMap<K, V, N>
1146where
1147    K: Borrow<Q>,
1148    Q: Eq + ?Sized,
1149{
1150    fn get_mut(&mut self, key: &'a Q) -> Option<Self::ItemMut<'_>> {
1151        self.keys
1152            .iter()
1153            .position(|item| key == item.borrow())
1154            .map(|i| &mut self.vals[i])
1155    }
1156}
1157impl<K, V, const N: usize> Keyed for ArrayMap<K, V, N> {
1158    type Key = K;
1159}
1160impl<K, V, const N: usize> KeyedRef for ArrayMap<K, V, N> {
1161    type KeyRef<'a>
1162        = &'a Self::Key
1163    where
1164        Self: 'a;
1165
1166    covariant_key_ref!();
1167}
1168impl<'a, Q, K, V, const N: usize> GetKeyValue<&'a Q> for ArrayMap<K, V, N>
1169where
1170    K: Borrow<Q>,
1171    Q: Eq + ?Sized,
1172{
1173    fn get_key_value(&self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemRef<'_>)> {
1174        self.keys
1175            .iter()
1176            .zip(self.vals.iter())
1177            .find(|(k, _v)| key == K::borrow(k))
1178    }
1179}
1180impl<'a, Q, K, V, const N: usize> GetKeyValueMut<&'a Q> for ArrayMap<K, V, N>
1181where
1182    K: Borrow<Q>,
1183    Q: Eq + ?Sized,
1184{
1185    fn get_key_value_mut(&mut self, key: &'a Q) -> Option<(Self::KeyRef<'_>, Self::ItemMut<'_>)> {
1186        self.keys
1187            .iter()
1188            .zip(self.vals.iter_mut())
1189            .find(|(k, _v)| key == K::borrow(k))
1190    }
1191}
1192impl<K, V, const N: usize> Iter for ArrayMap<K, V, N> {
1193    type Iter<'a>
1194        = core::slice::Iter<'a, V>
1195    where
1196        Self: 'a;
1197
1198    fn iter(&self) -> Self::Iter<'_> {
1199        self.vals.iter()
1200    }
1201}
1202impl<K, V, const N: usize> SimpleKeyedRef for ArrayMap<K, V, N> {
1203    simple_keyed_ref!();
1204}
1205impl<K, V, const N: usize> MapIter for ArrayMap<K, V, N> {
1206    type Iter<'a>
1207        = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::Iter<'a, V>>
1208    where
1209        Self: 'a;
1210
1211    fn iter(&self) -> Self::Iter<'_> {
1212        self.keys.iter().zip(self.vals.iter())
1213    }
1214}
1215impl<K, V, const N: usize> MapIterMut for ArrayMap<K, V, N> {
1216    type IterMut<'a>
1217        = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::IterMut<'a, V>>
1218    where
1219        Self: 'a;
1220
1221    fn iter_mut(&mut self) -> Self::IterMut<'_> {
1222        self.keys.iter().zip(self.vals.iter_mut())
1223    }
1224}
1225impl<K, OldVal, const N: usize> MapMapValues<OldVal> for ArrayMap<K, OldVal, N> {
1226    type MapValue<NewVal> = ArrayMap<K, NewVal, N>;
1227
1228    fn map_values<NewVal, MapFn>(self, map_fn: MapFn) -> Self::MapValue<NewVal>
1229    where
1230        MapFn: FnMut(OldVal) -> NewVal,
1231    {
1232        let Self { keys, vals } = self;
1233        let vals = vals.map(map_fn);
1234        ArrayMap { keys, vals }
1235    }
1236}
1237
1238// /// A boolean-masked fixed-size array wrapper which implements `Collection`.
1239// #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1240// pub struct MaskedArray<T, const N: usize> {
1241//     /// The boolean mask.
1242//     pub mask: [bool; N],
1243//     /// The collection items.
1244//     pub vals: [T; N],
1245// }
1246// impl<T, const N: usize> IntoIterator for MaskedArray<T, N> {
1247//     type Item = T;
1248//     type IntoIter = impl Iterator<Item = Self::Item>;
1249
1250//     fn into_iter(self) -> Self::IntoIter {
1251//         self.mask
1252//             .into_iter()
1253//             .zip(self.vals)
1254//             .filter(|(mask, _)| *mask)
1255//             .map(|(_, val)| val)
1256//     }
1257// }
lattices/collections.rs

lattices/
collections.rs
