Repository: rust-itertools/itertools
Pull request #355 (2019-07-02 19:57:13)

Docs: Document that combinations may output duplicates.
Also added one doc test to show the case.

Did this as i needed to test it to check if it did this or not. Might as well put it in the docs to show it.


Patch:
diff --git a/README.rst b/README.rst
index b0ddda3..45f1b5a 100644
--- a/README.rst
+++ b/README.rst
@@ -10,8 +10,8 @@ __ https://docs.rs/itertools/
 
 |build_status|_ |crates|_
 
-.. |build_status| image:: https://travis-ci.org/bluss/rust-itertools.svg?branch=master
-.. _build_status: https://travis-ci.org/bluss/rust-itertools
+.. |build_status| image:: https://travis-ci.org/rust-itertools/itertools.svg?branch=master
+.. _build_status: https://travis-ci.org/rust-itertools/itertools
 
 .. |crates| image:: http://meritbadge.herokuapp.com/itertools
 .. _crates: https://crates.io/crates/itertools
diff --git a/benches/fold_specialization.rs b/benches/fold_specialization.rs
new file mode 100644
index 0000000..db3c995
--- /dev/null
+++ b/benches/fold_specialization.rs
@@ -0,0 +1,66 @@
+#![feature(test)]
+
+extern crate test;
+extern crate itertools;
+
+use itertools::Itertools;
+
+struct Unspecialized<I>(I);
+
+impl<I> Iterator for Unspecialized<I>
+where I: Iterator
+{
+    type Item = I::Item;
+
+    #[inline(always)]
+    fn next(&mut self) -> Option<I::Item> {
+        self.0.next()
+    }
+
+    #[inline(always)]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+mod specialization {
+    use super::*;
+
+    mod intersperse {
+        use super::*;
+
+        #[bench]
+        fn external(b: &mut test::Bencher)
+        {
+            let arr = [1; 1024];
+
+            b.iter(|| {
+                let mut sum = 0;
+                for &x in arr.into_iter().intersperse(&0) {
+                    sum += x;
+                }
+                sum
+            })
+        }
+
+        #[bench]
+        fn internal_specialized(b: &mut test::Bencher)
+        {
+            let arr = [1; 1024];
+
+            b.iter(|| {
+                arr.into_iter().intersperse(&0).fold(0, |acc, x| acc + x)
+            })
+        }
+
+        #[bench]
+        fn internal_unspecialized(b: &mut test::Bencher)
+        {
+            let arr = [1; 1024];
+
+            b.iter(|| {
+                Unspecialized(arr.into_iter().intersperse(&0)).fold(0, |acc, x| acc + x)
+            })
+        }
+    }
+}
diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs
index 59aebfa..4d0f5e1 100644
--- a/src/adaptors/mod.rs
+++ b/src/adaptors/mod.rs
@@ -463,61 +463,16 @@ impl<I> ExactSizeIterator for Step<I>
     where I: ExactSizeIterator
 {}
 
