Rudimentary Tree, and Pointers, in Rust

Question

Coming from a scripting language background with some C, trying to 'learn' Rust leads me to question my competence. I'm trying to figure out how to change an owned pointer, and struggling to do it.

Besides copying in from the extra libs, I can't figure out the recursion I need on a binary tree. Particularly, I don't know how to swap out the pointer branches. Whereas with a linked list I can cheat and use a temporary vector to return a new list, or prepend a new Cons(value, ~Cons) to the list head, branches have got me boggled.

enum NaiveTreeNode {
    NNil,
    NNode(~NaiveTreeNode, ~NaiveTreeNode, int, char) 
    //         left            right          key   val
}

impl NaiveTreeNode {
  fn eq(first_node: &NaiveTreeNode, second_node: &NaiveTreeNode) -> bool {
      match (first_node, second_node) {
          (&NNil, &NNil)              => true,
          ( &NNode( ~ref left_lval, ~ref left_rval, left_leafkey, left_leafval ),
            &NNode( ~ref right_lval, ~ref right_rval, right_leafkey, right_leafval )
          ) if left_leafkey == right_leafkey && left_leafval == right_leafval => {
              NaiveTreeNode::eq(left_lval, right_lval) && NaiveTreeNode::eq(left_rval, right_rval)
          },
          _                           => false
      }
  }

  fn add_branch(&mut self, node_to_add: ~NaiveTreeNode) {
      match (self, node_to_add) {
          (&NaiveTreeNode(~NNil, ~ref r_branch, leaf_key, leaf_val), ~NaiveTreeNode(_, _, new_node_key, _)              )
              if leaf_key > new_node_key   => self = &NaiveTreeNode(node_to_add, *r_branch, leaf_key, leaf_val),
          (&NaiveTreeNode(~ref l_branch, ~NNil, leaf_key, leaf_val), ~NaiveTreeNode(_, _, new_node_key, _))
               if leaf_key < new_node_key  => self = &NaiveTreeNode(*l_branch, node_to_add, leaf_key, leaf_val),
          (&NaiveTreeNode(~ref l_branch, _, leaf_key, _), ~NaiveTreeNode(_, _, new_node_key, _)) 
               if leaf_key > new_node_key  => self.add_branch(l_branch, node_to_add),
          (&NaiveTreeNode(_, ~ref r_branch, leaf_key, _), ~NaiveTreeNode(_, _, new_node_key, _)) 
               if leaf_key < new_node_key  => self.add_branch(l_branch, node_to_add),
          (_, ~NNil)                       => fail!("NNil branch. failing"),
          (&NNil, _)                       => fail!("NNil trunk. failing"),
          _                                => fail!("something is wrong. failing.")
      };
  }
}

The compiler throws 11 errors on this, and when I type it out, it feels like pseudocode. I'm frustrated because I feel okay implementing a tree with C pointers.

What I'm trying to do is update the pointers in-place--this is part of the reason I'm using them, right?--rather than copying the entire tree every time I want to make a change. But I don't even know how to get to them.

I'm not sure how I'd go about doing this with structs rather than enums. I've looked at the Treemap lib, but it seems to introduce too much complexity for what I want to accomplish right now, which is proof of concept--I might be trying to run when I should crawl, though!

Answer 1

I believe that you would do better with a different data representation:

struct NaiveTreeNode {
    left: Option<~NaiveTreeNode>,
    right: Option<~NaiveTreeNode>,
    key: int,
    val: char,
}

This will be easier to work with and is slightly more efficient (Option<~T> can be represented as a nullable pointer, while your current solution has a leaf node still requiring a pointer lookup to check if it's NNil).

You don't need to implement your eq method; it can be derived, an implementation of the Eq trait, by putting #[deriving(Eq)] immediately before the struct.

Of your add_branch method, you must understand that self.add_branch is a method bound to self. When you call self.add_branch(l_branch, node_to_add), that is invalid, for you are passing two arguments to one expecting one. What you meant was l_branch.add_branch(node_to_add).

I've restructured the add_branch method significantly; here's the complete code that I would write:

#[deriving(Eq)]
struct NaiveTreeNode {
    left: Option<~NaiveTreeNode>,
    right: Option<~NaiveTreeNode>,
    key: int,
    val: char,
}

impl NaiveTreeNode {
    fn add_branch(&mut self, node: ~NaiveTreeNode) {
        match (self.key.cmp(node.key), self.left, self.right) {
            (Greater, None, _) => self.left = Some(node),
            (Greater, Some(~ref mut left), _) => left.add_branch(node),
            (Less, _, None) => self.right = Some(node),
            (Less, _, Some(~ref mut right)) => right.add_branch(node),
            (Equal, _, _) => fail!("this tree already has a node with key {} \
                                    (value {}, attempted value {})", 
                                   self.key, self.value, node.value),
        }
    }
}

The match could also be expanded to the following, if you desired:

        match self.key.cmp(node.key) {
            Greater => match self.left {
                None => self.left = Some(node),
                Some(~ref mut left) => left.add_branch(node),
            },
            Less => match self.right {
                None => self.right = Some(node),
                Some(~ref mut right) => right.add_branch(node),
            },
            Equal => fail!("this tree already has a node with key {} \
                                  (value {}, attempted value {})", 
                                  self.key, self.value, node.value),
        }

If there's anything you don't understand in this code, just holler and I'll explain it.