Repository: rust-itertools/itertools
Pull request #357 (2019-07-20 21:50:44)

Introduce dedup_by
This refers to #325. My suggestion consists of two steps:

* Generalize `Dedup` to `DedupBy` so that `DedupBy` stores a comparison function. `Dedup` is then defined via a type alias so that `Dedup<I>=DedupBy<I, SimpleCompareEq>`. Since `SimpleCompareEq` is an empty struct, it should not occupy more memory than it did before. `SimpleCompareEq` simply compares elements via `==`.
* Introduce `dedup_by` taking a comparison function, returning an appropriate `DedupBy`.

Some questions:
* I did not see this kind of architecture (i.e. basically only having `DedupBy`, and type-aliasing `Dedup`) so far, but to me it seems it leads to concise, straightforward code. Do you have any objections about this?
* If the previous question is answered "no objections": Should we try to simplify e.g. `Merge` and `MergeBy` in a similar way?
* Should we, for consistency, also think about `dedup_by_key`?


Patch:
diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs
index 59aebfa..aa8e646 100644
--- a/src/adaptors/mod.rs
+++ b/src/adaptors/mod.rs
@@ -753,53 +753,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,
+}
+
+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;
 }
 
-impl<I: Clone> Clone for Dedup<I>
+#[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 +846,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/lib.rs b/src/lib.rs
index 064a07d..dc7d435 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.


Test patch:
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());