Rust implementa un iterador ordenado por fusión

Question

Estoy intentando implementar un iterador que combine dos iteradores ordenados.Estoy corriendo hacia problemas al tomar prestados campos de una estructura.

¿Cómo evito este error?Intenté usar referencias prestadas pero eso no parece ayudar, ya que eventualmente necesito mover los valores de a_item y 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))
    }
}

Aquí está el error específico, esto se repite para todos los usos de self.a_item y self.b_item.

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

Answer 1

El primer problema es este patrón:

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

Después de la primera línea y antes de la segunda línea. self.b_item se mueve hacia afuera, haciendo un "agujero" en self (incluso si lo olvidamos) self es un puntero prestado y no puedes salir de él).Esto no esta permitido.Para expresar tal patrón hay una función especial en std::mem, llamado replace.

El segundo y principal problema es que A no se puede copiar implícitamente, por lo que cuando intenta hacer coincidir valores de tipo Option<A>, estos valores se mueven hacia afuera, pero saliendo desde el interior de &/&mut El puntero está prohibido.La única forma de evitar esto es hacer coincidir las referencias.Pero entonces debes tener cuidado, porque las reglas de préstamo solo te permiten tener un préstamo mutable a la vez.Entonces hay que organizar una especie de "flujo" de referencias a self.a_item y self.b_item a través de la declaración de coincidencia, utilizando enlaces de patrones.

El siguiente código se compila.También puedes reemplazar result variables y Some() uso en el cuerpo de match directamente con mem::replace() llamadas, pero pensé que separar la selección de valores y mem::replace() llame a hacer que el código sea más limpio.Además no pude usar Some(x) y Some(y) patrones en el último match brazo porque las referencias mismas se mueven a a_item y 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

Esta solución funcionará con Rust 1.2 y probablemente con Rust 1.x.

En lugar de mantener el nuestro Option de artículos, opté por usar el peekable Adaptador iterador.Esto nos permite mirar hacia adelante un elemento, sin perderlo.

También rompí el Iterator::next método en dos partes: una que determina de qué lado tirar y otra que realmente hace avanzar ese iterador.

También hay actualizaciones generales sobre cómo se definen ahora los iteradores con tipos asociados.

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