[Solved]? Writing a generic iterator: filter and zip in place

I want to have one itereator over two ordered key-value sequences (as iterators) matching their keys against each other and yielding the equal ones. In my first attempt I got stuck after filtering both iterators and want to zip the filtered iterators. See the uncommented line (18) in the following gist or playground:

/// Takes two iterators over an ordered (key, value) sequence,
/// removing all entries which keys don't find a match in place
/// and zips the resulting filtered iterators afterwards.
///
/// Assumes the keys are in ascending order.
pub fn filter_zip<K, V, W, A, B>(a: &mut A, b: &mut B) // -> Iterator<Item=(K,(V, W))>
    where K: Ord,
          A: Iterator<Item=(K, V)>,
          B: Iterator<Item=(K, W)>,
{
    a.filter(|&(ref key_a,_)| {
            let mut is_equal = false;
            b.filter(|&(ref key_b,_)| {
                if key_a == key_b {
                    is_equal = true;
                    true
                } else {
                    key_a > key_b
                }
            });
            is_equal
        })
//        .zip(b)
        ;
}

Uncommenting that line the compiler tells me I cant move b in the call to zip(b) beacause its borrowed. I know this makes sense at all but does anyone have an idea how to achieve my desired implementation?

Edit: how can I activate syntaxhighliting for code examples?

Syntax highlighting in code examples:

To get

fn main()

write

```rust
fn main()
```

iteration problem

For your problem I think it will be easiest if you just make a struct that owns the two iterators and implement the Iterator trait for it. I think you then don't even need Ord, but only Eq.

1 Like

I tried and now everything works as expected :slight_smile: Here is the code I came up with:

struct FilterZip<A, B> {
    a: A,
    b: B,
}

impl<K, V, W, A, B> Iterator for FilterZip<A, B>
    where K: Ord,
          A: Iterator<Item=(K, V)>,
          B: Iterator<Item=(K, W)>,
{
    type Item = (K, (V, W));
    fn next(&mut self) -> Option<Self::Item> {
        if let (Some((mut ka, mut va)), Some((mut kb, mut vb))) = (self.a.next(), self.b.next()) {
            while ka < kb {
                if let Some((kn,vn)) = self.a.next() {
                    ka = kn;
                    va = vn;
                } else { return None; }
            }
            while ka > kb {
                if let Some((kn,vn)) = self.b.next() {
                    kb = kn;
                    vb = vn;
                } else { return None; }
            }
            return Some((ka, (va, vb)));
        }
        None
    }
}

trait ToFilterZip<B>: Sized {
    /// Zips the iterators by matching their keys against each other in ascending order
    /// and only yielding the equal ones.
    fn filter_zip(self, B) -> FilterZip<Self, B>;
}

impl<K, V, W, A, B> ToFilterZip<B> for A
    where K: Ord,
          A: Iterator<Item=(K, V)>,
          B: Iterator<Item=(K, W)>,
{
    fn filter_zip(self, b: B) -> FilterZip<A, B> {
        FilterZip {
            a: self,
            b: b,
        }
    }
}

Thank you for your help @ConnyOnny!

2 Likes

Hello its me again... I implemented a testcase in playground for two vec's:

let mut a = Vec::new();
let mut b = Vec::new();

a.push((0, 0));
a.push((1, 1));

b.push((1, 'a'));
b.push((2, 'b'));

let mut iter = a.iter().filter_zip(b.iter());
assert_eq!(iter.next(), Some((&1, (&1, &'a'))));
assert_eq!(iter.next(), None);

but I get the following error I cant resolve myself...

error: no method named `filter_zip` found for type
    `std::slice::Iter<'_, ({integer}, {integer})>` in the current scope
[...]
note: the method `filter_zip` exists but the following trait bounds were not satisfied:
    `&std::slice::Iter<'_, ({integer}, {integer})> : std::iter::Iterator`

Can anyone explain me what to do?

note: the method `filter_zip` exists but the following trait bounds were not satisfied:
    `&std::slice::Iter<'_, ({integer}, {integer})> : std::iter::Iterator`

Huh, the error message is confused. If you convert this to explicit UFCS form, it's more helpful:

13 |     let mut iter = ToFilterZip::filter_zip(a.iter(), b.iter());
   |                    ^^^^^^^^^^^^^^^^^^^^^^^ expected reference, found tuple
   |
   = note: expected type `&({integer}, {integer})`
   = note:    found type `(_, _)`
   = note: required because of the requirements on the impl of `ToFilterZip<_>` for `std::slice::Iter<'_, ({integer}, {integer})>`
   = note: required by `ToFilterZip::filter_zip`

