I am trying to write a trie structure, which takes in a stream of characters and adds them onto the trie if it doesn't exist yet. When it adds a character, it returns to the top to start again.
#[derive(Debug)]
pub struct Trie {
char: u8,
children: [Option<Box<Self>>; 2],
}
impl Trie {
pub fn new(char: u8) -> Trie {
return Trie {
char,
children: [None, None],
};
}
pub fn push(&mut self, lz_pair: Trie) {
let idx = lz_pair.char as usize;
self.children[idx] = Some(Box::new(lz_pair));
}
pub fn get_child(&mut self, char: u8) -> Option<&mut Trie> {
let child = self.children[char as usize].as_mut();
if let Some(c) = child {
Some(c.as_mut())
} else {
None
}
}
}
fn main() {
let data = b"abbabababbbbbabaaaabababaa";
let mut root = Trie::new(0);
let mut cur = &mut root;
for c in data {
cur = match cur.get_child(*c) {
Some(child) => child,
None => {
cur.push(Trie::new(*c - 97));
&mut root
}
};
}
}
The actual code is a bit more complicated, but I distilled it down to just show this error.
The borrow checker complains:
error[E0499]: cannot borrow `*cur` as mutable more than once at a time
--> src/main.rs:40:17
|
37 | cur = match cur.get_child(*c) {
| --- first mutable borrow occurs here
...
40 | cur.push(Trie::new(*c - 97));
| ^^^
| |
| second mutable borrow occurs here
| first borrow used here, in later iteration of loop
I have read through all the questions here on the borrow checker errors when unwrapping Option
s (i.e. This question and all the duplicates), so I sort of understand why it happens, however I don't know how I can restructure this code to solve this particular case.
Non-lexical lifetimes don't seem to solve this problem as I am compiling using the 2018 version of Rust.