/* Binary Tree Traversal Framework
   Top-level framework
   H. Conrad Cunningham
   Version #1: 15 October 2008
   Version #2: 29 April 2010   Separate each level into a separate file

This program is a relatively straightforward translation into Scala of
the non-generic Java code for the Binary Tree Traversal framework
described in the paper:

  H. C. Cunningham, Y. Liu, and C. Zhang. Using classic problems to
  teach Java framework design, Science of Computer Programming,
  Special Issue on Principles and Practice of Programming in Java
  (PPPJ 2004), Vol. 59, No. 1-2, pp. 147-169, January 2006. 
  doi: 10.10.16/j.scico.2005.07.009.

This Scala version uses a singleton object to replace the application
of the Singleton pattern in the Java version.  However, it does not
attempt to take advantage of other enhanced features of Scala.  For
example, this code just uses Scala traits to define the signatures of
the interfaces and does not use generics to avoid casting within
applications.

123456789012345678901234567890123456789012345678901234567890123456789012345678
*/


/* Class BinTree a Binary Tree base class structured for the role
   Component base class in the Composite design pattern.  It also has
   the role of Element in the Visitor design pattern.
*/

abstract class BinTree {
  // mutators
  def setValue(nv: Any)     { }
  def setLeft (nl: BinTree) { }       
  def setRight(nr: BinTree) { }

  // accept Visitor object
  def accept(vis: BinTreeVisitor) 

  //accessors
  def getValue: Any     = null 
  def getLeft:  BinTree = null
  def getRight: BinTree = null
}


/* Class Node is a binary tree node with a value and left and right
   subtrees.  This has the role of Composite subclass in the Composite
   design pattern and role of a ConcreteElement class in the Visitor
   pattern.
*/

class Node(v: Any, l: BinTree, r: BinTree) extends BinTree {

  // attributes
  private var nodeVal = v
  private var left    = l
  private var right   = r
 
  // mutators
  override def setValue(nv: Any)     { nodeVal = nv    }
  override def setLeft (nl: BinTree) { left    = nl    }
  override def setRight(nr: BinTree) { right   = nr    }

  // accept Visitor object
  def accept(vis: BinTreeVisitor)    { vis.visit(this) }

  // accessors
  override def getValue = nodeVal
  override def getLeft  = left 
  override def getRight = right

  // redefine toString to aid in testing
  override def toString = "Node(" + l + "(" + nodeVal + ")" + r + ")"
}


/* Singleton object NilTree represents an empty binary tree node.
   This has the role of a Leaf subclass in the Composite design 
   pattern and ConcreteElement class in the Visitor pattern.  
*/

object NilTree extends BinTree {
  def accept(v: BinTreeVisitor) { v.visit(this) }  // accept Visitor
  override def toString = "NilTree"
}


/* The BinTreeVisitor trait defines the Binary Tree Visitor
   interface. This interface has the Visitor base role in the Visitor
   design pattern.  Implementations of this interface are tightly
   coupled with the BinTree Composite hierarchy.  Implementations are
   expected to do their own traversals of the BinTree
   structure.
*/

abstract trait BinTreeVisitor {
  def visit(t: Node)
  def visit(t: NilTree.type)
}