exhaust/impls/
alloc_impls.rs

1use core::iter::FusedIterator;
2use core::pin::Pin;
3use core::{fmt, iter};
4
5use alloc::borrow::{Cow, ToOwned};
6use alloc::boxed::Box;
7use alloc::collections::{BTreeMap, BTreeSet};
8use alloc::rc::Rc;
9use alloc::vec::Vec;
10
11use itertools::Itertools as _;
12
13use crate::iteration::peekable_exhaust;
14use crate::patterns::{delegate_factory_and_iter, impl_newtype_generic};
15use crate::Exhaust;
16
17impl_newtype_generic!(T: [], Box<T>, Box::new);
18impl_newtype_generic!(T: [], Rc<T>, Rc::new);
19impl_newtype_generic!(T: [], Pin<Box<T>>, Box::pin);
20impl_newtype_generic!(T: [], Pin<Rc<T>>, Rc::pin);
21
22/// Note that this implementation necessarily ignores the borrowed versus owned distinction;
23/// every value returned will be a [`Cow::Owned`], not a [`Cow::Borrowed`].
24/// This agrees with the [`PartialEq`] implementation for [`Cow`], which considers
25/// owned and borrowed to be equal.
26impl<T: ?Sized + ToOwned<Owned = O>, O: Exhaust> Exhaust for Cow<'_, T> {
27    delegate_factory_and_iter!(O);
28
29    fn from_factory(factory: Self::Factory) -> Self {
30        Cow::Owned(O::from_factory(factory))
31    }
32}
33
34// Note: This impl is essentially identical to the one for `HashSet`.
35impl<T: Exhaust + Ord> Exhaust for BTreeSet<T> {
36    type Iter = ExhaustSet<T>;
37    type Factory = Vec<T::Factory>;
38    fn exhaust_factories() -> Self::Iter {
39        ExhaustSet::default()
40    }
41    fn from_factory(factory: Self::Factory) -> Self {
42        factory.into_iter().map(T::from_factory).collect()
43    }
44}
45
46// TODO: Instead of delegating to itertools, we should implement our own powerset
47// iterator, to provide the preferred ordering of elements.
48pub struct ExhaustSet<T: Exhaust>(itertools::Powerset<<T as Exhaust>::Iter>);
49
50impl<T: Exhaust> Default for ExhaustSet<T> {
51    fn default() -> Self {
52        ExhaustSet(itertools::Itertools::powerset(T::exhaust_factories()))
53    }
54}
55
56impl<T: Exhaust> Clone for ExhaustSet<T> {
57    fn clone(&self) -> Self {
58        Self(self.0.clone())
59    }
60}
61
62impl<T: Exhaust> Iterator for ExhaustSet<T> {
63    type Item = Vec<T::Factory>;
64    fn next(&mut self) -> Option<Self::Item> {
65        self.0.next()
66    }
67}
68impl<T: Exhaust> FusedIterator for ExhaustSet<T> {}
69
70impl<T: Exhaust> fmt::Debug for ExhaustSet<T>
71where
72    T::Factory: fmt::Debug,
73    T::Iter: fmt::Debug,
74{
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        f.debug_tuple("ExhaustSet").field(&self.0).finish()
77    }
78}
79
80pub(crate) type MapFactory<K, V> = Vec<(<K as Exhaust>::Factory, <V as Exhaust>::Factory)>;
81
82impl<K: Exhaust + Ord, V: Exhaust> Exhaust for BTreeMap<K, V> {
83    type Iter = ExhaustMap<<BTreeSet<K> as Exhaust>::Iter, V>;
84    fn exhaust_factories() -> Self::Iter {
85        ExhaustMap::new(peekable_exhaust::<BTreeSet<K>>())
86    }
87
88    type Factory = MapFactory<K, V>;
89
90    fn from_factory(factory: Self::Factory) -> Self {
91        factory
92            .into_iter()
93            .map(|(k, v)| (K::from_factory(k), V::from_factory(v)))
94            .collect()
95    }
96}
97
98/// Iterator which exhausts map types.
99///
100/// * `KI` is an iterator of key factory *sets* (as `Vec`s) that the map should contain.
101/// * `V` is the type of the map’s values.
102pub struct ExhaustMap<KI, V>
103where
104    KI: Iterator,
105    V: Exhaust,
106{
107    keys: iter::Peekable<KI>,
108    vals: iter::Peekable<itertools::MultiProduct<<V as Exhaust>::Iter>>,
109}
110
111impl<KF, KI, V> ExhaustMap<KI, V>
112where
113    KI: Iterator<Item = Vec<KF>>,
114    V: Exhaust,
115{
116    pub fn new(mut keys: iter::Peekable<KI>) -> Self {
117        let key_count = keys.peek().map_or(0, Vec::len);
118        ExhaustMap {
119            keys,
120            vals: itertools::repeat_n(V::exhaust_factories(), key_count)
121                .multi_cartesian_product()
122                .peekable(),
123        }
124    }
125}
126
127impl<KF, KI, V> Iterator for ExhaustMap<KI, V>
128where
129    KI: Iterator<Item = Vec<KF>>,
130    KF: Clone,
131    V: Exhaust,
132{
133    type Item = Vec<(KF, V::Factory)>;
134    fn next(&mut self) -> Option<Self::Item> {
135        let keys: Vec<KF> = self.keys.peek()?.clone();
136        let vals: Vec<V::Factory> = self.vals.next()?;
137
138        if self.vals.peek().is_none() {
139            self.keys.next();
140            let key_count = self.keys.peek().map_or(0, Vec::len);
141            self.vals = itertools::repeat_n(V::exhaust_factories(), key_count)
142                .multi_cartesian_product()
143                .peekable();
144        }
145
146        Some(keys.into_iter().zip_eq(vals).collect())
147    }
148}
149impl<KF, KI, V> FusedIterator for ExhaustMap<KI, V>
150where
151    KI: Iterator<Item = Vec<KF>>,
152    KF: Clone,
153    V: Exhaust,
154{
155}
156
157impl<KI, V> Clone for ExhaustMap<KI, V>
158where
159    KI: Iterator<Item: Clone> + Clone,
160    V: Exhaust,
161{
162    fn clone(&self) -> Self {
163        Self {
164            keys: self.keys.clone(),
165            vals: self.vals.clone(),
166        }
167    }
168}
169
170impl<KI, V> fmt::Debug for ExhaustMap<KI, V>
171where
172    KI: fmt::Debug + Iterator<Item: fmt::Debug>,
173    V: Exhaust<Iter: fmt::Debug, Factory: fmt::Debug>,
174{
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        f.debug_struct("ExhaustMap")
177            .field("keys", &self.keys)
178            .field("vals", &self.vals)
179            .finish()
180    }
181}
exhaust/impls/alloc_impls.rs

exhaust/impls/
alloc_impls.rs
