/* Binary Tree Traversal Framework (Generic Version)
   Top-level framework
   H. Conrad Cunningham
   Version #1: 29 April 2010

This program is a translation into Scala and an enhancement 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 generics and function arguments.  This version
also added the isEmpty method to BinTree to help avoid type
checking.

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.

   Type parameter Val in these classes and traits denote the type of
   the values stored at the nodes of the BinTree.
*/

abstract class BinTree[Val] {
  private var DEFVAL: Val = _ 

  // mutators
  def setValue(nv: Val)          { }
  def setLeft (nl: BinTree[Val]) { }       
  def setRight(nr: BinTree[Val]) { }

  // accept Visitor object
  def accept(vis: BinTreeVisitor[Val]) 

  //accessors
  def getValue: Val          = DEFVAL
  def getLeft:  BinTree[Val] = null
  def getRight: BinTree[Val] = null
  def isEmpty: Boolean
}


/* 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[Val](v: Val, l: BinTree[Val], r: BinTree[Val])
  extends BinTree[Val] {

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

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

  // accessors
  override def getValue = nodeVal
  override def getLeft  = left 
  override def getRight = right
  def isEmpty: Boolean  = false

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


/* Class 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.  
*/

class NilTree[Val] extends BinTree[Val] {
  def accept(v: BinTreeVisitor[Val]) { v.visit(this) }  // accept Visitor
  def isEmpty: Boolean  = true
  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.

   Type parameter Val is the type of values stored at the nodes of the
   BinTrees.
*/

trait BinTreeVisitor[Val] {
  def visit(t: Node[Val])
  def visit(t: NilTree[Val])
}