Repository: rust-itertools/itertools
Pull request #760 (2023-09-23 10:34:05)

Minimize features
Somehow, I looked at `try_collect` and ticked seeing that it needs `use_alloc`. It sure does in most common cases but we can collect to `arrayvec` for example.
Because of that, I looked at each adaptor/method to find another unrequired features and found only the ones based on `extrema_set` which only needs to allocate to vectors.


Patch:
diff --git a/benches/powerset.rs b/benches/powerset.rs
index f5862a4..018333d 100644
--- a/benches/powerset.rs
+++ b/benches/powerset.rs
@@ -20,6 +20,17 @@ fn powerset_n(c: &mut Criterion, n: usize) {
     });
 }
 
+fn powerset_n_fold(c: &mut Criterion, n: usize) {
+    let id = format!("powerset {} fold", n);
+    c.bench_function(id.as_str(), move |b| {
+        b.iter(|| {
+            for _ in 0..calc_iters(n) {
+                (0..n).powerset().fold(0, |s, elt| s + black_box(elt).len());
+            }
+        })
+    });
+}
+
 fn powerset_0(c: &mut Criterion) {
     powerset_n(c, 0);
 }
@@ -44,6 +55,30 @@ fn powerset_12(c: &mut Criterion) {
     powerset_n(c, 12);
 }
 
+fn powerset_0_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 0);
+}
+
+fn powerset_1_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 1);
+}
+
+fn powerset_2_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 2);
+}
+
+fn powerset_4_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 4);
+}
+
+fn powerset_8_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 8);
+}
+
+fn powerset_12_fold(c: &mut Criterion) {
+    powerset_n_fold(c, 12);
+}
+
 criterion_group!(
     benches,
     powerset_0,
@@ -52,5 +87,11 @@ criterion_group!(
     powerset_4,
     powerset_8,
     powerset_12,
+    powerset_0_fold,
+    powerset_1_fold,
+    powerset_2_fold,
+    powerset_4_fold,
+    powerset_8_fold,
+    powerset_12_fold,
 );
 criterion_main!(benches);
diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs
index 4bc50ea..90cf46e 100644
--- a/src/adaptors/mod.rs
+++ b/src/adaptors/mod.rs
@@ -14,7 +14,7 @@ pub use self::map::{map_into, map_ok, MapInto, MapOk};
 #[cfg(feature = "use_alloc")]
 pub use self::multi_product::*;
 
-use crate::size_hint;
+use crate::size_hint::{self, SizeHint};
 use std::fmt;
 use std::iter::{FromIterator, Fuse, FusedIterator};
 use std::marker::PhantomData;
@@ -626,6 +626,14 @@ where
     fn next(&mut self) -> Option<Self::Item> {
         self.iter.next()
     }
+
+    fn size_hint(&self) -> SizeHint {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
 }
 
 impl<I, T> FusedIterator for TupleCombinations<I, T>
@@ -652,6 +660,14 @@ impl<I: Iterator> Iterator for Tuple1Combination<I> {
     fn next(&mut self) -> Option<Self::Item> {
         self.iter.next().map(|x| (x,))
     }
+
+    fn size_hint(&self) -> SizeHint {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
 }
 
 impl<I: Iterator> HasCombination<I> for (I::Item,) {
@@ -701,6 +717,20 @@ macro_rules! impl_tuple_combination {
                     })
                 }
             }
+
+            fn size_hint(&self) -> SizeHint {
+                const K: usize = 1 + count_ident!($($X,)*);
+                let (mut n_min, mut n_max) = self.iter.size_hint();
+                n_min = checked_binomial(n_min, K).unwrap_or(usize::MAX);
+                n_max = n_max.and_then(|n| checked_binomial(n, K));
+                size_hint::add(self.c.size_hint(), (n_min, n_max))
+            }
+
+            fn count(self) -> usize {
+                const K: usize = 1 + count_ident!($($X,)*);
+                let n = self.iter.count();
+                checked_binomial(n, K).unwrap() + self.c.count()
+            }
         }
 
         impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*)
@@ -736,6 +766,42 @@ impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i)
 impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j);
 impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k);
 
