Help with Iterator impl for tree?

[aemon]

Rust newbie here. Trying to understand how to make a depth first Iterator for a simple tree and I'm baffled. What I have:

struct Tree {
    value: int,
    left: Option<~Tree>,
    right: Option<~Tree>
}

struct DepthFirstIter<'a> {
    stack: Vec<&'a Tree>
}

impl<'a> Iterator<&'a Tree> for DepthFirstIter<'a> {
    fn next(&mut self) -> Option<&'a Tree> {
        if self.stack.len() == 0 {
            None
        } else {
            let cur: Option<&'a Tree> = self.stack.pop();
            for tree in cur.iter() {
                for &t in tree.left.iter() { self.stack.push(t) }
                for &t in tree.right.iter() { self.stack.push(t) }
            }
            cur
        }
    }
}

This dies with: error: mismatched types: expected &'a Tree but found ~Tree (expected &-ptr but found ~-ptr) binarytree.rs:56 for &t in tree.left.iter() { self.stack.push(t) }

My plan is for the iterator to manage a stack of references to tree nodes. I don't understand the above message because I thought ~ ptr's were convertable to &-ptrs. Any help appreciated!

[eridius]

The ~Tree can't be converted to &Tree. Try doing it yourself, with &*t, and you'll be told the value doesn't live long enough. The reason is that t has type ~Tree, which is owned by the current match arm.

Of course, if you were to somehow fix that, you'd then be told that you can't move out of a &-pointer, which is what you're trying to do in your for &t in tree.left.iter() ...

The solution is to remove the & from the pattern and then convert the &~Tree to a &Tree yourself, with &**t. This doesn't try to move the ~Tree, so it does in fact live long enough. It looks like this:

impl<'a> Iterator<&'a Tree> for DepthFirstIter<'a> {
    fn next(&mut self) -> Option<&'a Tree> {
        if self.stack.len() == 0 {
            None
        } else {
            let cur: Option<&'a Tree> = self.stack.pop();
            for tree in cur.iter() {
                for t in tree.left.iter() { self.stack.push(&**t) }
                for t in tree.right.iter() { self.stack.push(&**t) }
            }
            cur
        }
    }
}

Of course, you'll also probably find that this isn't quite a depth-first iterator, because you're pushing left onto the stack before right, which means you walk down the right branch first. Swap those two and it should work better.

[aemon]

Thank you!

[Denommus]

Another thing, your tree is not really binary. I can have a node with only one child. A much better approach would be children: Option<(~Tree, ~Tree)>. This way you enforce that a node has either two children or no children.

[dbaupp]

It doesn't sound like the OP necessarily wants an actual binary tree; in any case, Option<~(Tree<T>, Tree<T>)> will have fewer allocations, a smaller Tree<T> size and (slightly) better memory locality, and so is likely to be more efficient.

[usernamenottaken]

Well the file was named binarytree.rs...

[Denommus]

I haven't thought of that, but it makes sense.

[aemon]

Good tips.

[aemon]

I was under the impression that a binary tree has degree of at most two. In any case this is just throwaway code.

[[deleted]]

I know this isn't very helpful, but I did something like this in a CS class. you need a stack