-
-struct MergeCore<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
-{
-    a: Peekable<I>,
-    b: Peekable<J>,
-    fused: Option<bool>,
+pub trait MergePredicate<T> {
+    fn merge_pred(&mut self, a: &T, b: &T) -> bool;
 }
 
+#[derive(Clone)]
+pub struct MergeLte;
 
-impl<I, J> Clone for MergeCore<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>,
-          Peekable<I>: Clone,
-          Peekable<J>: Clone
-{
-    fn clone(&self) -> Self {
-        clone_fields!(MergeCore, self, a, b, fused)
-    }
-}
-
-impl<I, J> MergeCore<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
-{
-    fn next_with<F>(&mut self, mut less_than: F) -> Option<I::Item>
-        where F: FnMut(&I::Item, &I::Item) -> bool
-    {
-        let less_than = match self.fused {
-            Some(lt) => lt,
-            None => match (self.a.peek(), self.b.peek()) {
-                (Some(a), Some(b)) => less_than(a, b),
-                (Some(_), None) => {
-                    self.fused = Some(true);
-                    true
-                }
-                (None, Some(_)) => {
-                    self.fused = Some(false);
-                    false
-                }
-                (None, None) => return None,
-            }
-        };
-
-        if less_than {
-            self.a.next()
-        } else {
-            self.b.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        // Not ExactSizeIterator because size may be larger than usize
-        size_hint::add(self.a.size_hint(), self.b.size_hint())
+impl<T: PartialOrd> MergePredicate<T> for MergeLte {
+    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
+        a <= b
     }
 }
 
@@ -528,30 +483,7 @@ impl<I, J> MergeCore<I, J>
 ///
 /// See [`.merge()`](../trait.Itertools.html#method.merge_by) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct Merge<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
-{
-    merge: MergeCore<I, J>,
-}
-
-impl<I, J> Clone for Merge<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>,
-          Peekable<I>: Clone,
-          Peekable<J>: Clone
-{
-    fn clone(&self) -> Self {
-        clone_fields!(Merge, self, merge)
-    }
-}
-
-impl<I, J> fmt::Debug for Merge<I, J>
-    where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
-          I::Item: fmt::Debug,
-{
-    debug_fmt_fields!(Merge, merge.a, merge.b);
-}
+pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
 
 /// Create an iterator that merges elements in `i` and `j`.
 ///
@@ -569,29 +501,7 @@ pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as Int
           J: IntoIterator<Item = I::Item>,
           I::Item: PartialOrd
 {
-    Merge {
-        merge: MergeCore {
-            a: i.into_iter().peekable(),
-            b: j.into_iter().peekable(),
-            fused: None,
-        },
-    }
-}
-
-impl<I, J> Iterator for Merge<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>,
-          I::Item: PartialOrd
-{
-    type Item = I::Item;
-
-    fn next(&mut self) -> Option<I::Item> {
-        self.merge.next_with(|a, b| a <= b)
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.merge.size_hint()
-    }
+    merge_by_new(i, j, MergeLte)
 }
 
 /// An iterator adaptor that merges the two base iterators in ascending order.
@@ -605,7 +515,9 @@ pub struct MergeBy<I, J, F>
     where I: Iterator,
           J: Iterator<Item = I::Item>
 {
-    merge: MergeCore<I, J>,
+    a: Peekable<I>,
+    b: Peekable<J>,
+    fused: Option<bool>,
     cmp: F,
 }
 
@@ -613,20 +525,25 @@ impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
     where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
           I::Item: fmt::Debug,
 {
-    debug_fmt_fields!(MergeBy, merge.a, merge.b);
+    debug_fmt_fields!(MergeBy, a, b);
+}
+
+impl<T, F: FnMut(&T, &T)->bool> MergePredicate<T> for F {
+    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
+        self(a, b)
+    }
 }
 
 /// Create a `MergeBy` iterator.
-pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I, J, F>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
+pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
+    where I: IntoIterator,
+          J: IntoIterator<Item = I::Item>,
+          F: MergePredicate<I::Item>,
 {
     MergeBy {
-        merge: MergeCore {
-            a: a.peekable(),
-            b: b.peekable(),
-            fused: None,
-        },
+        a: a.into_iter().peekable(),
+        b: b.into_iter().peekable(),
+        fused: None,
         cmp: cmp,
     }
 }
@@ -639,23 +556,43 @@ impl<I, J, F> Clone for MergeBy<I, J, F>
           F: Clone
 {
     fn clone(&self) -> Self {
-        clone_fields!(MergeBy, self, merge, cmp)
+        clone_fields!(MergeBy, self, a, b, fused, cmp)
     }
 }
 
 impl<I, J, F> Iterator for MergeBy<I, J, F>
     where I: Iterator,
           J: Iterator<Item = I::Item>,
-          F: FnMut(&I::Item, &I::Item) -> bool
+          F: MergePredicate<I::Item>
 {
     type Item = I::Item;
 
     fn next(&mut self) -> Option<I::Item> {
-        self.merge.next_with(&mut self.cmp)
+        let less_than = match self.fused {
+            Some(lt) => lt,
+            None => match (self.a.peek(), self.b.peek()) {
+                (Some(a), Some(b)) => self.cmp.merge_pred(a, b),
+                (Some(_), None) => {
+                    self.fused = Some(true);
+                    true
+                }
+                (None, Some(_)) => {
+                    self.fused = Some(false);
+                    false
+                }
+                (None, None) => return None,
+            }
+        };
+        if less_than {
+            self.a.next()
+        } else {
+            self.b.next()
+        }
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        self.merge.size_hint()
+        // Not ExactSizeIterator because size may be larger than usize
+        size_hint::add(self.a.size_hint(), self.b.size_hint())
     }
 }
 
@@ -753,53 +690,88 @@ impl<I, F> Iterator for Coalesce<I, F>
     }
 }
 
-/// An iterator adaptor that removes repeated duplicates.
+/// An iterator adaptor that removes repeated duplicates, determining equality using a comparison function.
 ///
