1 #![cfg(feature = "use_alloc")]
9 /// An iterator adaptor that iterates over the cartesian product of
10 /// multiple iterators of type `I`.
12 /// An iterator element type is `Vec<I>`.
14 /// See [`.multi_cartesian_product()`](crate::Itertools::multi_cartesian_product)
15 /// for more information.
16 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
17 pub struct MultiProduct
<I
>(Vec
<MultiProductIter
<I
>>)
18 where I
: Iterator
+ Clone
,
21 /// Create a new cartesian product iterator over an arbitrary number
22 /// of iterators of the same type.
24 /// Iterator element is of type `Vec<H::Item::Item>`.
25 pub fn multi_cartesian_product
<H
>(iters
: H
) -> MultiProduct
<<H
::Item
as IntoIterator
>::IntoIter
>
27 H
::Item
: IntoIterator
,
28 <H
::Item
as IntoIterator
>::IntoIter
: Clone
,
29 <H
::Item
as IntoIterator
>::Item
: Clone
31 MultiProduct(iters
.map(|i
| MultiProductIter
::new(i
.into_iter())).collect())
34 #[derive(Clone, Debug)]
35 /// Holds the state of a single iterator within a MultiProduct.
36 struct MultiProductIter
<I
>
37 where I
: Iterator
+ Clone
,
45 /// Holds the current state during an iteration of a MultiProduct.
47 enum MultiProductIterState
{
49 MidIter { on_first_iter: bool }
,
52 impl<I
> MultiProduct
<I
>
53 where I
: Iterator
+ Clone
,
56 /// Iterates the rightmost iterator, then recursively iterates iterators
57 /// to the left if necessary.
59 /// Returns true if the iteration succeeded, else false.
61 multi_iters
: &mut [MultiProductIter
<I
>],
62 mut state
: MultiProductIterState
64 use self::MultiProductIterState
::*;
66 if let Some((last
, rest
)) = multi_iters
.split_last_mut() {
67 let on_first_iter
= match state
{
69 let on_first_iter
= !last
.in_progress();
70 state
= MidIter { on_first_iter }
;
73 MidIter { on_first_iter }
=> on_first_iter
80 if last
.in_progress() {
82 } else if MultiProduct
::iterate_last(rest
, state
) {
85 // If iterator is None twice consecutively, then iterator is
86 // empty; whole product is empty.
92 // Reached end of iterator list. On initialisation, return true.
93 // At end of iteration (final iterator finishes), finish.
96 MidIter { on_first_iter }
=> on_first_iter
101 /// Returns the unwrapped value of the next iteration.
102 fn curr_iterator(&self) -> Vec
<I
::Item
> {
103 self.0.iter
().map(|multi_iter
| {
104 multi_iter
.cur
.clone().unwrap()
108 /// Returns true if iteration has started and has not yet finished; false
110 fn in_progress(&self) -> bool
{
111 if let Some(last
) = self.0.last() {
119 impl<I
> MultiProductIter
<I
>
120 where I
: Iterator
+ Clone
,
123 fn new(iter
: I
) -> Self {
131 /// Iterate the managed iterator.
132 fn iterate(&mut self) {
133 self.cur
= self.iter
.next();
136 /// Reset the managed iterator.
137 fn reset(&mut self) {
138 self.iter
= self.iter_orig
.clone();
141 /// Returns true if the current iterator has been started and has not yet
142 /// finished; false otherwise.
143 fn in_progress(&self) -> bool
{
148 impl<I
> Iterator
for MultiProduct
<I
>
149 where I
: Iterator
+ Clone
,
152 type Item
= Vec
<I
::Item
>;
154 fn next(&mut self) -> Option
<Self::Item
> {
155 if MultiProduct
::iterate_last(
157 MultiProductIterState
::StartOfIter
159 Some(self.curr_iterator())
165 fn count(self) -> usize {
166 if self.0.is_empty
() {
170 if !self.in_progress() {
171 return self.0.into_iter
().fold(1, |acc
, multi_iter
| {
172 acc
* multi_iter
.iter
.count()
176 self.0.into_iter
().fold(
178 |acc
, MultiProductIter { iter, iter_orig, cur: _ }
| {
179 let total_count
= iter_orig
.count();
180 let cur_count
= iter
.count();
181 acc
* total_count
+ cur_count
186 fn size_hint(&self) -> (usize, Option
<usize>) {
187 // Not ExactSizeIterator because size may be larger than usize
188 if self.0.is_empty
() {
192 if !self.in_progress() {
193 return self.0.iter
().fold((1, Some(1)), |acc
, multi_iter
| {
194 size_hint
::mul(acc
, multi_iter
.iter
.size_hint())
200 |acc
, &MultiProductIter { ref iter, ref iter_orig, cur: _ }
| {
201 let cur_size
= iter
.size_hint();
202 let total_size
= iter_orig
.size_hint();
203 size_hint
::add(size_hint
::mul(acc
, total_size
), cur_size
)
208 fn last(self) -> Option
<Self::Item
> {
209 let iter_count
= self.0.len();
211 let lasts
: Self::Item
= self.0.into_iter
()
212 .map(|multi_iter
| multi_iter
.iter
.last())
216 if lasts
.len() == iter_count
{