Unendlich Schleife bei der Implementierung von benutzerdefinierten Iterator in Rust

Question

Ich versuche, eine Liste zipper zu implementieren. Bisher habe ich:

#[derive(RustcDecodable, RustcEncodable, Debug, Clone)] 
pub struct ListZipper { 
    pub focus: Option<Tile>, 
    pub left: VecDeque<Tile>, 
    pub right: VecDeque<Tile>, 
} 

impl PartialEq for ListZipper { 
    fn eq(&self, other: &ListZipper) -> bool { 
     self.left == other.left && self.focus == other.focus && self.right == other.right 
    } 
} 

ich jetzt versuchen, einen Iterator zu implementieren

impl Iterator for ListZipper { 
    type Item = Tile; 

    fn next(&mut self) -> Option<Tile> { 
     self.left.iter().chain(self.focus.iter()).chain(self.right.iter()).next().map(|w| *w)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
    } 
} 

In meinem Kopf das macht Sinn. Wenn ich über ListZipper iteriere, möchte ich über left, dann focus und dann right iterieren. Also kette ich diese Iteratoren und gebe einfach next() zurück.

Dies funktioniert, wenn alle Felder in ListZipper leer sind. Sobald man nicht leer ist, führt die Iteration über ListZipper zu einer Endlosschleife.

Das Problem ist nicht die Kette. Wenn ich das durch z.B. self.left.iter() und left ist nicht leer, das Problem ist das gleiche. Ebenso für focus und right.

Ich habe versucht, alle Elemente im Iterator zu drucken und es scheint durch die VecDeque von vorne nach hinten gehen, und dann bleibt stecken. I.e. next() bewegt den Cursor nicht weiter, wenn er die Rückseite erreicht.

Warum?

Ich weiß, ich möchte nicht ListZipper selbst ein Iterator sein, aber das ist eine andere Diskussion.

Answer 1

Wie in den Kommentaren erwähnt, fehlt Ihrem Iterator ein entscheidender Status: Wie weit in der Iteration ist es. Jedes Mal, wenn Sie next aufrufen, baut es einen anderen Iterator vollständig von Grund auf und ruft das erste Element ab.

Hier ist ein reduzierter Beispiel:

struct ListZipper { 
    focus: Option<u8>, 
} 

impl Iterator for ListZipper { 
    type Item = u8; 

    fn next(&mut self) -> Option<Self::Item> { 
     self.focus.iter().next().cloned() 
    } 
} 

fn main() { 
    let lz = ListZipper { focus: Some(42) }; 
    let head: Vec<_> = lz.take(5).collect(); 
    println!("{:?}", head); // [42, 42, 42, 42, 42] 
} 

Ich weiß, ich nicht ListZipper möchte kann sich ein Iterator sein, aber das ist eine andere Diskussion.

Nein, es ist wirklich nicht^_ ^. Sie müssen das zu iterierende Objekt irgendwie mutieren, damit es sich ändern kann und für jeden nachfolgenden Aufruf andere Werte haben kann.

Wenn Sie eine Kombination aus vorhandenen Iteratoren und Iteratoradaptern zurückgeben möchten, finden Sie Anweisungen unter Correct way to return an Iterator?.

Andernfalls müssen Sie irgendwie ListZipper zu next während des Gesprächs ändern:

impl Iterator for ListZipper { 
    type Item = Tile; 

    fn next(&mut self) -> Option<Self::Item> { 
     if let Some(v) = self.left.pop_front() { 
      return Some(v); 
     } 

     if let Some(v) = self.focus.take() { 
      return Some(v); 
     } 

     if let Some(v) = self.right.pop_front() { 
      return Some(v); 
     } 

     None 
    } 
} 

kurz und bündig:

impl Iterator for ListZipper { 
    type Item = Tile; 

    fn next(&mut self) -> Option<Self::Item> { 
     self.left.pop_front() 
      .or_else(|| self.focus.take()) 
      .or_else(|| self.right.pop_front()) 
    } 
} 

---

Beachten Sie, dass Ihre PartialEq Umsetzung das gleiche wie das zu sein scheint automatisch abgeleitetes ...

use std::collections::VecDeque; 

type Tile = u8; 

#[derive(Debug, Clone, PartialEq)] 
pub struct ListZipper { 
    pub focus: Option<Tile>, 
    pub left: VecDeque<Tile>, 
    pub right: VecDeque<Tile>, 
} 

impl Iterator for ListZipper { 
    type Item = Tile; 

    fn next(&mut self) -> Option<Self::Item> { 
     self.left.pop_front() 
      .or_else(|| self.focus.take()) 
      .or_else(|| self.right.pop_front()) 
    } 
} 

fn main() { 
    let lz = ListZipper { 
     focus: Some(42), 
     left: vec![1, 2, 3].into(), 
     right: vec![97, 98, 99].into(), 
    }; 

    let head: Vec<_> = lz.take(5).collect(); 

    println!("{:?}", head); 
}