lattices/
collections.rs

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

lattices/
collections.rs