+// https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages
+pub(crate) fn checked_binomial(mut n: usize, mut k: usize) -> Option<usize> {
+    if n < k {
+        return Some(0);
+    }
+    // `factorial(n) / factorial(n - k) / factorial(k)` but trying to avoid it overflows:
+    k = (n - k).min(k); // symmetry
+    let mut c = 1;
+    for i in 1..=k {
+        c = (c / i)
+            .checked_mul(n)?
+            .checked_add((c % i).checked_mul(n)? / i)?;
+        n -= 1;
+    }
+    Some(c)
+}
+
+#[test]
+fn test_checked_binomial() {
+    // With the first row: [1, 0, 0, ...] and the first column full of 1s, we check
+    // row by row the recurrence relation of binomials (which is an equivalent definition).
+    // For n >= 1 and k >= 1 we have:
+    //   binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k)
+    const LIMIT: usize = 500;
+    let mut row = vec![Some(0); LIMIT + 1];
+    row[0] = Some(1);
+    for n in 0..=LIMIT {
+        for k in 0..=LIMIT {
+            assert_eq!(row[k], checked_binomial(n, k));
+        }
+        row = std::iter::once(Some(1))
+            .chain((1..=LIMIT).map(|k| row[k - 1]?.checked_add(row[k]?)))
+            .collect();
+    }
+}
+
 /// An iterator adapter to filter values within a nested `Result::Ok`.
 ///
 /// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information.
diff --git a/src/combinations.rs b/src/combinations.rs
index 332bcb3..1c834a7 100644
--- a/src/combinations.rs
+++ b/src/combinations.rs
@@ -4,6 +4,8 @@ use std::iter::FusedIterator;
 use super::lazy_buffer::LazyBuffer;
 use alloc::vec::Vec;
 
+use crate::adaptors::checked_binomial;
+
 /// An iterator to iterate through all the `k`-length combinations in an iterator.
 ///
 /// See [`.combinations()`](crate::Itertools::combinations) for more information.
@@ -160,42 +162,6 @@ where
 {
 }
 
-// https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages
-pub(crate) fn checked_binomial(mut n: usize, mut k: usize) -> Option<usize> {
-    if n < k {
-        return Some(0);
-    }
-    // `factorial(n) / factorial(n - k) / factorial(k)` but trying to avoid it overflows:
-    k = (n - k).min(k); // symmetry
-    let mut c = 1;
-    for i in 1..=k {
-        c = (c / i)
-            .checked_mul(n)?
-            .checked_add((c % i).checked_mul(n)? / i)?;
-        n -= 1;
-    }
-    Some(c)
-}
-
-#[test]
-fn test_checked_binomial() {
-    // With the first row: [1, 0, 0, ...] and the first column full of 1s, we check
-    // row by row the recurrence relation of binomials (which is an equivalent definition).
-    // For n >= 1 and k >= 1 we have:
-    //   binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k)
-    const LIMIT: usize = 500;
-    let mut row = vec![Some(0); LIMIT + 1];
-    row[0] = Some(1);
-    for n in 0..=LIMIT {
-        for k in 0..=LIMIT {
-            assert_eq!(row[k], checked_binomial(n, k));
-        }
-        row = std::iter::once(Some(1))
-            .chain((1..=LIMIT).map(|k| row[k - 1]?.checked_add(row[k]?)))
-            .collect();
-    }
-}
-
 /// For a given size `n`, return the count of remaining combinations or None if it would overflow.
 fn remaining_for(n: usize, first: bool, indices: &[usize]) -> Option<usize> {
     let k = indices.len();
diff --git a/src/combinations_with_replacement.rs b/src/combinations_with_replacement.rs
index e4f1cda..f1a0bc0 100644
--- a/src/combinations_with_replacement.rs
+++ b/src/combinations_with_replacement.rs
@@ -3,7 +3,7 @@ use std::fmt;
 use std::iter::FusedIterator;
 
 use super::lazy_buffer::LazyBuffer;
-use crate::combinations::checked_binomial;
+use crate::adaptors::checked_binomial;
 
 /// An iterator to iterate through all the `n`-length combinations in an iterator, with replacement.
 ///
diff --git a/src/extrema_set.rs b/src/extrema_set.rs
index ae12836..d24114c 100644
--- a/src/extrema_set.rs
+++ b/src/extrema_set.rs
@@ -1,3 +1,5 @@
+#![cfg(feature = "use_alloc")]
+use alloc::{vec, vec::Vec};
 use std::cmp::Ordering;
 
 /// Implementation guts for `min_set`, `min_set_by`, and `min_set_by_key`.
diff --git a/src/impl_macros.rs b/src/impl_macros.rs
index 5fd78cb..7c0b0c2 100644
--- a/src/impl_macros.rs
+++ b/src/impl_macros.rs
@@ -27,3 +27,8 @@ macro_rules! clone_fields {
 macro_rules! ignore_ident{
     ($id:ident, $($t:tt)*) => {$($t)*};
 }
+
+macro_rules! count_ident {
+    () => {0};
+    ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)};
+}
diff --git a/src/lib.rs b/src/lib.rs
index 458ffe6..3d5f05c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -70,7 +70,6 @@ use std::hash::Hash;
 use std::iter::{once, IntoIterator};
 #[cfg(feature = "use_alloc")]
 type VecIntoIter<T> = alloc::vec::IntoIter<T>;