-/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information.
+/// See [`.dedup_by()`](../trait.Itertools.html#method.dedup_by) or [`.dedup()`](../trait.Itertools.html#method.dedup) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct Dedup<I>
+pub struct DedupBy<I, Pred>
     where I: Iterator
 {
     iter: CoalesceCore<I>,
+    dedup_pred: Pred,
 }
 
-impl<I: Clone> Clone for Dedup<I>
+pub trait DedupPredicate<T> { // TODO replace by Fn(&T, &T)->bool once Rust supports it
+    fn dedup_pair(&mut self, a: &T, b: &T) -> bool;
+}
+
+#[derive(Clone)]
+pub struct DedupEq;
+
+impl<T: PartialEq> DedupPredicate<T> for DedupEq {
+    fn dedup_pair(&mut self, a: &T, b: &T) -> bool {
+        a==b
+    }
+}
+
+impl<T, F: FnMut(&T, &T)->bool> DedupPredicate<T> for F {
+    fn dedup_pair(&mut self, a: &T, b: &T) -> bool {
+        self(a, b)
+    }
+}
+
+/// An iterator adaptor that removes repeated duplicates.
+///
+/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information.
+pub type Dedup<I>=DedupBy<I, DedupEq>;
+
+impl<I: Clone, Pred: Clone> Clone for DedupBy<I, Pred>
     where I: Iterator,
-          I::Item: Clone
+          I::Item: Clone,
 {
     fn clone(&self) -> Self {
-        clone_fields!(Dedup, self, iter)
+        clone_fields!(DedupBy, self, iter, dedup_pred)
     }
 }
 
