/* Euler Tour Traversal Visitor
   A second-level framework, a part of the Binary Tree Traversal Framework
   H. Conrad Cunningham
   Version #1: 15 October 2008
   Version #2: 29 April 2010   Separate each level into separate files

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

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
    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.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.

   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 {
  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
}