Dealing with the borrower
I am new to Rust. As an educational exercise, I am trying to create a basic binary tree. This is what I have so far:
fn main() {
let data = vec![6,1,2,3,4,5];
let mut root = Node::<i32> { value: data[0], left: None, right: None };
for val in data {
createAndInsert::<i32>(&root, val);
}
println!("Root value: {}", root.value);
}
fn createAndInsert<T: PartialOrd>(mut root: &Node<T>, value: T) {
let mut n = Node::<T> { value: value, left: None, right: None };
insert::<T>(&root, &n);
}
fn insert<T: PartialOrd>(mut curr: &Node<T>, new: &Node<T>) {
if new.value > curr.value {
match curr.right {
Some(ref n) => insert(n, new),
None => curr.right = Some(Box::new(*new))
}
} else {
match curr.left {
Some(ref n) => insert(n, new),
None => curr.left = Some(Box::new(*new))
}
}
}
struct Node<T: PartialOrd> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
Compiler errors I am getting:
test.rs:21:48: 21:52 error: cannot move out of borrowed content
test.rs:21 None => curr.right = Some(Box::new(*new))
^~~~
test.rs:26:47: 26:51 error: cannot move out of borrowed content
test.rs:26 None => curr.left = Some(Box::new(*new))
^~~~
test.rs:21:21: 21:54 error: cannot assign to immutable field `curr.right`
test.rs:21 None => curr.right = Some(Box::new(*new))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.rs:26:21: 26:53 error: cannot assign to immutable field `curr.left`
test.rs:26 None => curr.left = Some(Box::new(*new))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 4 previous errors
I myself am confused about all the refs and muts and and, and * and I am not sure how to exit. Where am I going wrong?
source to share
You have two problems:
-
Unable to get out of borrowed context: see Unable to get out of borrowed content when borrowing a generic type for an explanation.
-
You cannot assign an immutable field: you only have
&Node<T>
; to changeNode
you need&mut Node<T>
.mut curr
in the template just makes the binding mutable, which means you can assign a new valuecurr
. However, you cannot change the content that is linked tocurr
. Spread the&
-to- conversion&mut
throughout your code and it works.
source to share
Since you are new to Rust, it might help to see how I would write this:
struct Node<T> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(x: T) -> Node<T> {
Node { value: x, left: None, right: None }
}
fn boxed(x: T) -> Box<Node<T>> {
Box::new(Node::new(x))
}
}
fn insert<T: PartialOrd>(root: &mut Option<Box<Node<T>>>, new: Box<Node<T>>) {
if let Some(ref mut rbx) = *root {
if new.value < rbx.value {
insert(&mut rbx.left, new);
} else {
insert(&mut rbx.right, new);
}
} else {
*root = Some(new);
}
}
fn main() {
let data = vec![6,1,2,3,4,5];
let mut root = None;
for val in data {
insert(&mut root, Node::boxed(val));
}
println!("Root value: {}", root.unwrap().value);
}
I realize this is more of an exercise, but keep in mind that this type of data structure must not exceed a certain depth of the tree, as it could otherwise overflow when the nodes are freed recursively.
source to share