That is, slice::Iter iterates by reference, like Iterator<Item=&T>, where T in this case is the tuple. Your ToFilterZip is requiring Iterator<Item=(K, V)>, iterating tuple values with arbitrary types inside.

It works if you map each &(x, y) to (&x, &y) like this:

    let mut iter = a.iter().map(|t| (&t.0, &t.1))
                    .filter_zip(b.iter().map(|t| (&t.0, &t.1)));

Mhm.. that seems not very practical to me. I would like to hide the .map part completely for the user.

Couldnt I provide a tailored implementation for this? Something like...

impl<'a, K, V, W, A, B> ToFilterZip<B> for A
    where K: Ord,
          A: Iterator<Item=&'a(K, V)>,
          B: Iterator<Item=&'a(K, W)>,
{ ... }

Meh... it dawns on me I need a full blown struct + impl for this?! Whats the ideomatic approach in this kind of situation?

You can adapt your existing struct to do this. Or do you want to support iter() and into_iter() (ie a consuming iterator that returns tuple values, not tuple references)?

I only need support for iter() and iter_mut().

I tried but always get livetime errors :confused: sry I'm not that save in using livetimes. Could someone advice me?

Something like this: Rust Playground

1 Like

This seems to work with the given example, but when using the following iteratorcombination

let mut iter = a.iter().filter_zip(b.iter_mut());

it doesnt work again.

Is it possible to provide one implement for all types of iteratorcombination regardless if they are into_iter(), iter() or iter_mut(), ideally generic over their item like

Iterator<Item=SomeGenericType<K,V>>?

where SomeGenericType<K,V> includes tupletypes?

FWIW, I filed an issue to see if we can get better diagnostics for that error:

https://github.com/rust-lang/rust/issues/40375

1 Like

Something like:

trait Unpair<T, U> {
    fn unpair(self) -> (T, U);
}

impl<T, U> Unpair<T, U> for (T, U) {
    fn unpair(self) -> (T, U) {
        (self.0, self.1)
    }
}

impl<'a, T, U> Unpair<&'a T, &'a U> for &'a (T, U) {
    fn unpair(self) -> (&'a T, &'a U) {
        (&self.0, &self.1)
    }
}

impl<'a, T, U> Unpair<&'a mut T, &'a mut U> for &'a mut (T, U) {
    fn unpair(self) -> (&'a mut T, &'a mut U) {
        (&mut self.0, &mut self.1)
    }
}

Then your bound would be roughly where A: Iterator, A::Item: Unpair<K, V>

I tried to implement @cuviper approach in playground and again I run into some errors I'm not able to resolve :confused:

Errors:

the trait bound `Unpair<K, V> + 'static: std::marker::Sized` is not satisfied
the trait `Unpair` cannot be made into an object

Impls:

pub trait ToFilterZip<B>: Sized {
    /// Zips the iterators by matching their keys against each other
    /// in ascending order and only yielding the equal ones.
    fn filter_zip(self, B) -> FilterZip<Self, B>;
}

pub struct FilterZip<A, B> {
    a: A,
    b: B,
}

impl<K, V, W, A, B> Iterator for FilterZip<A, B>
    where K: Ord,
          A: Iterator<Item=Unpair<K, V>>,
          B: Iterator<Item=Unpair<K, W>>,
{
    type Item = Unpair<K, (V, W)>;
    fn next(&mut self) -> Option<Self::Item> {
        // ...
        None
    }
}

impl<K, V, W, A, B> ToFilterZip<B> for A
    where K: Ord,
          A: Iterator<Item=Unpair<K, V>>,
          B: Iterator<Item=Unpair<K, W>>,
{
    fn filter_zip(self, b: B) -> FilterZip<A, B> {
        FilterZip {
            a: self,
            b: b,
        }
    }
}

trait Unpair<T, U>: Sized {
    fn unpair(self) -> (T, U);
}

impl<T, U> Unpair<T, U> for (T, U) {
    fn unpair(self) -> (T, U) {
        (self.0, self.1)
    }
}

// ...

You should mark your Item as implementing Unpair, not being Unpair itself:

    where K: Ord,
          X: Unpair<K, V>
          Y: Unpair<K, W>
          A: Iterator<Item=X>,
          B: Iterator<Item=Y>,

Also, if both K and V are cheap to clone, your original approach requires caller just to do:

let mut iter = a.iter().cloned().filter_zip(b.iter().cloned());

Which is not that bad imho.

