CODEWITHSUNDEEP
rust
Ed Behn
Ed Behn

Reputation: 460

How do I get values in a HashMap to reference each other?

I'm trying to teach myself Rust by writing a compiler for COOL.

I have a HashMap that stores multiple nodes by name. I also want each node to refer to its parent node if it has one. This way I am able both to find a node by name or navigate the tree from child to parent in constant time.

In this example, I want the node named B to reference A

#![allow(unused_variables)]
#![allow(dead_code)]

use std::collections::HashMap;

struct Node {
    name: String,
    parent_name: Option<String>,
    parent: Option<&'static Node>, // I'm not sure this is the correct lifetime
}

fn main() {
    let mut hm: HashMap<String, Node> = HashMap::new();

    hm.insert(
        "A".to_string(),
        Node {
            name: "A".to_string(),
            parent_name: None,
            parent: None,
        },
    );

    hm.insert(
        "B".to_string(),
        Node {
            name: "B".to_string(),
            parent_name: Some("A".to_string()),
            parent: None,
        },
    );

    // ---------------
    // This is where things go awry.

    let a: &Node = hm.get(&"A".to_string()).unwrap();
    let b: &mut Node = hm.get_mut(&"B".to_string()).unwrap();
    
    b.parent = Some(a);
}

No matter how I change the code I get a error based on multiple references and/or lifetime issues. Is there a way to do this in Rust?

Upvotes: 0

Views: 917

Answers (1)

WinterCicada
WinterCicada

Reputation: 96

You can use Rc to let the parent node own by both HashMap and child node, and use RefCell to allow you to mutate the data of immutable reference so that you don't have to borrow hm as mutable and immutable at the same time.

#![allow(unused_variables)]
#![allow(dead_code)]

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    name: String,
    parent_name: Option<String>,
    parent: Option<Rc<RefCell<Node>>>, // use Rc to enable multiple ownership
}

fn main() {
    let mut hm: HashMap<String, Rc<RefCell<Node>>> = HashMap::new();

    hm.insert(
        "A".to_string(),
        Rc::new(RefCell::new(Node {
            name: "A".to_string(),
            parent_name: None,
            parent: None,
        })),
    );

    hm.insert(
        "B".to_string(),
        Rc::new(RefCell::new(Node {
            name: "B".to_string(),
            parent_name: Some("A".to_string()),
            parent: None,
        })),
    );



    let a: &Rc<RefCell<Node>> = hm.get(&"A".to_string()).unwrap();
    let b: &Rc<RefCell<Node>> = hm.get(&"B".to_string()).unwrap();  
    // Can't borrow hm as mutable and immutable at the same time
    // use RefCell to mutate data even when there are immutable references to that data
    
    b.borrow_mut().parent = Some(Rc::clone(a));
}

Upvotes: 1

Related Questions