Infinite loop when implementing custom iterator in Rust

Question

I am trying to implement a list zipper. So far I have:

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

I am now trying to implement an iterator

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 my head this makes sense. When iterating over ListZipper, I want to iterate over left, then focus and then right. So I chain those iterators and just return next().

This works fine if all fields in ListZipper are empty. As soon as one is not empty iterating over ListZipper results in an infinite loop.

The problem is not the chain. If I replace that by e.g. self.left.iter(), and left is not empty, the problem is the same. Likewise for focus and right.

I tried printing all elements in the iterator and it appears to go through the VecDeque from front to back, and then gets stuck. I.e. next() does not advance the cursor when it reaches the back.

Why?

I realize I may not want ListZipper itself to be an iterator, but that is another discussion.

You do realize next is creating a whole new iterator every time it's called right? — mcarton
– mcarton, Commented Nov 28, 2016 at 17:53

Community · Accepted Answer · 2017-05-23 11:59:58Z

As mentioned in the comments, your iterator is lacking a crucial piece of state: how far along in the iteration it is. Every time you call next, it constructs another iterator completely from scratch and gets the first element.

Here's a reduced example:

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

I realize I may not want ListZipper itself to be an iterator, but that is another discussion.

No, it's really not ^_^. You need to somehow mutate the thing being iterated on so that it can change and have different values for each subsequent call.

If you want to return a combination of existing iterators and iterator adapters, refer to Correct way to return an Iterator? for instructions.

Otherwise, you need to somehow change ListZipper during the call to next:

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

More succinctly:

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

Note that your PartialEq implementation seems to be the same as the automatically-derived one...

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

Thank you so much for your elaborate answer. It's clear now. Thanks for the comment on PartialEq as well.

Collectives™ on Stack Overflow

Infinite loop when implementing custom iterator in Rust

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related