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


#1

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?


#2

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.


#3

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!


#4

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?


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

#6

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?


#7

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


#8

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?


#9

Something like this: https://is.gd/BjDCL2


#10

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?


#11

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


#12

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>


#13

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

// ...

#14

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


#15

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.


#16

OK, it works with associated types:

pub trait Unpair {
    type Left;
    type Right;

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

Full example: https://is.gd/cRzfNU


#17

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.


#18

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:

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


#19

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! https://play.rust-lang.org/?gist=d7a341ff2b60e27078fb093cf233986f&version=stable&backtrace=0

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