Implement tree data structure

Question

I want to implement a tree data structure. I have a Node struct and want it to hold references to child Nodes. I tried:

use std::collections::*;

#[derive(Debug)]
struct Node {
    value: String,
    children: HashMap<String, Node>,
}


impl Node {
    fn new(value: String) -> Self {
        Node {
            value: value,
            children: HashMap::new(),
        }
    }

    fn add_child(&mut self, key: String, value: String) -> &mut Node {
        let mut node = Node::new(value);
        self.children.insert(key, node);
        &mut node
    }
}


fn main() {
    let mut root_node = Node::new("root".to_string());
    root_node.add_child("child_1_1".to_string(), "child_1_1_value".to_string());
}

This code does not compile:

error: `node` does not live long enough
  --> src/main.rs:22:10
   |
22 |     &mut node
   |          ^^^^ does not live long enough
23 |   }
   |   - borrowed value only lives until here
   |
note: borrowed value must be valid for the anonymous lifetime #1 defined on the body at 19:67...
  --> src/main.rs:19:68
   |
19 |     fn add_child(&mut self, key: String, value: String) -> &mut Node {
   |  ____________________________________________________________________^ starting here...
20 | |     let mut node = Node::new(value);
21 | |     self.children.insert(key, node);
22 | |     &mut node
23 | |   }
   | |___^ ...ending here

error[E0382]: use of moved value: `node`
  --> src/main.rs:22:10
   |
21 |     self.children.insert(key, node);
   |                               ---- value moved here
22 |     &mut node
   |          ^^^^ value used here after move
   |
   = note: move occurs because `node` has type `Node`, which does not implement the `Copy` trait

How can I implement this?

Answer 1

In this case, it's actually necessary to look at the second error message in the compiler output:

error[E0382]: use of moved value: `node`
  --> src/main.rs:22:10
   |
21 |     self.children.insert(key, node);
   |                               ---- value moved here
22 |     &mut node
   |          ^^^^ value used here after move
   |
   = note: move occurs because `node` has type `Node`, which does not implement the `Copy` trait

The variable node is moved into the hashmap in line 21. You can't use it afterwards! In Rust we have move semantics, meaning that everything gets moved by default instead of cloned by default (C++) or referenced by default (Java). You want to return a reference to the Node object inside the hashmap!

An easy way would be to insert node as you are already doing and afterwards fetching the value from the hashmap:

let mut node = Node::new(value);
self.children.insert(key.clone(), node);
self.children.get_mut(key).unwrap()

This should make clear what the function actually does. However, this code has some disadvantages: First, we have to clone key (we need it for the insertion and the query) and secondly, the hashmap needs calculate the hash of the key twice which is not very efficient.

Luckily, Rust's HashMap has a nice entry()-API. We could change the function like that:

self.children.entry(key).or_insert_with(|| Node::new(value))

This is the whole body of add_child()! Now, however, we notice that ... we haven't really thought about what is supposed to happen if the hashmap already contains a value associated with the given key! In the code above, the old value is kept and returned. If you want to do something else (e.g. replace the value), you could just use match on the Entry object:

let node = Node::new(value);
match self.children.entry(key) {
    Entry::Occupied(e) => {
        // Maybe you want to panic!() here... but we will just 
        // replace the value:
        e.insert(node);  // discarding old value...
        e.get_mut()
    }
    Entry::Vacant(e) => insert(node),
}