/* Euler Tour Traversal Visitor (Generic Version)
   A second-level framework, a part of the Binary Tree Traversal Framework
   H. Conrad Cunningham
   Version #1: 29 April 2010

This is a second-level framework that introduces an EulerTourVisitor
that is a specialization and extension of the BinTreeVisitor feature
of the top-level framework. 

A concrete EulerStrategy object will be needed for an application of
this framework.

123456789012345678901234567890123456789012345678901234567890123456789012345678
*/


/* Class EulerTourVisitor is a concrete binary tree visitor class that
   implements an Euler tour traversal of the BinTree structure.  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.  

   Type parameter Val is the type of values stored at the nodes of the
   BinTrees and type parameter State is the value of the computation folded 
   through the traversal.

*/

class EulerTourVisitor[Val,State](es: EulerStrategy[Val,State], ts: State) 
  extends BinTreeVisitor[Val] {

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

  // mutators
  def setVisitStrategy(ns: EulerStrategy[Val,State]) { strategy = ns }
  def reinitResult                                   { state = ts    }
  def setResult(r: State)                            { state = r     }

  // visitor hook implementations
  def visit(t: Node[Val]) {
    state = strategy.visitLeft(state,t)    // upon first arrival from above
    val l = t.getLeft
    if (l != null) l.accept(this)
    state = strategy.visitBottom(state,t)  // upon return from left
    val r = t.getRight
    if (r != null) r.accept(this)
    state = strategy.visitRight(state,t)   // upon completion of this node
  }

  def visit(t: NilTree[Val]) { state = strategy.visitNilTree(state,t) }

  // accessors
  def getResult: State = state
}


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

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

abstract trait EulerStrategy[Val,State] {
  def visitLeft    (ts: State, t: BinTree[Val]): State 
  def visitBottom  (ts: State, t: BinTree[Val]): State
  def visitRight   (ts: State, t: BinTree[Val]): State
  def visitNilTree (ts: State, t: BinTree[Val]): State
}