-#[cfg(feature = "use_alloc")]
 use std::iter::FromIterator;
 
 #[macro_use]
@@ -178,7 +177,7 @@ mod diff;
 #[cfg(feature = "use_std")]
 mod duplicates_impl;
 mod exactly_one_err;
-#[cfg(feature = "use_std")]
+#[cfg(feature = "use_alloc")]
 mod extrema_set;
 mod flatten_ok;
 mod format;
@@ -2214,7 +2213,6 @@ pub trait Itertools: Iterator {
     ///     Ok(())
     /// }
     /// ```
-    #[cfg(feature = "use_alloc")]
     fn try_collect<T, U, E>(self) -> Result<U, E>
     where
         Self: Sized + Iterator<Item = Result<T, E>>,
@@ -3171,7 +3169,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn min_set(self) -> Vec<Self::Item>
     where
         Self: Sized,
@@ -3204,7 +3202,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn min_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
     where
         Self: Sized,
@@ -3236,7 +3234,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn min_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
     where
         Self: Sized,
@@ -3268,7 +3266,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn max_set(self) -> Vec<Self::Item>
     where
         Self: Sized,
@@ -3301,7 +3299,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn max_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
     where
         Self: Sized,
@@ -3333,7 +3331,7 @@ pub trait Itertools: Iterator {
     ///
     /// The elements can be floats but no particular result is guaranteed
     /// if an element is NaN.
-    #[cfg(feature = "use_std")]
+    #[cfg(feature = "use_alloc")]
     fn max_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
     where
         Self: Sized,
diff --git a/src/powerset.rs b/src/powerset.rs
index 811cfce..9a7131a 100644
--- a/src/powerset.rs
+++ b/src/powerset.rs
@@ -3,7 +3,8 @@ use std::fmt;
 use std::iter::FusedIterator;
 use std::usize;
 
-use super::combinations::{checked_binomial, combinations, Combinations};
+use super::combinations::{combinations, Combinations};
+use crate::adaptors::checked_binomial;
 use crate::size_hint::{self, SizeHint};
 
 /// An iterator to iterate through the powerset of the elements from an iterator.
@@ -74,6 +75,24 @@ where
         let (n, combs_count) = self.combs.n_and_count();
         combs_count + remaining_for(n, k).unwrap()
     }
+
+    fn fold<B, F>(self, mut init: B, mut f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        let mut it = self.combs;
+        if it.k() == 0 {
+            init = it.by_ref().fold(init, &mut f);
+            it.reset(1);
+        }
+        init = it.by_ref().fold(init, &mut f);
+        // n is now known for sure because k >= 1 and all k-combinations have been generated.
+        for k in it.k() + 1..=it.n() {
+            it.reset(k);
+            init = it.by_ref().fold(init, &mut f);
+        }
+        init
+    }
 }
 
 impl<I> FusedIterator for Powerset<I>
diff --git a/src/tuple_impl.rs b/src/tuple_impl.rs
index ba1c69d..c01190e 100644
--- a/src/tuple_impl.rs
+++ b/src/tuple_impl.rs
@@ -105,6 +105,35 @@ where
     fn next(&mut self) -> Option<Self::Item> {
         T::collect_from_iter(&mut self.iter, &mut self.buf)
     }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // The number of elts we've drawn from the underlying iterator, but have