-/// Create a new `Dedup`.
-pub fn dedup<I>(mut iter: I) -> Dedup<I>
-    where I: Iterator
+/// Create a new `DedupBy`.
+pub fn dedup_by<I, Pred>(mut iter: I, dedup_pred: Pred) -> DedupBy<I, Pred>
+    where I: Iterator,
 {
-    Dedup {
+    DedupBy {
         iter: CoalesceCore {
             last: iter.next(),
             iter: iter,
         },
+        dedup_pred,
     }
 }
 
-impl<I> fmt::Debug for Dedup<I>
+/// Create a new `Dedup`.
+pub fn dedup<I>(iter: I) -> Dedup<I>
+    where I: Iterator
+{
+    dedup_by(iter, DedupEq)
+}
+
+impl<I, Pred> fmt::Debug for DedupBy<I, Pred>
     where I: Iterator + fmt::Debug,
           I::Item: fmt::Debug,
 {
     debug_fmt_fields!(Dedup, iter);
 }
 
-impl<I> Iterator for Dedup<I>
+impl<I, Pred> Iterator for DedupBy<I, Pred>
     where I: Iterator,
-          I::Item: PartialEq
+          I::Item: PartialEq,
+          Pred: DedupPredicate<I::Item>,
 {
     type Item = I::Item;
 
     fn next(&mut self) -> Option<I::Item> {
+        let ref mut dedup_pred = self.dedup_pred;
         self.iter.next_with(|x, y| {
-            if x == y { Ok(x) } else { Err((x, y)) }
+            if dedup_pred.dedup_pair(&x, &y) { Ok(x) } else { Err((x, y)) }
         })
     }
 
@@ -811,8 +783,9 @@ impl<I> Iterator for Dedup<I>
         where G: FnMut(Acc, Self::Item) -> Acc,
     {
         if let Some(mut last) = self.iter.last {
+            let mut dedup_pred = self.dedup_pred;
             accum = self.iter.iter.fold(accum, |acc, elt| {
-                if elt == last {
+                if dedup_pred.dedup_pair(&elt, &last) {
                     acc
                 } else {
                     f(acc, replace(&mut last, elt))
diff --git a/src/intersperse.rs b/src/intersperse.rs
index b1dc732..f825442 100644
--- a/src/intersperse.rs
+++ b/src/intersperse.rs
@@ -57,4 +57,23 @@ impl<I> Iterator for Intersperse<I>
         let sh = self.iter.size_hint();
         size_hint::add_scalar(size_hint::add(sh, sh), has_peek)
     }
+
+    fn fold<B, F>(mut self, init: B, mut f: F) -> B where
+        Self: Sized, F: FnMut(B, Self::Item) -> B,
+    {
+        let mut accum = init;
+        
+        if let Some(x) = self.peek.take() {
+            accum = f(accum, x);
+        }
+
+        let element = &self.element;
+
+        self.iter.fold(accum,
+            |accum, x| {
+                let accum = f(accum, element.clone());
+                let accum = f(accum, x);
+                accum
+        })
+    }
 }
diff --git a/src/lib.rs b/src/lib.rs
index aa01a4f..2ac9add 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -79,6 +79,7 @@ pub use std::iter as __std_iter;
 pub mod structs {
     pub use adaptors::{
         Dedup,
+        DedupBy,
         Interleave,
         InterleaveShortest,
         Product,
@@ -956,6 +957,28 @@ pub trait Itertools : Iterator {
         adaptors::dedup(self)
     }
 
+    /// Remove duplicates from sections of consecutive identical elements,
+    /// determining equality using a comparison function.
+    /// If the iterator is sorted, all elements will be unique.
+    ///
+    /// Iterator element type is `Self::Item`.
+    ///
+    /// This iterator is *fused*.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)];
+    /// itertools::assert_equal(data.into_iter().dedup_by(|x, y| x.1==y.1),
+    ///                         vec![(0, 1.), (0, 2.), (0, 3.), (1, 2.)]);
+    /// ```
+    fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp>
+        where Self: Sized,
+              Cmp: FnMut(&Self::Item, &Self::Item)->bool,
+    {
+        adaptors::dedup_by(self, cmp)
+    }
+
     /// Return an iterator adaptor that filters out elements that have
     /// already been produced once during the iteration. Duplicates
     /// are detected using hash and equality.
@@ -1123,6 +1146,19 @@ pub trait Itertools : Iterator {
     ///     vec![2, 3, 4],
     ///     ]);
     /// ```
+    ///
+    /// Note: Combinations does not take into account the equality of the iterated values.
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// let it = vec![1, 2, 2].into_iter().combinations(2);
+    /// itertools::assert_equal(it, vec![
+    ///     vec![1, 2], // Note: these are the same
+    ///     vec![1, 2], // Note: these are the same
+    ///     vec![2, 2],
+    /// ]);
+    /// ```
+    ///
     #[cfg(feature = "use_std")]
     fn combinations(self, n: usize) -> Combinations<Self>
         where Self: Sized,
@@ -1561,7 +1597,7 @@ pub trait Itertools : Iterator {
     /// ```
     ///
     /// With a `start` value of 0 and an addition as folding function,
-    /// this effetively results in *((0 + 1) + 2) + 3*
+    /// this effectively results in *((0 + 1) + 2) + 3*
     ///
     /// ```
     /// use std::ops::Add;


Test patch:
diff --git a/tests/fold_specialization.rs b/tests/fold_specialization.rs
new file mode 100644
index 0000000..ac5d6a2
--- /dev/null
+++ b/tests/fold_specialization.rs
@@ -0,0 +1,15 @@
+extern crate itertools;
+
+use itertools::Itertools;
+
+#[test]
+fn specialization_intersperse() {
+    let mut iter = (1..2).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+
+    let mut iter = (1..3).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+
+    let mut iter = (1..4).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+}
diff --git a/tests/quick.rs b/tests/quick.rs
index 886c405..95c1ba8 100644
--- a/tests/quick.rs
+++ b/tests/quick.rs
@@ -635,12 +635,26 @@ quickcheck! {
     }
 }
 
+quickcheck! {
+    fn equal_dedup_by(a: Vec<(i32, i32)>) -> bool {
+        let mut b = a.clone();
+        b.dedup_by(|x, y| x.0==y.0);
+        itertools::equal(&b, a.iter().dedup_by(|x, y| x.0==y.0))
+    }
+}
+
 quickcheck! {
     fn size_dedup(a: Vec<i32>) -> bool {
         correct_size_hint(a.iter().dedup())
     }
 }
 
+quickcheck! {
+    fn size_dedup_by(a: Vec<(i32, i32)>) -> bool {
+        correct_size_hint(a.iter().dedup_by(|x, y| x.0==y.0))
+    }
+}
+
 quickcheck! {
     fn exact_repeatn((n, x): (usize, i32)) -> bool {
         let it = itertools::repeat_n(x, n);
diff --git a/tests/test_std.rs b/tests/test_std.rs
index b587f44..c390d32 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -98,6 +98,22 @@ fn dedup() {
     assert_eq!(&xs_d, &ys);
 }
 
+#[test]
+fn dedup_by() {
+    let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
+    let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
+    it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1==y.1));
+    let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
+    let ys = [(0, 1)];
+    it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0==y.0));
+
+    let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
+    let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
+    let mut xs_d = Vec::new();
+    xs.iter().dedup_by(|x, y| x.1==y.1).fold((), |(), &elt| xs_d.push(elt));
+    assert_eq!(&xs_d, &ys);
+}
+
 #[test]
 fn all_equal() {
     assert!(!"AABBCCC".chars().all_equal());