Newbie: Rust idiomatic way to deal with tree-like structures

1

Hi!

Creating a simple tree-like structure where parent/child nodes is fairly easy in most languages. The Typescript example below does the following:

  1. creates a parent
  2. adds a child to the parent
  3. grabs the newly created child
  4. adds a grandchild to the child
  5. prints out the parent including its decendants
// typescript example:
class Node {
  id:string;
  children:Array<Node> ;
  constructor(id:string) {
    this.id = id;
    this.children = [];
  }
  public addChild(id:string):Node {
    let child = new Node(id);
    this.children.push(child);
    return child;
  }
}

const parent:Node = new Node("parent");
const child:Node = parent.addChild("child");
const grandchild:Node = child.addChild("grandchild");
console.log(JSON.stringify(parent));

What would be the Rust idiomatic way of doing the same thing?

(Below is a simple attempt that in the end creates the same parent>child>grandchild relation, but is very limitied in that the add_child function doesn't return the child created . so I must keep refering to parent all the time... I'm sure it all comes down to my limited knowledge of Rust's borrowing handling!)

fn main() {
    let mut parent = Node::new("Parent".to_string());
    parent.add_child("Child".to_string());
// Can I somehow get hold of the child as a mutable variable here?
// the following is very limited and ugly...
    parent.children[0].add_child("Grandchild".to_string());
    println!("{:?}", parent);
}

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

impl Node {
    fn new(id:String)->Node {
        Node {id, children:vec![]}
    }

    fn add_child(&mut self, id:String) {
        let child = Node::new(id);
        self.children.push(child);
    }
}

Thanks!

2

You can make add_child return a mutable reference to the child:

    fn add_child(&mut self, id:String)->&mut Node {
        let child = Node::new(id);
        self.children.push(child);
        self.children.last_mut().unwrap()
    }
2 Likes
3

Thanks a lot, 2e71828! Didn't know of the .last_mut() method.

That works. However, the add_child method isn't returning the child directly - it is returned "via" children.last_mut().unwrap().
What if the children field was something else than a simple Vec pushed to, so that I couldn't rely on last_mut()?

4

Most collections will have a way (or several) to go from &mut Collection<T> to &mut T.

Alternatively, you can build the tree bottom-up instead of top-down so that you don't edit children after they've been inserted:

fn main() {
    let parent = Node::new("Parent", vec![
        Node::new("Child", vec![
            Node::new("Grandchild", vec![])
        ])
    ]);
    println!("{:?}", parent);
}

impl Node {
    fn new(id:String, children:Vec<Node>)->Node {
        Node {id, children:vec![]}
    }
}
1 Like
5

This is due to ownership rules in Rust. The child must be moved to its new owner (the children Vec) before you can return a reference to it.

1 Like
6

@parasyte

Thanks! Yes, I realize that's the way it has to be done.

@2e71828

Alternatively, you can build the tree bottom-up instead of top-down

Yes, that may be a better solution in many cases. But this example was created just for hoping to better understand how to deal with the ownership model. Thanks!

If anyone's interested, here's the original example modified with @2e71828's suggested solution:

fn main() {
    let mut parent = Node::new("Parent".to_string());
    let mut child = parent.add_child("Child".to_string());
    let mut grandchild = child.add_child("Grandchild".to_string());
    println!("{:?}", parent);
}

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

impl Node {
    fn new(id:String)->Node {
        Node {id, children:vec![]}
    }

    fn add_child(&mut self, id:String)-> &mut Node {
        let mut child = Node::new(id);
        self.children.push(child);
        self.children.last_mut().unwrap()
    }
}