Reorganize items in a box inside a structure
I'm trying to implement rotation code for a balanced (AVL) version of a binary search tree in Rust, but I'm having trouble claiming ownership of the nodes being refactored.
My structure:
struct Tree<T> {
root: Box<TreeNode<T>>,
depth: usize,
}
enum TreeNode<T> {
Empty,
Node {
val: T,
left: Tree<T>,
right: Tree<T>,
},
}
I know I can only use one type, or Option
s. It seemed a little nicer.
When I want to implement pivot:
T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2
I cannot find a way to remap the nodes. I have a method rotate(&mut self, ...)
that I call z
node ( Tree<T>
node), but I need to use match *self.root {}
to cast the root TreeNode
to its version Node
in order to get the components. This works, but I cannot use those extracted values to create a new node.
If I try this:
fn insert(&mut self, ...) {
...
// need to rotate
rotate(self, ...);
}
fn rotate(&mut ztree, ...) {
ztree.root = match *ztree.root {
// just re assign same tree to test...
TreeNode::Node {val, left, right} =>
Box::new(TreeNode::Node {val: val, left: left, right: right}),
_ => panic!("meh"),
} ...
I am getting this error.
| 171 | ztree.root = match *ztree.root { | ^^^^^ cannot move out of borrowed content 172 | TreeNode::Node {val, left, right} => | --- ---- ----- ...and here (use `ref right` or `ref mut right`) | | | | | ...and here (use `ref left` or `ref mut left`) | hint: to prevent move, use `ref val` or `ref mut val`
I realize that I don’t like it when I get the ownership of a box TreeNode
, but I don’t know how to tell Rust that I’m going to assign a new box TreeNode
and the old one TreeNode
can be declared locally.
If I try self.root = Box::new(TreeNode::Empty)
that works fine because it knows that I am reassigning self.root
to a new field and the previous field and the heap struct reference should be freed.
source to share
Let's assume Rust trusted you to replace the value ztree.root
. Then you can write
fn rotate(&mut ztree, ...) {
let locally_owned = ztree.root (and I promise to give it back);
// Now, ztree.root is in some undefined state.
// Thats OK though, because I promise to fix it before anyone looks!
let local_new_value = match locally_owned {
// just re assign same tree to test...
TreeNode::Node {val, left, right} =>
Box::new(TreeNode::Node {val: val, left: left, right: right}),
// Looks safe-ish, because the whole program will crash,
// so the programmer might expect that no one
// will see the undefined value of ztree.root
// (in fact, there would be problems when the destructor
// of ztree.root is called in the panic)
_ => panic!("meh"),
}
// FIXED IT! Put a value back into ztree.root
ztree.root = local_new_value;
}
which looks like OK. However, imagine if you replaced panic("meh")
with some return statement. Then you might have code like this:
ztree.root = Box::new(TreeNode::Empty);
// Returns without replacing the value of ztree.root
// because ztree.root is Empty
rotate(&mut ztree);
// Now ztree.root is in a undefined state
rotate(&mut ztree); // So something bad happens here
Basically, the compiler would have to make sure that not only are you intending to replace the value ztree.root
, but that there is no code path that would result in the value not being replaced. This is a way to complicate things, and for this reason there is no way to tell the compiler to let you do what you are trying to do.
Instead, you can fix your problem by repeating it. Instead of trying to compute a new value to replace the old value, you just need to change the current value without replacing it. One way to do it is to use std::mem::swap
this ( Playground ):
fn rotate<T>(ztree: &mut Tree<T>) { let ref mut root : TreeNode<T> = *ztree.root; match root { &mut TreeNode::Node {ref mut left, ref mut right, ..} => { std::mem::swap(left, right); }, _ => unimplemented!(), } }
If you are wondering why it let ref mut root: TreeNode<T> = *ztree.root;
works but match *ztree.root {...}
not, I'm not sure, but it is probably related to this question .
source to share