| 1 |
use alloc::vec::Vec; |
| 2 |
use std::fmt; |
| 3 |
use std::iter::FusedIterator; |
| 4 |
|
| 5 |
use super::lazy_buffer::LazyBuffer; |
| 6 |
|
| 7 |
/// An iterator to iterate through all the `n`-length combinations in an iterator, with replacement. |
| 8 |
/// |
| 9 |
/// See [`.combinations_with_replacement()`](crate::Itertools::combinations_with_replacement) |
| 10 |
/// for more information. |
| 11 |
#[derive(Clone)] |
| 12 |
pub struct CombinationsWithReplacement<I> |
| 13 |
where |
| 14 |
I: Iterator, |
| 15 |
I::Item: Clone, |
| 16 |
{ |
| 17 |
indices: Vec<usize>, |
| 18 |
pool: LazyBuffer<I>, |
| 19 |
first: bool, |
| 20 |
} |
| 21 |
|
| 22 |
impl<I> fmt::Debug for CombinationsWithReplacement<I> |
| 23 |
where |
| 24 |
I: Iterator + fmt::Debug, |
| 25 |
I::Item: fmt::Debug + Clone, |
| 26 |
{ |
| 27 |
debug_fmt_fields!(Combinations, indices, pool, first); |
| 28 |
} |
| 29 |
|
| 30 |
impl<I> CombinationsWithReplacement<I> |
| 31 |
where |
| 32 |
I: Iterator, |
| 33 |
I::Item: Clone, |
| 34 |
{ |
| 35 |
/// Map the current mask over the pool to get an output combination |
| 36 |
fn current(&self) -> Vec<I::Item> { |
| 37 |
self.indices.iter().map(|i| self.pool[*i].clone()).collect() |
| 38 |
} |
| 39 |
} |
| 40 |
|
| 41 |
/// Create a new `CombinationsWithReplacement` from a clonable iterator. |
| 42 |
pub fn combinations_with_replacement<I>(iter: I, k: usize) -> CombinationsWithReplacement<I> |
| 43 |
where |
| 44 |
I: Iterator, |
| 45 |
I::Item: Clone, |
| 46 |
{ |
| 47 |
let indices: Vec<usize> = alloc::vec![0; k]; |
| 48 |
let pool: LazyBuffer<I> = LazyBuffer::new(iter); |
| 49 |
|
| 50 |
CombinationsWithReplacement { |
| 51 |
indices, |
| 52 |
pool, |
| 53 |
first: true, |
| 54 |
} |
| 55 |
} |
| 56 |
|
| 57 |
impl<I> Iterator for CombinationsWithReplacement<I> |
| 58 |
where |
| 59 |
I: Iterator, |
| 60 |
I::Item: Clone, |
| 61 |
{ |
| 62 |
type Item = Vec<I::Item>; |
| 63 |
fn next(&mut self) -> Option<Self::Item> { |
| 64 |
// If this is the first iteration, return early |
| 65 |
if self.first { |
| 66 |
// In empty edge cases, stop iterating immediately |
| 67 |
return if !(self.indices.is_empty() || self.pool.get_next()) { |
| 68 |
None |
| 69 |
// Otherwise, yield the initial state |
| 70 |
} else { |
| 71 |
self.first = false; |
| 72 |
Some(self.current()) |
| 73 |
}; |
| 74 |
} |
| 75 |
|
| 76 |
// Check if we need to consume more from the iterator |
| 77 |
// This will run while we increment our first index digit |
| 78 |
self.pool.get_next(); |
| 79 |
|
| 80 |
// Work out where we need to update our indices |
| 81 |
let mut increment: Option<(usize, usize)> = None; |
| 82 |
for (i, indices_int) in self.indices.iter().enumerate().rev() { |
| 83 |
if *indices_int < self.pool.len()-1 { |
| 84 |
increment = Some((i, indices_int + 1)); |
| 85 |
break; |
| 86 |
} |
| 87 |
} |
| 88 |
|
| 89 |
match increment { |
| 90 |
// If we can update the indices further |
| 91 |
Some((increment_from, increment_value)) => { |
| 92 |
// We need to update the rightmost non-max value |
| 93 |
// and all those to the right |
| 94 |
for indices_index in increment_from..self.indices.len() { |
| 95 |
self.indices[indices_index] = increment_value; |
| 96 |
} |
| 97 |
Some(self.current()) |
| 98 |
} |
| 99 |
// Otherwise, we're done |
| 100 |
None => None, |
| 101 |
} |
| 102 |
} |
| 103 |
} |
| 104 |
|
| 105 |
impl<I> FusedIterator for CombinationsWithReplacement<I> |
| 106 |
where |
| 107 |
I: Iterator, |
| 108 |
I::Item: Clone, |
| 109 |
{} |