Trie data structure: a problem of multiple mutable references

help
1

Trie data structure: a problem of multiple mutable references

Hi everyone, I'm trying to implement a Trie in rust but I'm stuck with this error:

error: cannot borrow `*self` as mutable more than once at a time

The problem lies in the insert funcion:

fn insert(&mut self, word: &str) {
    let word: Vec<_> = word.chars().collect(); // first mutable borrow
    let node: &mut TNode = &mut self.root; // first borrow later used here
    self.insert_rec(node, &word, 0);
}

After some research I found this example.
It shows a basic usage of Rc and RefCell, if possible I'd like to avoid that.

Here's the code (rust playground)

I managed to make it work with an iterative approach.
But I'd like to know how can I achieve the same with a recursive function (and why the borrow checker "breaks" inside recursive functions?).

fn insert_iter(&mut self, word: &str) {
    let word: Vec<_> = word.chars().collect();
    let mut node: &mut TNode = &mut self.root;

    for i in 0..word.len() {
        let current = word[i];
        if !node.children.contains_key(&current) {
            let is_end = i == word.len() - 1;
            node.children
                .insert(current, TNode::new(current, is_end, None));
        }

        node = node.children.get_mut(&current).unwrap();
    }
}
2

You can't call a method on &mut self whlie also passing a reference to &mut self.root, even if inside of the insert_rec function you don't use self.root.

There was some blog post about "lifetime view" types or something that could maybe help with this but I can't seem find it.

Can you extract the body of the insert_rec function into an associated function/standalone function that just takes the pieces it needs (and re-use it to define insert_rec for deduplication)?

1 Like
3

This one maybe.

3 Likes
4

Sure, here's the updated code. I ran some tests and this works.

fn insert(&mut self, word: &str) {
    let word: Vec<_> = word.chars().collect();
    let node: &mut TNode = &mut self.root;
    Trie::insert_rec(node, &word, 0);
}

fn insert_rec(n: &mut TNode, word: &[char], depth: usize) {
    if depth >= word.len() {
        return;
    }

    let current = word[depth];

    if !n.children.contains_key(&current) {
        let is_end = depth == word.len() - 1;
        n.children
            .insert(current, TNode::new(current, is_end, None));
    }

    if let Some(next_node) = n.children.get_mut(&current) {
        Trie::insert_rec(next_node, word, depth + 1);
    }
}
5

That's the one, thanks!

6

Here is your code refactored:

Playground

use std::collections::HashMap;

fn main() {
    let mut trie = Trie::new();
    trie.insert("kitty");
    println!("{:#?}", trie.root);
}

#[derive(Debug)]
pub struct TNode {
    pub value: char,
    pub is_end: bool,
    pub children: HashMap<char, TNode>,
}

impl TNode {
    pub fn new(value: char, is_end: bool) -> Self {
        Self {
            value,
            is_end,
            children: Default::default(),
        }
    }
}

pub struct Trie {
    pub root: TNode,
}

impl Trie {
    pub fn new() -> Self {
        Self {
            root: TNode::new('\0', false),
        }
    }

    fn insert(&mut self, word: &str) {
        let mut remainder = word.chars();
        if let Some(first) = remainder.next() {
            Self::insert_rec(&mut self.root, first, remainder);
        }
    }

    fn insert_rec(cur_node: &mut TNode, cur_char: char, mut remainder: std::str::Chars<'_>) {
        let next_char = remainder.next();
        let next_node = cur_node
            .children
            .entry(cur_char)
            .or_insert_with(|| TNode::new(cur_char, next_char.is_none()));
        if let Some(next_char) = next_char {
            Self::insert_rec(next_node, next_char, remainder);
        }
    }
}

I'm not sure I would keep the recursive implementation but it was good for learning.

1 Like
7

I'm leaving this here in case someone is looking for the complete Trie implementation

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.