]>
Commit | Line | Data |
---|---|---|
532ac7d7 XL |
1 | use std::fmt; |
2 | ||
3dfed10e XL |
3 | use super::lazy_buffer::LazyBuffer; |
4 | ||
5 | /// An iterator to iterate through all the `k`-length combinations in an iterator. | |
532ac7d7 XL |
6 | /// |
7 | /// See [`.combinations()`](../trait.Itertools.html#method.combinations) for more information. | |
8 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
9 | pub struct Combinations<I: Iterator> { | |
3dfed10e | 10 | k: usize, |
532ac7d7 XL |
11 | indices: Vec<usize>, |
12 | pool: LazyBuffer<I>, | |
13 | first: bool, | |
14 | } | |
15 | ||
16 | impl<I> fmt::Debug for Combinations<I> | |
17 | where I: Iterator + fmt::Debug, | |
18 | I::Item: fmt::Debug, | |
19 | { | |
3dfed10e | 20 | debug_fmt_fields!(Combinations, k, indices, pool, first); |
532ac7d7 XL |
21 | } |
22 | ||
23 | /// Create a new `Combinations` from a clonable iterator. | |
3dfed10e | 24 | pub fn combinations<I>(iter: I, k: usize) -> Combinations<I> |
532ac7d7 XL |
25 | where I: Iterator |
26 | { | |
3dfed10e XL |
27 | let mut indices: Vec<usize> = Vec::with_capacity(k); |
28 | for i in 0..k { | |
532ac7d7 XL |
29 | indices.push(i); |
30 | } | |
31 | let mut pool: LazyBuffer<I> = LazyBuffer::new(iter); | |
32 | ||
3dfed10e | 33 | for _ in 0..k { |
532ac7d7 XL |
34 | if !pool.get_next() { |
35 | break; | |
36 | } | |
37 | } | |
38 | ||
39 | Combinations { | |
3dfed10e | 40 | k: k, |
532ac7d7 XL |
41 | indices: indices, |
42 | pool: pool, | |
43 | first: true, | |
44 | } | |
45 | } | |
46 | ||
47 | impl<I> Iterator for Combinations<I> | |
48 | where I: Iterator, | |
49 | I::Item: Clone | |
50 | { | |
51 | type Item = Vec<I::Item>; | |
52 | fn next(&mut self) -> Option<Self::Item> { | |
53 | let mut pool_len = self.pool.len(); | |
54 | if self.pool.is_done() { | |
3dfed10e | 55 | if pool_len == 0 || self.k > pool_len { |
532ac7d7 XL |
56 | return None; |
57 | } | |
58 | } | |
59 | ||
60 | if self.first { | |
61 | self.first = false; | |
3dfed10e | 62 | } else if self.k == 0 { |
532ac7d7 XL |
63 | return None; |
64 | } else { | |
65 | // Scan from the end, looking for an index to increment | |
3dfed10e | 66 | let mut i: usize = self.k - 1; |
532ac7d7 XL |
67 | |
68 | // Check if we need to consume more from the iterator | |
69 | if self.indices[i] == pool_len - 1 && !self.pool.is_done() { | |
70 | if self.pool.get_next() { | |
71 | pool_len += 1; | |
72 | } | |
73 | } | |
74 | ||
3dfed10e | 75 | while self.indices[i] == i + pool_len - self.k { |
532ac7d7 XL |
76 | if i > 0 { |
77 | i -= 1; | |
78 | } else { | |
79 | // Reached the last combination | |
80 | return None; | |
81 | } | |
82 | } | |
83 | ||
84 | // Increment index, and reset the ones to its right | |
85 | self.indices[i] += 1; | |
86 | let mut j = i + 1; | |
3dfed10e | 87 | while j < self.k { |
532ac7d7 XL |
88 | self.indices[j] = self.indices[j - 1] + 1; |
89 | j += 1; | |
90 | } | |
91 | } | |
92 | ||
93 | // Create result vector based on the indices | |
3dfed10e | 94 | let mut result = Vec::with_capacity(self.k); |
532ac7d7 XL |
95 | for i in self.indices.iter() { |
96 | result.push(self.pool[*i].clone()); | |
97 | } | |
98 | Some(result) | |
99 | } | |
100 | } |