How can I add new methods to Iterator?

I want to define a .unique() method on iterators that enables me to iterate without duplicates.

use std::collections::HashSet;

struct UniqueState<'a> {
    seen: HashSet<String>,
    underlying: &'a mut Iterator<Item = String>,
}

trait Unique {
    fn unique(&mut self) -> UniqueState;
}

impl Unique for Iterator<Item = String> {
    fn unique(&mut self) -> UniqueState {
        UniqueState {
            seen: HashSet::new(),
            underlying: self,
        }
    }
}

impl<'a> Iterator for UniqueState<'a> {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        while let Some(x) = self.underlying.next() {
            if !self.seen.contains(&x) {
                self.seen.insert(x.clone());
                return Some(x);
            }
        }
        None
    }
}

This compiles. However, when I try to use in the same file:

fn main() {
    let foo = vec!["a", "b", "a", "cc", "cc", "d"];

    for s in foo.iter().unique() {
        println!("{}", s);
    }
}

I get the following error:

error[E0599]: no method named `unique` found for type `std::slice::Iter<'_, &str>` in the current scope
  --> src/main.rs:37:25
   |
37 |     for s in foo.iter().unique() {
   |                         ^^^^^^
   |
   = help: items from traits can only be used if the trait is implemented and in scope
   = note: the following trait defines an item `unique`, perhaps you need to implement it:
           candidate #1: `Unique`

What am I doing wrong? How would I extend this arbitrary hashable types?

Solution 1:

In your particular case, it's because you have implemented your trait for an iterator of String, but your vector is providing an iterator of &str. Here's a more generic version:

use std::collections::HashSet;
use std::hash::Hash;

struct Unique<I>
where
    I: Iterator,
{
    seen: HashSet<I::Item>,
    underlying: I,
}

impl<I> Iterator for Unique<I>
where
    I: Iterator,
    I::Item: Hash + Eq + Clone,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(x) = self.underlying.next() {
            if !self.seen.contains(&x) {
                self.seen.insert(x.clone());
                return Some(x);
            }
        }
        None
    }
}

trait UniqueExt: Iterator {
    fn unique(self) -> Unique<Self>
    where
        Self::Item: Hash + Eq + Clone,
        Self: Sized,
    {
        Unique {
            seen: HashSet::new(),
            underlying: self,
        }
    }
}

impl<I: Iterator> UniqueExt for I {}

fn main() {
    let foo = vec!["a", "b", "a", "cc", "cc", "d"];

    for s in foo.iter().unique() {
        println!("{}", s);
    }
}

Broadly, we create a new extension trait called UniqueExt which has Iterator as a supertrait. When Iterator is a supertrait, we will have access to the associated type Iterator::Item.

This trait defines the unique method, which is only valid to call when then iterated item can be:

1. Hashed
2. Compared for total equality
3. Cloned

Additionally, it requires that the item implementing Iterator have a known size at compile time. This is done so that the iterator can be consumed by the Unique iterator adapter.

The other important part is the blanket implementation of the trait for any type that also implements Iterator:

impl<I: Iterator> UniqueExt for I {}