How to implement & mut iterator for binary search tree?

Question

I implemented a simple binary search tree in Rust (after CIS 198, this is great), and for training I do iterators that just run right edges.

I could not implement an iterator that gives mutable links. I tried many ways, but no one accepted the Rust compiler. The code I need help in is below ( while I did the gist with the full code here ):

#[derive(Debug)] pub struct Tree<T>(Option<Box<Node<T>>>); #[derive(Debug)] pub struct Node<T> { elem: T, left: Tree<T>, right: Tree<T>, } // MUTABLE BORROW STRUCT pub struct IterMut<'a, T: 'a> { next: &'a mut Tree<T>, } // MUTABLE BORROW NEXT (I'M STUCK HERE, NOTHING WORKS) impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { // 1 try: cannot infer lifetime self.next.0.as_mut().map(|node| { self.next = &mut node.right; &mut node.elem }) // 2 try: node.right, node.elem does not live long enough self.next.0.take().map(|node| { self.next = &mut node.right; &mut node.elem }) } } 

Answer 1

You need to change the type of the IterMut::next field to Option<&'a mut Node<T>> :

 pub struct IterMut<'a, T: 'a> { next: Option<&'a mut Node<T>>, } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| { self.next = node.right.0.as_mut().map(|node| &mut **node); &mut node.elem }) } } 

Here you can find more useful information about implementing a mutable iterator for recursive data structures: http://cglab.ca/~abeinges/blah/too-many-lists/book/second-iter-mut.html

Answer 2

I think you cannot split self into 2 mutable objects (one for Item , one for self ) without using any unsafe code.