Access values in a nested nested structure
I am new to Rust and want to implement an AVL tree.
I am using the following enum to represent my tree:
enum AvlTree<T> {
Leaf,
Node {
left: Box<AvlTree<T>>,
right: Box<AvlTree<T>>,
value: T
}
}
When implementing one of the balance functions, I run into some ownership and borrowing issues.
I am trying to write a function that takes AvlTree<T>
and returns another AvlTree<T>
. My first attempt was something like this:
fn balance_ll(tree: AvlTree<T>) -> AvlTree<T> {
if let AvlTree::Node {left: t, right: u, value: v} = tree {
if let AvlTree::Node {left: ref tl, right: ref ul, value: ref vl} = *t {
AvlTree::Leaf // Return a new AvlTree here
} else {
tree
}
} else {
tree
}
}
Even in this minimal example, the compiler returns an error:
error[E0382]: use of partially moved value: `tree`
--> avl.rs:67:17
|
63 | if let AvlTree::Node {left: t, right: u, value: v} = tree {
| - value moved here
...
67 | tree
| ^^^^ value used here after move
|
= note: move occurs because `(tree:AvlTree::Node).left` has type `std::boxed::Box<AvlTree<T>>`, which does not implement the `Copy` trait
I think I am understanding the error message correctly, since destructuring AvlTree::Node
will result in the grabbing of ownership of the example tree. How can I prevent this? I've tried different things already and (de-) referenced tree
-variable just to encounter more errors.
Also, I want to use some of the extracted values like u
, tl
and vl
in a new structure. Is this possible and could you provide a minimal example that does exactly this? I don't need access to the old tree after the function has been executed.
source to share
I think I understood the error message correctly, since destructuring
AvlTree::Node
would result in the grabbing of ownership of the example tree.
Yes. If you still need to use tree
after this, you will need to make a copy of it:
#[derive(Clone)]
enum AvlTree<T> {...}
fn balance_ll<T: Clone>(tree: AvlTree<T>) -> AvlTree<T> {
let copy = tree.clone();
if let AvlTree::Node { left: t, right: u, value: v } = tree {
if let AvlTree::Node { left: ref tl, right: ref ul, value: ref vl } = *t {
AvlTree::Leaf // Return a new AvlTree here
} else {
copy
}
} else {
tree
}
}
or use a helper function that frees up its property quickly, but I don't think this is possible without the box templates:
#![feature(box_patterns)]
impl<T> AvlTree<T> {
fn is_left_node(&self) -> bool {
if let &AvlTree::Node { left: ref t, right: ref u, value: ref v } = self {
if let &box AvlTree::Node { left: ref tl, right: ref ul, value: ref vl } = t {
true
} else {
false
}
} else {
false
}
}
}
fn balance_ll<T>(tree: AvlTree<T>) -> AvlTree<T> {
if tree.is_left_node() {
AvlTree::Leaf
} else {
tree
}
}
Since you might want to use destructive values, you will probably prefer an option clone
, but maybe another will give you additional ideas.
source to share