test_case_core/test_matrix/
matrix_product.rs

Help
1//! Copied with minor modifications from itertools v0.11.0
2//! under MIT License
3//!
4//! Modifications called out in "(MOD)" comments, below
5//!
6//! Source file and commit hash:
7//! https://github.com/rust-itertools/itertools/blob/v0.11.0/src/adaptors/multi_product.rs
8//! ed6fbda086a913a787450a642acfd4d36dc07c3b
9
10#[derive(Clone)]
11/// An iterator adaptor that iterates over the cartesian product of
12/// multiple iterators of type `I`.
13///
14/// An iterator element type is `Vec<I>`.
15///
16/// See [`.multi_cartesian_product()`](crate::Itertools::multi_cartesian_product)
17/// for more information.
18#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
19pub struct MultiProduct<I>(Vec<MultiProductIter<I>>)
20where
21    I: Iterator + Clone,
22    I::Item: Clone;
23
24// (MOD) Omit `impl Debug for MultiProduct`
25//       Not needed here and relies on a macro from itertools
26
27/// Create a new cartesian product iterator over an arbitrary number
28/// of iterators of the same type.
29///
30/// Iterator element is of type `Vec<H::Item::Item>`.
31pub fn multi_cartesian_product<H>(iters: H) -> MultiProduct<<H::Item as IntoIterator>::IntoIter>
32where
33    H: Iterator,
34    H::Item: IntoIterator,
35    <H::Item as IntoIterator>::IntoIter: Clone,
36    <H::Item as IntoIterator>::Item: Clone,
37{
38    MultiProduct(
39        iters
40            .map(|i| MultiProductIter::new(i.into_iter()))
41            .collect(),
42    )
43}
44
45#[derive(Clone, Debug)]
46/// Holds the state of a single iterator within a `MultiProduct`.
47struct MultiProductIter<I>
48where
49    I: Iterator + Clone,
50    I::Item: Clone,
51{
52    cur: Option<I::Item>,
53    iter: I,
54    iter_orig: I,
55}
56
57/// Holds the current state during an iteration of a `MultiProduct`.
58#[derive(Debug)]
59enum MultiProductIterState {
60    StartOfIter,
61    MidIter { on_first_iter: bool },
62}
63
64impl<I> MultiProduct<I>
65where
66    I: Iterator + Clone,
67    I::Item: Clone,
68{
69    /// Iterates the rightmost iterator, then recursively iterates iterators
70    /// to the left if necessary.
71    ///
72    /// Returns true if the iteration succeeded, else false.
73    fn iterate_last(
74        multi_iters: &mut [MultiProductIter<I>],
75        mut state: MultiProductIterState,
76    ) -> bool {
77        use self::MultiProductIterState::*;
78
79        if let Some((last, rest)) = multi_iters.split_last_mut() {
80            let on_first_iter = match state {
81                StartOfIter => {
82                    let on_first_iter = !last.in_progress();
83                    state = MidIter { on_first_iter };
84                    on_first_iter
85                }
86                MidIter { on_first_iter } => on_first_iter,
87            };
88
89            if !on_first_iter {
90                last.iterate();
91            }
92
93            if last.in_progress() {
94                true
95            } else if MultiProduct::iterate_last(rest, state) {
96                last.reset();
97                last.iterate();
98                // If iterator is None twice consecutively, then iterator is
99                // empty; whole product is empty.
100                last.in_progress()
101            } else {
102                false
103            }
104        } else {
105            // Reached end of iterator list. On initialisation, return true.
106            // At end of iteration (final iterator finishes), finish.
107            match state {
108                StartOfIter => false,
109                MidIter { on_first_iter } => on_first_iter,
110            }
111        }
112    }
113
114    /// Returns the unwrapped value of the next iteration.
115    fn curr_iterator(&self) -> Vec<I::Item> {
116        self.0
117            .iter()
118            .map(|multi_iter| multi_iter.cur.clone().unwrap())
119            .collect()
120    }
121
122    /// Returns true if iteration has started and has not yet finished; false
123    /// otherwise.
124    fn in_progress(&self) -> bool {
125        if let Some(last) = self.0.last() {
126            last.in_progress()
127        } else {
128            false
129        }
130    }
131}
132
133impl<I> MultiProductIter<I>
134where
135    I: Iterator + Clone,
136    I::Item: Clone,
137{
138    fn new(iter: I) -> Self {
139        MultiProductIter {
140            cur: None,
141            iter: iter.clone(),
142            iter_orig: iter,
143        }
144    }
145
146    /// Iterate the managed iterator.
147    fn iterate(&mut self) {
148        self.cur = self.iter.next();
149    }
150
151    /// Reset the managed iterator.
152    fn reset(&mut self) {
153        self.iter = self.iter_orig.clone();
154    }
155
156    /// Returns true if the current iterator has been started and has not yet
157    /// finished; false otherwise.
158    fn in_progress(&self) -> bool {
159        self.cur.is_some()
160    }
161}
162
163impl<I> Iterator for MultiProduct<I>
164where
165    I: Iterator + Clone,
166    I::Item: Clone,
167{
168    type Item = Vec<I::Item>;
169
170    fn next(&mut self) -> Option<Self::Item> {
171        if MultiProduct::iterate_last(&mut self.0, MultiProductIterState::StartOfIter) {
172            Some(self.curr_iterator())
173        } else {
174            None
175        }
176    }
177
178    fn count(self) -> usize {
179        if self.0.is_empty() {
180            return 0;
181        }
182
183        if !self.in_progress() {
184            return self
185                .0
186                .into_iter()
187                .fold(1, |acc, multi_iter| acc * multi_iter.iter.count());
188        }
189
190        self.0.into_iter().fold(
191            0,
192            |acc,
193             MultiProductIter {
194                 iter,
195                 iter_orig,
196                 cur: _,
197             }| {
198                let total_count = iter_orig.count();
199                let cur_count = iter.count();
200                acc * total_count + cur_count
201            },
202        )
203    }
204
205    fn size_hint(&self) -> (usize, Option<usize>) {
206        // Not ExactSizeIterator because size may be larger than usize
207        if self.0.is_empty() {
208            return (0, Some(0));
209        }
210
211        if !self.in_progress() {
212            return self.0.iter().fold((1, Some(1)), |acc, multi_iter| {
213                size_hint::mul(acc, multi_iter.iter.size_hint())
214            });
215        }
216
217        // (MOD) Clippy warning about unnecessary `ref` destructuring of `MultiProductIter`
218        //       Removed redundant `&` and `ref`
219        self.0.iter().fold(
220            (0, Some(0)),
221            |acc,
222             MultiProductIter {
223                 iter,
224                 iter_orig,
225                 cur: _,
226             }| {
227                let cur_size = iter.size_hint();
228                let total_size = iter_orig.size_hint();
229                size_hint::add(size_hint::mul(acc, total_size), cur_size)
230            },
231        )
232    }
233
234    fn last(self) -> Option<Self::Item> {
235        let iter_count = self.0.len();
236
237        // (MOD) Replaced `itertools::Itertools::while_some()`
238        //       `std::iter::Iterator::filter_map()` does the same
239        //       thing in this case, and doesn't require the `Itertools` trait
240        let lasts: Self::Item = self
241            .0
242            .into_iter()
243            .filter_map(|multi_iter| multi_iter.iter.last())
244            .collect();
245
246        if lasts.len() == iter_count {
247            Some(lasts)
248        } else {
249            None
250        }
251    }
252}
253
254// (MOD) Copied two required functions and type alias
255//       From itertools::size_hint module
256mod size_hint {
257    /// `SizeHint` is the return type of `Iterator::size_hint()`.
258    pub type SizeHint = (usize, Option<usize>);
259
260    /// Add `SizeHint` correctly.
261    #[inline]
262    pub fn add(a: SizeHint, b: SizeHint) -> SizeHint {
263        let min = a.0.saturating_add(b.0);
264        let max = match (a.1, b.1) {
265            (Some(x), Some(y)) => x.checked_add(y),
266            _ => None,
267        };
268
269        (min, max)
270    }
271
272    /// Multiply `SizeHint` correctly
273    #[inline]
274    pub fn mul(a: SizeHint, b: SizeHint) -> SizeHint {
275        let low = a.0.saturating_mul(b.0);
276        let hi = match (a.1, b.1) {
277            (Some(x), Some(y)) => x.checked_mul(y),
278            (Some(0), None) | (None, Some(0)) => Some(0),
279            _ => None,
280        };
281        (low, hi)
282    }
283}
test_case_core/test_matrix/matrix_product.rs

test_case_core/test_matrix/
matrix_product.rs
