/* Binary Tree Visitor Framework
   CSci 581/582: Special Topics in Computer Science
   Multiparadigm Programming in Scala, Fall 2008
   H. Conrad Cunningham
   Version #0:  2 October 2008
   Version #1: 15 October 2008 Replaced Nil by NilTree because of List
                               Spelling corrections

This is a relatively straightforward translation into Scala of the
Java code for the Binary Tree Traversal framework and applications
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 version uses the Scala singleton objects 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.  It also might be useful to consider
redesigning the framework to use Scala higher-order functions instead
of the (probably more verbose) applications of the Strategy pattern.
It might also be useful to incorporate a different data structure to
replace the Javaesque use of ArrayList.  Neither the original Java nor
the Scala framework uses generics; the framework should be modified to
do that.

123456789012345678901234567890123456789012345678901234567890123456789012345678
*/

import scala.collection.jcl._

/***********************************************************************
  Beginning of top-level Binary Tree Visitor Framework
************************************************************************/

/* 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)
}

/***********************************************************************
  End of top-level Binary Tree Visitor Framework
************************************************************************/

/***********************************************************************
  Beginning of second-level Euler Tour Traversal Framework
************************************************************************/

/* Class EulerTourVisitor is a concrete binary tree visitor class that
   implements an Euler tour traversal of the tree.  This has the
   ConcreteVisitor role in the Visitor design pattern.  It also has
   the role Context in the Strategy design pattern.  Method visit is a
   template method for the  Euler tour traversal second-level
   framework.
*/

class EulerTourVisitor(es: EulerStrategy, ts: Any) extends BinTreeVisitor {

  // attributes
  private var strategy = es
  private var state    = ts

  // mutators
  def setVisitStrategy(ns: EulerStrategy) { strategy = ns }
  def reinitResult                        { state = ts    }
  def setResult(r: Any)                   { state = r     }

  // visitor hook implementations
  def visit(t: Node) {
    state = strategy.visitLeft(state,t)    // upon first arrival from above
    t.getLeft.accept(this)
    state = strategy.visitBottom(state,t)  // upon return from left
    t.getRight.accept(this)
    state = strategy.visitRight(state,t)   // upon completion of this node
  }

  def visit(t: NilTree.type) { state = strategy.visitNilTree(state,t) }

  // accessors
  def getResult: Any = state
}

/* Trait EulerVisitStrategy is the Strategy base interface defines the
   interface to the hook methods used by the EulerTourVisitor visit
   method.
*/

abstract trait EulerStrategy {
  def visitLeft    (ts: Any, t: BinTree): Any 
  def visitBottom  (ts: Any, t: BinTree): Any
  def visitRight   (ts: Any, t: BinTree): Any
  def visitNilTree (ts: Any, t: BinTree): Any
}

/*  Note: Preorder, postorder, and inorder traversals can be implemented 
    either as applications of the Euler tour traversal or as their own 
    simpler Visitors.
*/

/***********************************************************************
  End of second-level Euler Tour Traversal Framework
************************************************************************/

/***********************************************************************
  Beginning of second-level Binary Tree Mapping Framework
************************************************************************/

/* Class MappingVisitor is a concrete binary tree visitor class that
   implements a map operation over BinTree's.  That is, it applies a
   unary operator to every value stored in the tree. This has the
   ConcreteVisitor role in the Visitor design pattern.  It also has
   the role Context in the Strategy design pattern.  Method visit is
   a template method for the Mapping Visitor second-level
   framework.
*/

class MappingVisitor(op: UnaryOp) extends BinTreeVisitor {

  // attributes
  private var vop = op

  // mutators
  def setMapOp(op: UnaryOp) { vop = op }

  // visitor hook implementations
  def visit(t: Node) {
    t.setValue(vop.apply(t.getValue))
    t.getLeft.accept(this)
    t.getRight.accept(this)
  }

  def visit(t: NilTree.type) { }
}

/* Trait UnaryOp is a Strategy base interface that defines the hook
   method used by the MappingVisitor visit method.
*/

abstract trait UnaryOp {   
  def apply(v: Any): Any
}

/***********************************************************************
  End of second-level Binary Tree Mapping Framework
************************************************************************/

