I'm trying to implement a trie but the borrow checker is really giving me a hard time:
struct Node {
// a trie node
value: char,
children: Vec<Node>,
}
impl Node {
fn add_child(&mut self, value: char) -> &mut Node {
// adds a child to given node
let vec: Vec<Node> = Vec::new();
let node = Node {
value,
children: vec,
};
self.children.push(node);
self.children.last_mut().unwrap()
}
fn get_child(&mut self, value: char) -> Option<&mut Node> {
// checks if given node has a child with given value, returns the child if it exists
for child in self.children.iter_mut() {
if child.value == value {
return Some(child);
}
}
None
}
fn has_child(&self, value: char) -> bool {
for child in self.children.iter() {
if child.value == value {
return true;
}
}
false
}
fn add_word(&mut self, word: String) {
let mut cursor = self;
for c in word.chars() {
match cursor.get_child(c) {
Some(node) => cursor = node,
None => cursor = cursor.add_child(c),
}
}
cursor.add_child('~');
}
}
The add_word method gives these 5 errors:
error[E0499]: cannot borrow `*cursor` as mutable more than once at a time
--> src/main.rs:41:19
|
41 | match cursor.get_child(c) {
| ^^^^^^ mutable borrow starts here in previous iteration of loop
...
47 | }
| - mutable borrow ends here
error[E0506]: cannot assign to `cursor` because it is borrowed
--> src/main.rs:42:31
|
41 | match cursor.get_child(c) {
| ------ borrow of `cursor` occurs here
42 | Some(node) => cursor = node,
| ^^^^^^^^^^^^^ assignment to borrowed `cursor` occurs here
error[E0506]: cannot assign to `cursor` because it is borrowed
--> src/main.rs:43:25
|
41 | match cursor.get_child(c) {
| ------ borrow of `cursor` occurs here
42 | Some(node) => cursor = node,
43 | None => cursor = cursor.add_child(c),
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `cursor` occurs here
error[E0499]: cannot borrow `*cursor` as mutable more than once at a time
--> src/main.rs:43:34
|
41 | match cursor.get_child(c) {
| ------ first mutable borrow occurs here
42 | Some(node) => cursor = node,
43 | None => cursor = cursor.add_child(c),
| ^^^^^^ second mutable borrow occurs here
...
47 | }
| - first borrow ends here
error[E0499]: cannot borrow `*cursor` as mutable more than once at a time
--> src/main.rs:46:9
|
41 | match cursor.get_child(c) {
| ------ first mutable borrow occurs here
...
46 | cursor.add_child('~');
| ^^^^^^ second mutable borrow occurs here
47 | }
| - first borrow ends here
This is the Go code that I was trying to translate:
func (n *trieNode) AddWord(word string) {
cursor := n
for i := 0; i < len(word); i++ {
if cursor.HasChild(byte(word[i])) == nil {
cursor = cursor.AddChild(byte(word[i]))
} else {
cursor = cursor.HasChild(byte(word[i]))
}
}
// tilde indicates the end of the word
cursor.AddChild(byte('~'))
}
