Rustでカスタムイテレータを実装する際の無限ループ

Question

リストzipperを実装しようとしています。これまでのところ私が持っている：

#[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 
    } 
} 

私は今、これは理にかなって私の頭では、イテレータ

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

を実装しようとしています。 ListZipperを反復するときは、leftを繰り返し、次にfocusを、さらにrightを反復したいとします。だから私はそれらの反復子を連鎖し、ちょうどnext()を返します。

これは、ListZipperのすべてのフィールドが空の場合に問題ありません。 1つが空でないとすぐにListZipperを反復すると、無限ループになります。

問題はチェーンではありません。私がそれを例えばに置き換えると。 self.left.iter()、およびleftが空でない場合、問題は同じです。同様にfocusおよびrightについても同様である。

イテレータのすべての要素を印刷しようとしましたが、これは前面から背面に向かってVecDequeを通過しているように見えます。私。 next()は、カーソルが背面に到達したときにカーソルを前進させません。

なぜですか？

私はListZipper自身がイテレータであることを望んでいないかもしれないが、それは別の議論です。

Answer 1

コメントに記載されているとおり、イテレータには重大な状態がありません：反復ではどれくらいまでですかです。 nextを呼び出すたびに、最初から完全に別のイテレータを構築し、最初の要素を取得します。私はListZipper自身がイテレータであることを望まない場合があり実現

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

、それはまた別の議論です：

はここで減少した例です。

いいえ、それは本当に^ _ ^ではありません。反復されているものを何らかの形で変更して、後続の呼び出しごとに異なる値を持つようにする必要があります。

既存のイテレーターとイテレーターアダプターの組み合わせを戻したい場合は、Correct way to return an Iterator?を参照してください。

そうでない場合、あなたは何とかnextの呼び出し中にListZipperを変更する必要があります。

より簡潔

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

：あなたのPartialEq実装が同じであるように思わ

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

---

注意自動的に派生したもの...

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