0

I have the following code:

struct Node{
    node_map: HashMap<char, Node>,
    value: Option<i32>,
}

struct Trie {
    root: Node,
}

impl Trie {
    fn new() -> Trie {
        Trie {
            root: Node{
                node_map: HashMap::new(),
                value: None,
            },
        }
    }

    fn find(&self, key: &String) -> Option<&Node> {
       // Returning some Option<&Node>
    }

    fn delete(&mut self, key: &String) -> Option<i32> {
        // extract code snippet
        let mut search_node = self.find(key);
        if search_node.is_some() {
            search_node.unwrap().node_map.remove(& 'x');
        }
        None
    }
}

Rust complains the error under search_node.unwrap().chs part: cannot borrow data in a "&" reference as mutable

So I understand that the find function returns Option<&Node> so when unwrapping at the above line, I get the reference to Node.

Attempts:

  • I tried to dereference the node by: *search_node.unwrap().node_map.remove(& 'x'); or *(search_node.unwrap()).node_map.remove(& 'x'); but it still throws error.
  • I followed another answer here and tried to make node_map mutable like:
 struct Node<'a> {
     node_map: &'a mut HashMap<char, Node<'a>>,
     value: Option<i32>,
 }

But then I got complain about lacking lifetime several places. One particular place I dont know how to add is in the new function.

Please let me know how to solve the original issue or how to add the appropriate lifetime.

hydradon
  • 1,316
  • 1
  • 21
  • 52

1 Answers1

1

The problem is that find returns an (optional) immutable reference, but then you try to mutate it later. For that reason, you'll probably want to add a method find_mut with signature

fn find_mut(&mut self, key: &str) -> Option<&mut Node>

(I changed the key argument to &str because it's discouraged to take &String as an argument)

Another stylistic thing: you should use if let instead of checking that search_node is some and then unwrapping.

if let Some(search_node) = self.find_mut(key) {
    search_node.node_map.remove(&'x');
}
SCappella
  • 9,534
  • 1
  • 26
  • 35
  • HI @SCappella, I tried your method and implement `find_mut`, but I got some other reference issue: could you check my code here at PlayGround: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1a333f353aa91643b8f5d493c02785d0 – hydradon Oct 17 '19 at 03:34
  • 1
    @hydradon Your main problem is the line `let mut search_node = &self.root;`. Remember, if you start with an immutable reference, you won't be able to take a mutable reference later on. You'll also have to use `HashMap`'s `get_mut` method to ensure that the later `search_node`s are also mutable. – SCappella Oct 17 '19 at 03:53
  • 1
    @hydradon I'll also warn you about using unwrap. As written, the code will panic whenever a key doesn't exist in the trie. I'd probably rewrite that using the [`?` operator](https://doc.rust-lang.org/edition-guide/rust-2018/error-handling-and-panics/the-question-mark-operator-for-easier-error-handling.html) as `search_node = search_node.node_map.get_mut(&c)?;`. – SCappella Oct 17 '19 at 03:53
  • 1
    @hydradon Just so we're clear, `let mut search_node = &self.root;` is not a mutable reference, but rather a reference that is mutable. That is, the pointer itself can be changed, but not the underlying data. What you want is `let search_node = &mut self.root;`. – SCappella Oct 17 '19 at 03:55
  • I have made your suggested change: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=5f46673c83a6b5863deb86ffe7b6cb46 Now it complains `cannot assign twice to immutable variable search_node`. Also, since at the end, it returns `Some(search_node)` is inconsistent with `-> Option<&mut Node>` . How do I fix this return? – hydradon Oct 17 '19 at 04:19
  • 1
    @hydradon Oh yeah, I guess you do still need to change the reference itself as well as its data, so `let mut search_node = &mut self.root;` is appropriate. – SCappella Oct 17 '19 at 04:24