Iterating forward and backward

Question

We have a double ended list of structs, e.g. LinkedList.

I need to iterate forward and backward through the elements (like, 4 times forward then 2 times backward then 5 times forward).

In C++ it would be:

iter++; iter++; ... iter--; ...

In Rust, I only see .next() and .rev() which is inconvenient (since after a few iterations I already do not know in which direction I've reversed iteration).

Answer 1

Iterator is similar to ForwardIterator of C++. What you want is a BidirectionalIterator, but Rust does not provide a trait similar to it because of a limitation in the type system.

As Matthieu M said in comments, the way an iterator is defined allows a reference to the yielded element to be kept. And that's a problem if the iterator produces mutable references, because moving forward and backward would allow multiples mutable references to the same element. One way to solve this problem would be to tie the lifetime of the yielded element with &mut self, so a call to next (or prev) would borrow self, but there is no way of doing it in a generic way (there is a RFC to add such capability).

Looking the Iterator trait definition:

pub trait Iterator {
    type Item;
    fn next<'a>(&'a mut self) -> Option<Self::Item>;
    // ...
}

we can see that the lifetime of Self::Item is independent of 'a. What is necessary to solve the problem is:

pub trait Iterator {
    type Item<'a>; // hypothetical syntax
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
    // ...
}

but that is not supported yet.

---

That said, one option is to use a external crate that use a specific iterator (that is, do not implement a trait). The linked_list crate provides a linked list implementation with Cursor, that allows forward and backward iteration:

use linked_list::LinkedList;
use std::iter::FromIterator;

fn main() {
    // LinkedList::cursor takes &mut self, so lst must be mutable
    let mut lst = LinkedList::from_iter(0..10);
    let mut c = lst.cursor();

    c.next();
    c.next();
    c.next();
    c.prev();

    assert_eq!(1, *c.prev().unwrap());
}

Cursor does not allow a reference to the yielded element to be kept. The docs says:

A Cursor is like an iterator, except that it can freely seek back-and-forth, and can safely mutate the list during iteration. This is because the lifetime of its yielded references is tied to its own lifetime, instead of just the underlying list. This means cursors cannot yield multiple elements at once.

The following example:

let a = c.next();
let b = c.next();

generates this error:

error: cannot borrow `c` as mutable more than once at a time [E0499]
    let b = c.next();

This happens because next (and prev) borrows from self, that is:

fn next<'a>(&'a mut self) -> Option<&'a mut T>

Answer 2

You'll need to implement your own iterator to do this. Here's a sample implementation of one for Vecs:

pub trait ForwardBackwardIterator : Iterator {
    fn prev(&mut self) -> Option<Self::Item>;
}

pub struct VectorForwardBackwardIterator<'a, Item> where Item : 'a {
    index: Option<usize>,
    vector: &'a Vec<Item>,
}

impl<'a, Item> VectorForwardBackwardIterator<'a, Item> {
    fn new(vector: &'a Vec<Item>) -> VectorForwardBackwardIterator<'a, Item> {
        VectorForwardBackwardIterator { index: None, vector: vector }
    }
}

impl<'a, Item> Iterator for VectorForwardBackwardIterator<'a, Item> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<&'a Item> {
        let index = 
            match self.index {
                Some(i) => i + 1,
                None => 0
            };

        self.index = Some(index);
        self.vector.get(index)
    }
}

impl<'a, Item> ForwardBackwardIterator for VectorForwardBackwardIterator<'a, Item> {
    fn prev(&mut self) -> Option<&'a Item> {
        let index = 
            match self.index {
                Some(0) | None => return None,
                Some(i) => i - 1
            };

        self.index = Some(index);
        self.vector.get(index)
    }
}

fn main() {
    let v = vec![0, 1, 2, 3, 4, 5];
    let mut iterator = VectorForwardBackwardIterator::new(&v);

    println!("{:?}", iterator.next());
    println!("{:?}", iterator.next());
    println!("{:?}", iterator.next());
    println!("{:?}", iterator.prev());
    println!("{:?}", iterator.prev());
}

This prints out

Some(0)
Some(1)
Some(2)
Some(1)
Some(0)