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 Rc
s]. 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()
}