/***********************************************************************
  Beginning of second-level Breadth First Traversal Framework
************************************************************************/

/* Class BreadthFirstVisitor is a concrete binary tree visitor class
   that implements a breadth first traversal of the tree.  This has
   the ConcreteVisitor role in the Visitor design pattern.  It also
   has the role Context in the Strategy design pattern.  Method visit
   is a template method for the breadth first traversal second-level
   framework.
*/

class BreadthFirstVisitor(bfs: BreadthFirstVisitStrategy, ts: Any)
  extends BinTreeVisitor {

  // attributes
  private var strategy = bfs
  private var state    = ts
  private var nodeQ    = new ArrayList[Any]

  // mutators
  def setVisitStrategy(ns: BreadthFirstVisitStrategy) { strategy = ns }
  def reinitResult      { state = ts }
  def setResult(r: Any) { state = r  }

  // visitor hook implementations
  def visit(t: Node) {
    val l = t.getLeft
    val r = t.getRight
    if (l.isInstanceOf[Node]) nodeQ.add(l)
    if (r.isInstanceOf[Node]) nodeQ.add(r)
    state = strategy.visitNode(state,t)
    if(!nodeQ.isEmpty) nodeQ.remove(0).asInstanceOf[BinTree].accept(this)
  }

  def visit(t: NilTree.type) { state = strategy.visitNilTree(state,t)  }

  // accessors
  def getResult: Any = state
}

/* Trait BreadthFirstVisitStrategy is Strategy base interface defines
   the hook methods used by the BreadthFirst visit method.
*/

abstract trait BreadthFirstVisitStrategy {
  def visitNode(ts: Any, t: BinTree): Any
  def visitNilTree (ts: Any, t: BinTree): Any
}

/***********************************************************************
  End of second-level Breadth First Traversal Framework
************************************************************************/

/***********************************************************************
  Applications of frameworks 
************************************************************************/

/* Parenthesized traversal strategy for Euler traversal framework */

class VisitParen extends EulerStrategy {
  def visitLeft(ts: Any, t: BinTree)   = 
    ts.asInstanceOf[String] + "("
  def visitBottom(ts: Any, t: BinTree) = 
    ts.asInstanceOf[String] + t.getValue.asInstanceOf[String]
  def visitRight(ts: Any, t: BinTree)  = 
    ts.asInstanceOf[String] + ")" 
  def visitNilTree(ts: Any, t: BinTree) = 
    ts.asInstanceOf[String] + "(NIL)"
}

// Zap out values to be stars for Mapping
class AllStars extends UnaryOp { 
  def apply(v: Any) = "*"
}

// Append values for breadth first traversal
class Appender extends BreadthFirstVisitStrategy {

  def visitNode(ts: Any, t: BinTree)     =
    ts.asInstanceOf[String] + "|" + t.getValue.asInstanceOf[String]

  def visitNilTree (ts: Any, t: BinTree) = ts
}


/*  Toward a test program.  Minimal testing so far.  */

object BinTreeTest {

  def main(args: Array[String]) {   
    val vs = new VisitParen
    val v  = new EulerTourVisitor(vs,"START>")

    println("Euler parenthesized traversal")
    println("Input is NilTree")
    NilTree.accept(v)
    println(v.getResult.asInstanceOf[String])
    println(" ")
    
    v.reinitResult
    val t = new Node("1",new Node("2",NilTree,new Node("3",NilTree,NilTree)),
	                 new Node("4",NilTree,NilTree) ) 
    println("Input is " + t)
    t.accept(v)
    println(v.getResult.asInstanceOf[String])
    println(" ")

    println("Breadth first traversal -- appender");
    val bfs = new Appender
    val bfv = new BreadthFirstVisitor(bfs,"");
    t.accept(bfv);
    println(bfv.getResult.asInstanceOf[String])

    println("Mapping Visitor -- allstars");
    val mv = new MappingVisitor(new AllStars)
    t.accept(mv)
    println("Result is: " + t.asInstanceOf[Node])
    v.setResult("")
    t.accept(v)
    println(v.getResult.asInstanceOf[String])
  }
}