Implementing iterator on a nested RefCell, is it possible?

help
1

So i'm trying out to build a tree data structure in rust and i find it difficult to wrap my head around how to implement the IntoIterator trait.

I started our with using the example given here in the rust docs for Rc std::rc - Rust

I then started to try that wrap this structure in structs etc. So that i didn't have to work with Rc and RefCell etc directly.

It all went quite well until i needed to implement Iterator and IntoIterator for the children. I wanted to use a for loop to iterate over references and i have no idea how to write it.

this is my code:

#[derive(Debug, Default)]
struct Nodes(RefCell<Vec<Weak<NodeInner>>>);

impl Iterator for Nodes {
    type Item = Weak<NodeInner>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.borrow().into_iter().next()
    }
}

#[derive(Debug, Default)]
struct Node {
    inner: Rc<NodeInner>,
}

impl Node {
    fn new(parent: Option<Node>, children: Nodes, point: Point) -> Self {
        Self {
            inner: Rc::new(NodeInner {
                parent,
                children,
                point,
            }),
        }
    }

    fn from_inner(inner: Rc<NodeInner>) -> Node {
        Self { inner }
    }

    fn push(&self, node: &Node) {
        self.inner.children.0.borrow_mut().push(Rc::downgrade(node))
    }
}

impl Deref for Node {
    type Target = Rc<NodeInner>;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

impl Clone for Node {
    fn clone(&self) -> Self {
        Self {
            inner: Rc::clone(&self.inner),
        }
    }
}

#[derive(Debug, Default)]
struct Point {
    x: u32,
    y: u32,
}

#[derive(Debug, Default)]
struct NodeInner {
    parent: Option<Node>,
    children: Nodes,
    point: Point,
}

struct NodeBuilder {
    parent: Option<Node>,
    children: Nodes,
    point: Point,
}

impl NodeBuilder {
    fn new(point: Point) -> NodeBuilder {
        Self {
            parent: None,
            children: Nodes(RefCell::new(vec![])),
            point,
        }
    }

    fn with_parent(mut self, node: &Node) -> NodeBuilder {
        self.parent = Some(node.clone());
        self
    }

    fn build(self) -> Node {
        Node::new(self.parent, self.children, self.point)
    }
}

fn main() {
    let parent: Node = NodeBuilder::new(Point { x: 0, y: 0 }).build();

    let child_1: Node = NodeBuilder::new(Point { x: 1, y: 0 })
        .with_parent(&parent)
        .build();

    let child_2: Node = NodeBuilder::new(Point { x: 0, y: 1 })
        .with_parent(&parent)
        .build();

    parent.push(&child_1);
    parent.push(&child_2);

    // This doesnt work
    for child in &parent.children {
        println!("x: {}, y: {}", child.point.x, child.point.y);
    }
}

The example provided wraps the children in a Vec<T> that is placed in a RefCell<T>.

What i dont really get is:

  • Does IntoIterator consume the collection?
  • Do i need to implement Iterator and then use the Iter function when implementing IntoIterator
  • How do i implement Iter_mut?
  • Can you implement all of this if the collection is in a RefCell or do i actually need to owned values?
  • Is there any way to not return Weak<NodeInner> and instead pure Node?

im pretty confused here because the docs specifically just talks about the trait Iterator and just a simple nested Vec<T>

2

Your data structure looks like a tree. Have you read the section on using Box<T> in the rust programming language? Your example does not make it clear that you really need RefCell<T> or to store Weak references. Are you trying to implement some sort of cache?

Also consider re-reading the section on iterators as well as the std::iter module documentation.

1 Like
3

it is a tree structure but one of the requirments i wanted was to implement a tree that i can traverse both up and down. As i understand it this means i can't use Box<T> as this will give me circular references

I have read the section on iterators several times and there is very little information on how to actually implement IntoIterator as all i can see is that they just call into_iter on the nested Vec<T> and pass that along.

There is no implementation in the documentation on iter_mut.

I would gladly read the documentation if you you could please point me more accuratly to what parts i should read that will solve my problems.

4

When implemented directly on the collection, yes.

Often, it will also be implemented on (mutable) references to the collection, which then defer to iter(_mut). These implementations will consume the reference, but not the collection they point to.

You need to have some type that implements Iterator for IntoIterator to return. This is usually not the same iterator returned by an iter(&self) method.

It might not be possible in your case because of the shared ownership: Having exclusive access to the root doesn't necessarily mean that you'll be able to provide exclusive access to the various nodes in the tree.

RefCell makes thing a bit weird, but you should be able to make something work. You might need to yield std::cell::Ref<T> instead of &T, for example.

Given your definition of Node, you can just construct a new one:

Node { inner: weak_inner.try_upgrade().unwrap() }
1 Like
5

If you're having trouble traversing the tree in two directions, why don't you start with one?

Also, how are you planning to visit your tree? Breadth first or depth first? Can you sketch a tree and "iterate" over it?

Your statement is incorrect. Box<T> is a pointer to data allocated on the heap. It will not allow you to build circular references, Rc<T> will.

Have you implemented something like a count-down iterator? You should maybe do that as an exercise.

The documentation is quite clear. I think you're trying too many things at once which are making it difficult. We can help you take on these challenges one by one.

All of what I linked. It is okay if that takes you some time. Also, create some simpler exercises for yourself. Iterators first, then a linked list, then a tree, then a tree that supports multiple iteration strategies and backwards iteration.

6

Hierarchical RefCells are difficult to iterate in the canonical ways because you have to maintain the entire chain of ownership in the form of Refs. Consider internal iteration. Or you can perhaps collect a Vec<Ref<_>> first (but then you lose out on some of the benefits of iteration).

See this recentish thread and also this chapter of Too Many Linked Lists.

2 Likes
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.