What is also worth making is to change filter_zip argument from something implementing Iterator to something implementing IntoIterator (just like regular zip does). That way, the user could just do .filter_zip(&b).

You're trying to use Unpair like a type in itself, rather than as a trait to constrain the iterators. I was thinking more like this:

impl<K, V, W, A, B> Iterator for FilterZip<A, B>
    where K: Ord,
          A: Iterator,
          B: Iterator,
          A::Item: Unpair<K, V>,
          B::Item: Unpair<K, W>,

{
    type Item = (K, (V, W));
    fn next(&mut self) -> Option<Self::Item> {
        // ...
        None
    }
}

But then it gets errors like this for K, V, and U:

error[E0207]: the type parameter `K` is not constrained by the impl trait, self type, or predicates

I'm not sure how to fix that. It might have to use associated types for Unpair.

OK, it works with associated types:

pub trait Unpair {
    type Left;
    type Right;

    fn unpair(self) -> (Self::Left, Self::Right);
}

Full example: Rust Playground

2 Likes

I wonder if it makes sense for the compiler to omit the "or predicates" part of the help text - it looks confusing in this case because K is used in the predicates section. What it's really trying to say, I guess, is that it cannot uniquely identify what concrete type K would be given the trait and type its implemented for.

First of all I want to thank you @ConnyOnny, @cuviper, @vitalyd and @krdln for your support :slight_smile: !
Because finally I came up with an implementaion I feel quite confident with:

https://github.com/Bendrien/ommap/blob/0964523571956cd0f47baabe0546d50d7acd6289/src/iter.rs

I tweaked the Unpair impl for &mut (T, U) like so

impl<'a, T, U> Unpair for &'a mut (T, U) {
    type Left = &'a T;
    type Right = &'a mut U;

    fn unpair(self) -> (&'a T, &'a mut U) {
        (&self.0, &mut self.1)
    }
}

for beeing flexible about mutability concerning the right part of a tuple (the value V or W). Thus I'm able to write code like this

let mut iter = a.iter().filter_zip(b.iter_mut());
assert_eq!(iter.next(), Some((&1, (&'a', &mut 'b'))));
let mut iter = a.iter_mut().filter_zip(b.iter());
assert_eq!(iter.next(), Some((&1, (&mut 'a', &'b'))));

and thats all I want the filter_zip to be capable of.

However this brings me to the (hopefully) last issue I see to make this iterator generic for any usecases. Currently its not possible to make the "Key" part in the resulting tuple mutable like

let mut iter = a.iter_mut().filter_zip(b.iter_mut());
assert_eq!(iter.next(), Some((&mut 1, (&mut 'a', &mut 'b'))));
                              ^^^^^^

I tried to solve this by adding the impl from @cuviper again

impl<'a, T, U> Unpair<&'a mut T, &'a mut U> for &'a mut (T, U) {
    fn unpair(self) -> (&'a mut T, &'a mut U) {
        (&mut self.0, &mut self.1)
    }
} 

but then the compiler yells at me (see playground)

error[E0119]: conflicting implementations of trait `iter::Unpair` for type `&mut (_, _)`

And again I have no clue how to go over this... (the version without associated types was capable of impls like that :confused: ?!)

Right. You're implementing the exact same Unpair trait for the exact same type, which is a conflict. When you call unpair, how is it supposed to know which Unpair implementation you meant?

The implementations were allowed without associate types because Unpair<&'a mut T, &'a mut U> and Unpair<&'a T, &'a mut U> are effectively different traits. And this is why it didn't work as a constraint when I wrote it that way, because the constraints didn't offer any way to choose between these possibilities.

So it seems you're trying to do this mapping:

  • K1 = T and K2 = T becomes K = T
    which also covers these:
    • K1 = &T and K2 = &T becomes K = &T
    • K1 = &mut T and K2 = &mut T becomes K = &mut T
  • K1 = &mut T and K2 = &T becomes K = &T
  • K1 = &T and K2 = &mut T becomes K = &T

How about another trait?

pub trait Common<T> {
    type Target;
    fn into_common(self) -> Self::Target;
}

With constraints like:

impl<K, K1, K2, V, W, A, B> Iterator for FilterZip<A, B>
    where K: Ord,
          K1: Common<K2, Target = K>,
          K2: Common<K1, Target = K>,
          A: Iterator,
          A::Item: Unpair<Left = K1, Right = V>,
          B: Iterator,
          B::Item: Unpair<Left = K2, Right = W>,

And this exceedingly generic code actually works! Rust Playground

Now you want K + &K, K + &mut K, and vice versa? Umm, exercise left to the reader...

1 Like