• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 use std::fmt;
2 use std::usize;
3 use alloc::vec::Vec;
4 
5 use super::combinations::{Combinations, combinations};
6 use super::size_hint;
7 
8 /// An iterator to iterate through the powerset of the elements from an iterator.
9 ///
10 /// See [`.powerset()`](../trait.Itertools.html#method.powerset) for more
11 /// information.
12 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
13 pub struct Powerset<I: Iterator> {
14     combs: Combinations<I>,
15     // Iterator `position` (equal to count of yielded elements).
16     pos: usize,
17 }
18 
19 impl<I> Clone for Powerset<I>
20     where I: Clone + Iterator,
21           I::Item: Clone,
22 {
23     clone_fields!(combs, pos);
24 }
25 
26 impl<I> fmt::Debug for Powerset<I>
27     where I: Iterator + fmt::Debug,
28           I::Item: fmt::Debug,
29 {
30     debug_fmt_fields!(Powerset, combs, pos);
31 }
32 
33 /// Create a new `Powerset` from a clonable iterator.
powerset<I>(src: I) -> Powerset<I> where I: Iterator, I::Item: Clone,34 pub fn powerset<I>(src: I) -> Powerset<I>
35     where I: Iterator,
36           I::Item: Clone,
37 {
38     Powerset {
39         combs: combinations(src, 0),
40         pos: 0,
41     }
42 }
43 
44 impl<I> Iterator for Powerset<I>
45     where
46         I: Iterator,
47         I::Item: Clone,
48 {
49     type Item = Vec<I::Item>;
50 
next(&mut self) -> Option<Self::Item>51     fn next(&mut self) -> Option<Self::Item> {
52         if let Some(elt) = self.combs.next() {
53             self.pos = self.pos.saturating_add(1);
54             Some(elt)
55         } else if self.combs.k() < self.combs.n()
56             || self.combs.k() == 0
57         {
58             self.combs.reset(self.combs.k() + 1);
59             self.combs.next().map(|elt| {
60                 self.pos = self.pos.saturating_add(1);
61                 elt
62             })
63         } else {
64             None
65         }
66     }
67 
size_hint(&self) -> (usize, Option<usize>)68     fn size_hint(&self) -> (usize, Option<usize>) {
69         // Total bounds for source iterator.
70         let src_total = size_hint::add_scalar(self.combs.src().size_hint(), self.combs.n());
71 
72         // Total bounds for self ( length(powerset(set) == 2 ^ length(set) )
73         let self_total = size_hint::pow_scalar_base(2, src_total);
74 
75         if self.pos < usize::MAX {
76             // Subtract count of elements already yielded from total.
77             size_hint::sub_scalar(self_total, self.pos)
78         } else {
79             // Fallback: self.pos is saturated and no longer reliable.
80             (0, self_total.1)
81         }
82     }
83 }
84