Accessing more than one mutable from a HashMap at same time?

[glennpierce]

I am trying to implement an algorithm that turns a flat structure into a nested tree. The algorithm I have used can be seen as the answer in the following question.

How to efficiently build a tree from a flat structure?

For completeness it is as follows in C#

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

I am having trouble with porting this to rust.

My version is at

Rust Playground

However, the children field is never filled on my version. I believe because
I need to get a mut ref to the proposed_parent and I am cloning.

ie line

let proposed_parent_option = lookup.get(&parent_ref).cloned();

but I cant get more than one mut ref into the HashMap.
Any ideas how to solved this should of issue in rust ?

Thanks

[H2CO3]

You can't get more than one mutable reference into the hash map. Maybe in the future a method could be added to it that would ensure the keys are distinct.

However, if you don't need both a parent and a child link, you can drop one of them and then you will only need one mutable ref at a time.

[cuviper]

If you switch to IndexMap, then you could lookup up the usize index of multiple keys at once with get_index_of(&key), and then it's cheap to use usize indexing to bounce around accessing those nodes for mutation.

[Phlopsi]

If you wrap the stored type with a Cell or RefCell, you can have several shared references into the HashMap and mutate the specific items through the cell-type.

[glennpierce]

Made some progress with dropping the value

Rust Playground

Output not quite what I would expect. Need to run the C# version to check.

[steffahn]

I don’t think you’ll ever want to clone a Node. Perhaps the easiest way to start fixing the program then is to remove the derive(Clone) from the Node. Instead rather want to share the same node in multiple places, so you should probably start using Rc<Node> earlier. The problem then however is that you cannot modify a Node anymore when it’s behind an Rc. The two possible ways to solve this are: Either use something like Rc<RefCell<Node>> or make the fields of Node itself use RefCell or Cell. Let’s take the former approach, but introduce a helpful type synonym NodeRef.

A last thing to keep in mind is that having parent and child pointers like this creates reference-cycles which will easily lead to memory leaks. Replacing the parent pointer to something using rc::Weak can help with this. (This will also inhibit deriving Eq and PartialEq, but those were previously flawed anyways [they’d stack-overflow trying to recurse through all the Rcs]. If you still need Eq/PartialEq, you’ll probably have to implement it manually, perhaps even just comparing the ids)

These considerations (and some more small changes) give something like:

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::{Rc, Weak};

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct HackStackObject {
    pub id: String,
    pub parent_ref: Option<String>,
}

type NodeRef = Rc<RefCell<Node>>;
type NodeRefWeak = Weak<RefCell<Node>>;

#[derive(Debug)]
struct Node {
    pub object: HackStackObject,
    pub parent: Option<NodeRefWeak>,
    pub children: Vec<NodeRef>,
}

impl Node {
    pub fn new(object: HackStackObject) -> NodeRef {
        Rc::new(RefCell::new(Node {
            object: object,
            parent: None,
            children: vec![],
        }))
    }
}

fn build_tree_and_get_roots(actual_objects: Vec<HackStackObject>) -> Vec<NodeRef> {
    todo!()
}

fn main() {
    let mut objects: Vec<HackStackObject> = vec![];

    objects.push(HackStackObject {
        id: "campus1".to_string(),
        parent_ref: None,
    });
    objects.push(HackStackObject {
        id: "site1".to_string(),
        parent_ref: Some("campus1".to_string()),
    });
    objects.push(HackStackObject {
        id: "equipment1".to_string(),
        parent_ref: Some("site1".to_string()),
    });
    objects.push(HackStackObject {
        id: "point1".to_string(),
        parent_ref: Some("equipment1".to_string()),
    });
    objects.push(HackStackObject {
        id: "point2".to_string(),
        parent_ref: Some("equipment1".to_string()),
    });

    let result = build_tree_and_get_roots(objects);

    println!("{:#?}", result);
}

Filling in the todo!() in the above code is then more-or-less straightforward.

In case you want some hints / just see a solution, here’s a “translation” staying quite close to the original C#. Click here for spoilers.

fn build_tree_and_get_roots(actual_objects: Vec<HackStackObject>) -> Vec<NodeRef> {
//  Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    let mut lookup = HashMap::<String, NodeRef>::new();
    
//  actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    actual_objects.into_iter().for_each(|x| {lookup.insert(x.id.clone(), Node::new(x));});
    
//  foreach (var item in lookup.Values) {
    for item in lookup.values() {
        let mut item_mut = item.borrow_mut();
        
//      Node proposedParent;
//      if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
        if let Some(parent_ref) = &item_mut.object.parent_ref {
            if let Some(proposed_parent) = lookup.get(parent_ref)
            {
                let mut proposed_parent_mut = proposed_parent.borrow_mut();
//              item.Parent = proposedParent;
                item_mut.parent = Some(Rc::downgrade(proposed_parent));
//              proposedParent.Children.Add(item);
                proposed_parent_mut.children.push(Rc::clone(item));
            }
        }
    }
//  return lookup.Values.Where(x => x.Parent == null);
    lookup.into_iter().map(|(_key, value)| value) .filter(|x| x.borrow().parent.is_none()).collect()
}

[glennpierce]

Thanks so much. I was just coming to the same conclusion about removing clone.
I hadn't considered using rc::Weak at all.