Rust ref and boxes

rust_path_length.rs

extern crate core;

use core::cmp::min;

enum Tree {
  EmptyTree,
  BranchTree(int, Box<Tree>, Box<Tree>)
}

fn path_length(tree: &Tree, first: int, second: int) -> int {
  let (first_length, second_length) = inner_path_length(tree, first, second);
  increment(first_length, second_length)
}

fn inner_path_length(tree: &Tree, first: int, second: int) -> (int, int) {
  let branch_path_length = |value: int, left: &Tree, right: &Tree| {
    if value == first {
      let second_length = min(depth(left, second), depth(right, second));
      (0, increment(second_length, 1))
    } else if value == second {
      let first_length = min(depth(left, first), depth(right, first));
      (increment(first_length, 1), 0)
    } else {
      let (first_left_length, second_left_length) = inner_path_length(
        left,
        first,
        second);
      let (first_right_length, second_right_length) = inner_path_length(
        right,
        first,
        second);

      if first_left_length != std::int::MAX &&
         second_left_length != std::int::MAX {
        (first_left_length, second_left_length)
      } else if first_right_length != std::int::MAX &&
                second_right_length != std::int::MAX  {
        (first_right_length, second_right_length)
      } else {
        (increment(1, min(first_left_length, first_right_length)),
         increment(1, min(second_left_length, second_right_length)))
      }
    }
  };

  match tree {
    &Tree::EmptyTree => (std::int::MAX, std::int::MAX),
    &Tree::BranchTree(value, ref left, ref right) => branch_path_length(
      value,
      &**left,
      &**right)
  }
}

fn depth(tree: &Tree, key: int) -> int {
  let branch_depth = |value: int, left: &Tree, right: &Tree| {
    if value == key {
      0
    } else {
      increment(1, min(depth(left, key), depth(right, key)))
    }
  };

  match tree {
    &Tree::EmptyTree => std::int::MAX,
    &Tree::BranchTree(value, ref left, ref right) => branch_depth(
      value,
      &**left,
      &**right)
  }
}

fn increment(first: int, second: int) -> int {
  if first == std::int::MAX || second == std::int::MAX {
    std::int::MAX
  } else {
    first + second
  }
}

fn main() {
  let tree = Tree::BranchTree(
    0,
    box Tree::BranchTree(1,
                         box Tree::BranchTree(2,
                                              box Tree::EmptyTree,
                                              box Tree::EmptyTree),
                         box Tree::EmptyTree),
    box Tree::BranchTree(3, box Tree::EmptyTree, box Tree::EmptyTree));


  println!("The path length (3,2) = {}", path_length(&tree, 3, 2));
  println!("The path length (1,2) = {}", path_length(&tree, 1, 2));
  println!("The path length (3,1) = {}", path_length(&tree, 1, 3));
  println!("The path length (0,2) = {}", path_length(&tree, 0, 2));
}