Repository: rust-itertools/itertools
Pull request #895 (2024-03-07 15:27:33)

Deprecate `tree_fold1` for `tree_reduce`
I think `tree_fold1` should have been deprecated for `tree_reduce` at the same time `fold1` was deprecated for `reduce`.

With this deprecation, we will be able to remove `tree_fold1` and `fold1` at the same time and close that chapter once and for all.

@scottmcm Do you have an objection on this?

**PS:** I wish I had thought of this but no, thanks [reddit](https://www.reddit.com/r/rust/comments/1830wnj/tree_foldl_should_be_tree_reduce/).

Philippe-Cholet: In `GroupingMap`, `fold_first` seems to be named after `fold1`, is it?
If that's the case, should it be deprecated for `reduce` similarly to what I did here with `tree_`?

Patch:
diff --git a/Cargo.toml b/Cargo.toml
index d6dc3fa..7fb6a39 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -57,7 +57,7 @@ name = "combinations_with_replacement"
 harness = false
 
 [[bench]]
-name = "tree_fold1"
+name = "tree_reduce"
 harness = false
 
 [[bench]]
diff --git a/benches/tree_fold1.rs b/benches/tree_reduce.rs
similarity index 86%
rename from benches/tree_fold1.rs
rename to benches/tree_reduce.rs
index 5b76d54..051b148 100644
--- a/benches/tree_fold1.rs
+++ b/benches/tree_reduce.rs
@@ -6,7 +6,7 @@ use itertools::{cloned, Itertools};
 trait IterEx: Iterator {
     // Another efficient implementation against which to compare,
     // but needs `std` so is less desirable.
-    fn tree_fold1_vec<F>(self, mut f: F) -> Option<Self::Item>
+    fn tree_reduce_vec<F>(self, mut f: F) -> Option<Self::Item>
     where
         F: FnMut(Self::Item, Self::Item) -> Self::Item,
         Self: Sized,
@@ -91,14 +91,14 @@ def_benchs! {
 
 def_benchs! {
     10_000,
-    tree_fold1,
-    tree_fold1_stack_10k,
+    tree_reduce,
+    tree_reduce_stack_10k,
 }
 
 def_benchs! {
     10_000,
-    tree_fold1_vec,
-    tree_fold1_vec_10k,
+    tree_reduce_vec,
+    tree_reduce_vec_10k,
 }
 
 def_benchs! {
@@ -109,14 +109,14 @@ def_benchs! {
 
 def_benchs! {
     100,
-    tree_fold1,
-    tree_fold1_stack_100,
+    tree_reduce,
+    tree_reduce_stack_100,
 }
 
 def_benchs! {
     100,
-    tree_fold1_vec,
-    tree_fold1_vec_100,
+    tree_reduce_vec,
+    tree_reduce_vec_100,
 }
 
 def_benchs! {
@@ -127,24 +127,24 @@ def_benchs! {
 
 def_benchs! {
     8,
-    tree_fold1,
-    tree_fold1_stack_08,
+    tree_reduce,
+    tree_reduce_stack_08,
 }
 
 def_benchs! {
     8,
-    tree_fold1_vec,
-    tree_fold1_vec_08,
+    tree_reduce_vec,
+    tree_reduce_vec_08,
 }
 
 criterion_main!(
     fold1_10k,
-    tree_fold1_stack_10k,
-    tree_fold1_vec_10k,
+    tree_reduce_stack_10k,
+    tree_reduce_vec_10k,
     fold1_100,
-    tree_fold1_stack_100,
-    tree_fold1_vec_100,
+    tree_reduce_stack_100,
+    tree_reduce_vec_100,
     fold1_08,
-    tree_fold1_stack_08,
-    tree_fold1_vec_08,
+    tree_reduce_stack_08,
+    tree_reduce_vec_08,
 );
diff --git a/src/k_smallest.rs b/src/k_smallest.rs
index 4de1b25..fe699fb 100644
--- a/src/k_smallest.rs
+++ b/src/k_smallest.rs
@@ -2,7 +2,7 @@ use alloc::vec::Vec;
 use core::cmp::Ordering;
 
 /// Consumes a given iterator, returning the minimum elements in **ascending** order.
-pub(crate) fn k_smallest_general<I, F>(mut iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
+pub(crate) fn k_smallest_general<I, F>(iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
 where
     I: Iterator,
     F: FnMut(&I::Item, &I::Item) -> Ordering,
@@ -44,6 +44,7 @@ where
     if k == 0 {
         return Vec::new();
     }
+    let mut iter = iter.fuse();
     let mut storage: Vec<I::Item> = iter.by_ref().take(k).collect();
 
     let mut is_less_than = move |a: &_, b: &_| comparator(a, b) == Ordering::Less;
@@ -55,19 +56,15 @@ where
         sift_down(&mut storage, &mut is_less_than, i);
     }
 
-    if k == storage.len() {
-        // If we fill the storage, there may still be iterator elements left so feed them into the heap.
-        // Also avoids unexpected behaviour with restartable iterators.
-        iter.for_each(|val| {
-            if is_less_than(&val, &storage[0]) {
-                // Treating this as an push-and-pop saves having to write a sift-up implementation.
-                // https://en.wikipedia.org/wiki/Binary_heap#Insert_then_extract
-                storage[0] = val;
-                // We retain the smallest items we've seen so far, but ordered largest first so we can drop the largest efficiently.
-                sift_down(&mut storage, &mut is_less_than, 0);
-            }
-        });
-    }
+    iter.for_each(|val| {
+        if is_less_than(&val, &storage[0]) {
+            // Treating this as an push-and-pop saves having to write a sift-up implementation.
+            // https://en.wikipedia.org/wiki/Binary_heap#Insert_then_extract
+            storage[0] = val;
+            // We retain the smallest items we've seen so far, but ordered largest first so we can drop the largest efficiently.
+            sift_down(&mut storage, &mut is_less_than, 0);
+        }
+    });
 
     // Ultimately the items need to be in least-first, strict order, but the heap is currently largest-first.
     // To achieve this, repeatedly,
diff --git a/src/lib.rs b/src/lib.rs
index 0506a3d..ec374c4 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2466,7 +2466,7 @@ pub trait Itertools: Iterator {
     /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal
     /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler
     /// code because the compiler is able to optimize it
-    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_fold1` since it
+    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_reduce` since it
     /// reduces the number of operations from `O(n)` to `O(ln(n))`
     ///
     /// Here "non-trivial" means:
@@ -2479,20 +2479,20 @@ pub trait Itertools: Iterator {
     ///
     /// // The same tree as above
     /// let num_strings = (1..8).map(|x| x.to_string());
-    /// assert_eq!(num_strings.tree_fold1(|x, y| format!("f({}, {})", x, y)),
+    /// assert_eq!(num_strings.tree_reduce(|x, y| format!("f({}, {})", x, y)),
     ///     Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
     ///
     /// // Like fold1, an empty iterator produces None
-    /// assert_eq!((0..0).tree_fold1(|x, y| x * y), None);
+    /// assert_eq!((0..0).tree_reduce(|x, y| x * y), None);
     ///
-    /// // tree_fold1 matches fold1 for associative operations...
-    /// assert_eq!((0..10).tree_fold1(|x, y| x + y),
+    /// // tree_reduce matches fold1 for associative operations...
+    /// assert_eq!((0..10).tree_reduce(|x, y| x + y),
     ///     (0..10).fold1(|x, y| x + y));
     /// // ...but not for non-associative ones
-    /// assert_ne!((0..10).tree_fold1(|x, y| x - y),
+    /// assert_ne!((0..10).tree_reduce(|x, y| x - y),
     ///     (0..10).fold1(|x, y| x - y));
     /// ```
-    fn tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item>
+    fn tree_reduce<F>(mut self, mut f: F) -> Option<Self::Item>
     where
         F: FnMut(Self::Item, Self::Item) -> Self::Item,
         Self: Sized,
@@ -2505,7 +2505,7 @@ pub trait Itertools: Iterator {
             FF: FnMut(T, T) -> T,
         {
             // This function could be replaced with `it.next().ok_or(None)`,
-            // but half the useful tree_fold1 work is combining adjacent items,
+            // but half the useful tree_reduce work is combining adjacent items,
             // so put that in a form that LLVM is more likely to optimize well.
 
             let a = if let Some(v) = it.next() {
@@ -2555,6 +2555,16 @@ pub trait Itertools: Iterator {
         }
     }
 
+    /// See [`.tree_reduce()`](Itertools::tree_reduce).
+    #[deprecated(note = "Use .tree_reduce() instead", since = "0.13.0")]
+    fn tree_fold1<F>(self, f: F) -> Option<Self::Item>
+    where
+        F: FnMut(Self::Item, Self::Item) -> Self::Item,
+        Self: Sized,
+    {
+        self.tree_reduce(f)
+    }
+
     /// An iterator method that applies a function, producing a single, final value.
     ///
     /// `fold_while()` is basically equivalent to [`Iterator::fold`] but with additional support for
@@ -2949,7 +2959,7 @@ pub trait Itertools: Iterator {
     /// itertools::assert_equal(five_smallest, 0..5);
     /// ```
     #[cfg(feature = "use_alloc")]
-    fn k_smallest(mut self, k: usize) -> VecIntoIter<Self::Item>
+    fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item>
     where
         Self: Sized,
         Self::Item: Ord,
@@ -2963,9 +2973,10 @@ pub trait Itertools: Iterator {
             return Vec::new().into_iter();
         }
 
-        let mut heap = self.by_ref().take(k).collect::<BinaryHeap<_>>();
+        let mut iter = self.fuse();
+        let mut heap: BinaryHeap<_> = iter.by_ref().take(k).collect();
 
-        self.for_each(|i| {
+        iter.for_each(|i| {
             debug_assert_eq!(heap.len(), k);
             // Equivalent to heap.push(min(i, heap.pop())) but more efficient.
             // This should be done with a single `.peek_mut().unwrap()` but


Test patch:
diff --git a/tests/quick.rs b/tests/quick.rs
index 7b163d8..217ccbd 100644
--- a/tests/quick.rs
+++ b/tests/quick.rs
@@ -1334,7 +1334,7 @@ quickcheck! {
 }
 
 quickcheck! {
-    fn tree_fold1_f64(mut a: Vec<f64>) -> TestResult {
+    fn tree_reduce_f64(mut a: Vec<f64>) -> TestResult {
         fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64>
             where F: FnMut(f64, f64) -> f64
         {
@@ -1353,7 +1353,7 @@ quickcheck! {
             return TestResult::discard();
         }
 
-        let actual = a.iter().cloned().tree_fold1(f64::atan2);
+        let actual = a.iter().cloned().tree_reduce(f64::atan2);
 
         while a.len() > 1 {
             a = collapse_adjacent(a, f64::atan2);
diff --git a/tests/test_core.rs b/tests/test_core.rs
index 448f396..b5826ef 100644
--- a/tests/test_core.rs
+++ b/tests/test_core.rs
@@ -278,9 +278,9 @@ fn part() {
 }
 
 #[test]
-fn tree_fold1() {
+fn tree_reduce() {
     for i in 0..100 {
-        assert_eq!((0..i).tree_fold1(|x, y| x + y), (0..i).fold1(|x, y| x + y));
+        assert_eq!((0..i).tree_reduce(|x, y| x + y), (0..i).fold1(|x, y| x + y));
     }
 }
 
diff --git a/tests/test_std.rs b/tests/test_std.rs
index 5011053..1f319d8 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -1434,7 +1434,7 @@ fn fold_while() {
 }
 
 #[test]
-fn tree_fold1() {
+fn tree_reduce() {
     let x = [
         "",
         "0",
@@ -1461,7 +1461,7 @@ fn tree_fold1() {
             Some(s.to_string())
         };
         let num_strings = (0..i).map(|x| x.to_string());
-        let actual = num_strings.tree_fold1(|a, b| format!("{} {} x", a, b));
+        let actual = num_strings.tree_reduce(|a, b| format!("{} {} x", a, b));
         assert_eq!(actual, expected);
     }
 }