Rust implementing merge-sorted iterator

Question

I'm trying to implement an iterator that merges two sorted iterators. I'm running to issues borrowing fields from a struct.

How do I avoid this error? I tried using borrowed references but that doesn't seem to help, since eventually I need to move the values of a_item and b_item.

use std::num::Saturating;

pub struct MergeSorted<A, T> {
    a: T,
    b: T,
    a_item: Option<A>,
    b_item: Option<A>,
}

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {

        match (self.a_item, self.b_item) {
            (None, None) => None,

            (None, Some(y)) => {
                let result = self.b_item;
                self.b_item = None;
                return result;
            }

            (Some(x), None) => {
                let result = self.a_item;
                self.a_item = self.a.next();
                result
            }

            (Some(x), Some(y)) => {
                if x < y {
                    let result = self.a_item;
                    self.a_item = self.a.next();
                    result
                } else {
                    let result = self.b_item;
                    self.b_item = self.b.next();
                    result
                }
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // stub
        (10, Some(100))
    }
}

Here's the specific error, this is repeated for all uses of self.a_item and self.b_item.

error: cannot move out of dereference of `&mut`-pointer
       match (self.a_item, self.b_item) {
              ^~~~~~~~~~~

Answer 1

The first problem is this pattern:

let result = self.b_item;
self.b_item = None;
return result;

After the first line and before the second line self.b_item becomes moved out, making a "hole" in self (even if we forget that self is a borrowed pointer and you can't move out of it). This is not allowed. To express such pattern there is a special function in std::mem, called replace.

The second, main problem is that A is not implicitly copyable, so you when you try to match on values of type Option<A>, these values are moved out, but moving out from inside of &/&mut pointer is prohibited. The only way around this is to match on references. But then you should be careful, because borrowing rules only allow you to have single mutable borrow at a time. So you have to organize a kind of "flow" of references to self.a_item and self.b_item through the match statement, using pattern bindings.

The following code compiles. You can also replace result variable and Some() usage in the body of match directly with mem::replace() calls, but I thought that separating values selection and mem::replace() call make the code cleaner. Also I couldn't use Some(x) and Some(y) patterns in the last match arm because the references themselves are moved into a_item and b_item.

use std::mem;

pub struct MergeSorted<A, T> {
    a: T,
    b: T,
    a_item: Option<A>,
    b_item: Option<A>,
}

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        let result = match (&mut self.a_item, &mut self.b_item) {
            (&None, &None) => None,
            (&None, b_item @ &Some(_)) => Some((b_item, None)),
            (a_item @ &Some(_), &None) => Some((a_item, self.a.next())),
            (a_item @ &Some(_), b_item @ &Some(_)) => Some(
                if a_item.get_ref() < b_item.get_ref() {
                    (a_item, self.a.next())
                } else {
                    (b_item, self.b.next())
                }
            )
        };

        result.and_then(|(dest, value)| mem::replace(dest, value))
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // stub
        (10, Some(100))
    }
}

Answer 2

This solution will work with Rust 1.2 and likely and Rust 1.x.

Instead of keeping our own Option of items, I opted to use the peekable iterator adapter. This allows us to look forward one item, without losing it.

I also broke down the Iterator::next method into two parts - one that determines from which side to pull, and one that actually advances that iterator.

There's also general updates for how iterators are now defined with associated types.

use std::iter::Peekable;
use std::cmp::Ordering;

struct MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
{
    left: Peekable<L>,
    right: Peekable<R>,
}

impl<L, R> MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
{
    fn new(left: L, right: R) -> Self {
        MergeAscending {
            left: left.peekable(),
            right: right.peekable(),
        }
    }
}

impl<L, R> Iterator for MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
    L::Item: Ord,
{
    type Item = L::Item;

    fn next(&mut self) -> Option<L::Item> {
        let which = match (self.left.peek(), self.right.peek()) {
            (Some(l), Some(r)) => Some(l.cmp(r)),
            (Some(_), None) => Some(Ordering::Less),
            (None, Some(_)) => Some(Ordering::Greater),
            (None, None) => None,
        };

        match which {
            Some(Ordering::Less) => self.left.next(),
            Some(Ordering::Equal) => self.left.next(),
            Some(Ordering::Greater) => self.right.next(),
            None => None,
        }
    }
}

fn main() {
    let left = [1, 3, 5, 7, 9];
    let right = [3, 4, 5, 6, 7];

    let result: Vec<_> = MergeAscending::new(left.iter(), right.iter()).collect();
    println!("{:?}", result);
}