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

anyere · March 6, 2017, 3:31pm

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?

ConnyOnny · March 6, 2017, 4:43pm

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.~~

anyere · March 7, 2017, 3:21am

I tried and now everything works as expected 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!

anyere · March 8, 2017, 5:10pm

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?

cuviper · March 8, 2017, 6:11pm

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)));

anyere · March 8, 2017, 6:28pm

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?

vitalyd · March 8, 2017, 7:44pm

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)?

anyere · March 8, 2017, 8:04pm

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

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

vitalyd · March 8, 2017, 8:07pm

Something like this: Rust Playground

anyere · March 8, 2017, 8:42pm

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?

cuviper · March 8, 2017, 8:47pm

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

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

cuviper · March 8, 2017, 9:01pm

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>

anyere · March 9, 2017, 5:05pm

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

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)
    }
}

// ...

krdln · March 9, 2017, 5:15pm

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).

cuviper · March 9, 2017, 5:15pm

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.

cuviper · March 9, 2017, 5:31pm

OK, it works with associated types:

pub trait Unpair {
    type Left;
    type Right;

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

Full example: Rust Playground

vitalyd · March 9, 2017, 7:57pm

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.

anyere · March 9, 2017, 11:42pm

First of all I want to thank you @ConnyOnny, @cuviper, @vitalyd and @krdln for your support !
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 ?!)

cuviper · March 10, 2017, 1:01am

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...

Topic		Replies	Views
Writing a (parallel) zip for a const generic number of (parallel) iterators help	2	592	July 21, 2021
Zip two finite iterators and pad the shorter one help	5	1207	January 12, 2023
Can somene review my learning exercise? code review	9	712	October 7, 2022
Generic iterator type as reference help	7	384	January 6, 2023
Implementing filter on all generic iterators help	7	1734	February 18, 2020

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

Syntax highlighting in code examples:

iteration problem

Related Topics