Sunday, January 23, 2011

First program in Scala: porting binary search add/remove from Java

Today I worked on my first program in Scala, after reading most of Programming Scala. This is the first time in a very long time that I try to learn a new programming language and I took the approach of first reading the book. After starting writing the code, though, I noticed how important it is to actually code something in the language, as without coding, you can't remember much.

So, what I did first was to port the code to delete nodes from a binary tree available here in Java to Scala. The outcome was almost identical, except for some Scala-specific things, like trying to use Option.

Second, I tried to make is more Scala ("scalafy my code") and, since it's been a couple of weeks since I last read the "Programming Scala", I thought that there wasn't a whole lot I could do for this kind of program. However, after trying to implement pattern matching in some sections, I realized that I could get rid of my if statements (which were long, with a bunch of elses) only with pattern matching. Also, some of the "get" calls on the Options objects ended up being unnecessary with the pattern matching. I thought the result was quite elegant compared to the Java version. Open the Java version in a different tab and compare the code, and let me know what you think. Also, if you know Scala, please let me know what suggestions you would have to make use of more Scala features.

case class Node(value: Int, var right: Option[Node], var left: Option[Node])

object TreeUtils {
 def printInOrder(node: Option[Node]) {
  node match {
   case Some(node) => {
    printInOrder(node.left);
    Console.print(" " + node.value);
    printInOrder(node.right);    
   }
   case _ => ;
  }
 }
 
 def addNode(node: Option[Node], valueToAdd: Int): Option[Node] = {
  node match {
   case None => 
    Option(new Node(valueToAdd, None, None));
   case Some(currentNode) => {
    currentNode.value match {
     case v if v < valueToAdd =>
      currentNode.right = addNode(currentNode.right, valueToAdd);
      node;
     case v if v > valueToAdd =>
      currentNode.left = addNode(currentNode.left , valueToAdd);
      node;
     case _ => node;
    }
   }
  }
 }
 
 def deleteNode(node: Option[Node], valueToDelete: Int): Option[Node] = {
  node match {
   case None => 
    None;
   case Some(currentNode) => {
    currentNode.value match {
     case v if v < valueToDelete =>
      currentNode.right  = deleteNode(currentNode.right, valueToDelete);
      node;
     case v if v > valueToDelete =>
      currentNode.left  = deleteNode(currentNode.left , valueToDelete);
      node;
     case _ => {
      (currentNode.left, currentNode.right) match {
       case (None, None) => None
       case (None, _) => currentNode.right 
       case (_, None) => currentNode.left
       case (Some(leftNode), Some(rightNode)) if rightNode.left == None => {
        rightNode.left = currentNode.left;
        currentNode.right;
       }
       case (Some(leftNode), Some(rightNode)) => {
        var q = rightNode;
        var p = rightNode;
        
        while (p.left.get.left != None)
         p = p.left.get;
        
        q = p.left.get;
        p.left = q.right;
        q.left  = currentNode.left;
        q.right = currentNode.right;
        Some(q);
       }
      }
     }
    }
   }
  }
 }
}

object BinaryTree {
 def main(args: Array[String]) = {
  var root : Option[Node] = None;
  val numbers: Array[Int] = Array(56,86,71,97,82,99,65,36,16,10,28,52,46);
  for (i <- numbers) {
   Console.println("Inserting " + i);
   root = TreeUtils.addNode(root, i);
  }
  Console.print("Tree: ");
  TreeUtils.printInOrder(root);
  Console.println();
  for (i <- numbers) {
   Console.println("Removing " + i);
   root = TreeUtils.deleteNode(root, i);
   Console.print("Tree: ");
   root match {
    case None => Console.println("  ");
    case _ => 
     TreeUtils.printInOrder(root);
     Console.println();
   }
  }
  Console.println("Done");
 }
}
Post a Comment