+        // not yet produced as a tuple.
+        let buffered = T::buffer_len(&self.buf);
+        // To that, we must add the size estimates of the underlying iterator.
+        let (mut unbuffered_lo, mut unbuffered_hi) = self.iter.size_hint();
+        // The total low estimate is the sum of the already-buffered elements,
+        // plus the low estimate of remaining unbuffered elements, divided by
+        // the tuple size.
+        let total_lo = add_then_div(unbuffered_lo, buffered, T::num_items()).unwrap_or(usize::MAX);
+        // And likewise for the total high estimate, but using the high estimate
+        // of the remaining unbuffered elements.
+        let total_hi = unbuffered_hi.and_then(|hi| add_then_div(hi, buffered, T::num_items()));
+        (total_lo, total_hi)
+    }
+}
+
+/// `(n + a) / d` avoiding overflow when possible, returns `None` if it overflows.
+fn add_then_div(n: usize, a: usize, d: usize) -> Option<usize> {
+    debug_assert_ne!(d, 0);
+    (n / d).checked_add(a / d)?.checked_add((n % d + a % d) / d)
+}
+
+impl<I, T> ExactSizeIterator for Tuples<I, T>
+where
+    I: ExactSizeIterator<Item = T::Item>,
+    T: HomogeneousTuple,
+{
 }
 
 impl<I, T> Tuples<I, T>
@@ -284,6 +313,11 @@ pub trait TupleCollect: Sized {
     type Item;
     type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
 
+    fn buffer_len(buf: &Self::Buffer) -> usize {
+        let s = buf.as_ref();
+        s.iter().position(Option::is_none).unwrap_or(s.len())
+    }
+
     fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
     where
         I: IntoIterator<Item = Self::Item>;
@@ -297,10 +331,6 @@ pub trait TupleCollect: Sized {
     fn left_shift_push(&mut self, item: Self::Item);
 }
 
-macro_rules! count_ident{
-    () => {0};
-    ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)};
-}
 macro_rules! rev_for_each_ident{
     ($m:ident, ) => {};
     ($m:ident, $i0:ident, $($i:ident,)*) => {


Test patch:
diff --git a/tests/quick.rs b/tests/quick.rs
index 3dc23d7..5729cfa 100644
--- a/tests/quick.rs
+++ b/tests/quick.rs
@@ -901,8 +901,31 @@ quickcheck! {
 }
 
 quickcheck! {
-    fn size_combinations(it: Iter<i16>) -> bool {
-        correct_size_hint(it.tuple_combinations::<(_, _)>())
+    fn size_combinations(a: Iter<i16>) -> bool {
+        let it = a.clone().tuple_combinations::<(_, _)>();
+        correct_size_hint(it.clone()) && it.count() == binomial(a.count(), 2)
+    }
+
+    fn exact_size_combinations_1(a: Vec<u8>) -> bool {
+        let it = a.iter().tuple_combinations::<(_,)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 1)
+    }
+    fn exact_size_combinations_2(a: Vec<u8>) -> bool {
+        let it = a.iter().tuple_combinations::<(_, _)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 2)
+    }
+    fn exact_size_combinations_3(mut a: Vec<u8>) -> bool {
+        a.truncate(15);
+        let it = a.iter().tuple_combinations::<(_, _, _)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 3)
+    }
+}
+
+fn binomial(n: usize, k: usize) -> usize {
+    if k > n {
+        0
+    } else {
+        (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>()
     }
 }
 
@@ -1184,6 +1207,18 @@ quickcheck! {
         assert_eq!(buffer.len(), a.len() % 4);
         exact_size(buffer)
     }
+
+    fn tuples_size_hint_inexact(a: Iter<u8>) -> bool {
+        correct_size_hint(a.clone().tuples::<(_,)>())
+            && correct_size_hint(a.clone().tuples::<(_, _)>())
+            && correct_size_hint(a.tuples::<(_, _, _, _)>())
+    }
+
+    fn tuples_size_hint_exact(a: Iter<u8, Exact>) -> bool {
+        exact_size(a.clone().tuples::<(_,)>())
+            && exact_size(a.clone().tuples::<(_, _)>())
+            && exact_size(a.tuples::<(_, _, _, _)>())
+    }
 }
 
 // with_position
diff --git a/tests/specializations.rs b/tests/specializations.rs
index efc8ba6..7c21da6 100644
--- a/tests/specializations.rs
+++ b/tests/specializations.rs
@@ -72,9 +72,21 @@ where
 }
 
 quickcheck! {
+    fn tuple_combinations(v: Vec<u8>) -> () {
+        let mut v = v;
+        v.truncate(10);
+        test_specializations(&v.iter().tuple_combinations::<(_, _, _)>());
+    }
+
     fn intersperse(v: Vec<u8>) -> () {
         test_specializations(&v.into_iter().intersperse(0));
     }
+
+    fn powerset(a: Vec<u8>) -> () {
+        let mut a = a;
+        a.truncate(6);
+        test_specializations(&a.iter().powerset())
+    }
 }
 
 quickcheck! {