Iterator for a recursive structure

help
#1

I want to implement a graceful iterator for a recursive structure like this:

#[derive(Debug)]
struct OneItem(u64);

#[derive(Debug)]
struct List {
    item: OneItem,
    prev: Option<Box<List>>,
}

and I want to return reference on one item inside my recusrive list such way:

impl<'a> Iterator for IterAdapter<'a> {

    type Item = &'a mut OneItem;

    fn next(&mut self) -> Option<Self::Item> {
        None
    }
}

My attempt has a failure:

struct IterAdapter<'a> {
    list: &'a mut List,
}

impl<'a> Iterator for IterAdapter<'a> {

    type Item = &'a mut OneItem;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(ref prev) = self.list.prev {
            self.list = &mut prev;
            return Some(&mut prev.item);
        }
        None
    }
}

Is it possible to do it with rust? If yes how can I do it?

#2

The usual link for this http://cglab.ca/~abeinges/blah/too-many-lists/book/second-iter-mut.html

2 Likes
#3

I did it such way:

#[derive(Debug)]
pub struct OneItem(u64);

#[derive(Debug)]
struct List {
    item: OneItem,
    prev: Option<Box<List>>,
}

impl<'a> IntoIterator for &'a List {
    type Item = &'a OneItem;
    type IntoIter = IterList<'a>;

    fn into_iter(self) -> Self::IntoIter {
        IterList { list: Some(self) }
    }
}

pub struct IterList<'a> {
    list: Option<&'a List>,
}

impl<'a> Iterator for IterList<'a> {
    type Item = &'a OneItem;

    fn next(&mut self) -> Option<Self::Item> {
        let ptr = self as *mut IterList;

        if let Some(ref list) = self.list {

            let item: Option<Self::Item> = Some(&list.item);

            if let Some(ref prev) = list.prev {
                unsafe {
                    (*ptr).list = Some(&**prev);
                }
            } else {
                unsafe {
                    (*ptr).list = None;
                }
            }

            return item;
        }

        None
    }
}
#4

Try to avoid the unsafes, in this case it is possible and it is a good exercise :slight_smile:

2 Likes
#5

Why not simply use Rust’s standard linked list and define your structure as LinkedList<OneItem>? Then you don’t bother writing iters.
If you don’t like extrusive collections, an alternative option is searching “intrusive” in crates.io.
If your recursive data structure is a tree, maybe you can use trees

1 Like
#6

@dodomorandi, you’re right. I fixed it, my next attempt to idealize code:

#[derive(Debug)]
pub struct OneItem(u64);

#[derive(Debug)]
struct List {
    item: OneItem,
    prev: Option<Box<List>>,
}

impl<'a> IntoIterator for &'a List {
    type Item = &'a OneItem;
    type IntoIter = IterList<'a>;

    fn into_iter(self) -> Self::IntoIter {
        IterList { list: Some(self) }
    }
}

pub struct IterList<'a> {
    list: Option<&'a List>,
}

impl<'a> Iterator for IterList<'a> {
    type Item = &'a OneItem;

    fn next(&mut self) -> Option<Self::Item> {
    
        let mut item: Option<Self::Item> = None;
        let mut prev_list: Option<&'a List> = None;

        if let Some(ref list) = self.list {

            item = Some(&list.item);

            if let Some(ref prev) = list.prev {
                prev_list = Some(&**prev);
            } else {
                prev_list = None;
            }
        }

        self.list = prev_list;

        item
    }
}

P.S.: I do it only for fun and study :blush:

2 Likes
#7

Nice!

If you want, try to go a step further: try to use the functions of Option to transform the content of next using a more functional approach. Hint: use map from Option, you won't need a single if.

I imagined that, I think it can be a good learning exercise :wink:

1 Like