/* Breadth-First Search 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 a Breadth-First
Search Visitor that is a specialization and extension of the
BinTreeVisitor feature of the top-level framework.  The ArrayList
collection from the Java API is replaced by the Queue from the Scala
API.

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

123456789012345678901234567890123456789012345678901234567890123456789012345678
*/


import scala.collection.mutable.Queue

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

   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 BreadthFirstVisitor[Val,State]
  (bfs: BreadthFirstVisitStrategy[Val,State], ts: State)
  extends BinTreeVisitor[Val] {

  // attributes
  private var strategy = bfs
  private var state    = ts
  private var nodeQ    = new Queue[BinTree[Val]]

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

  // visitor hook implementations
  def visit(t: Node[Val]) {
    val l = t.getLeft
    val r = t.getRight
    if (l != null && !l.isEmpty) nodeQ += l
    if (l != null && !r.isEmpty) nodeQ += r
    state = strategy.visitNode(state,t)
    if(!nodeQ.isEmpty) nodeQ.dequeue.accept(this)
  }

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

  // accessors
  def getResult: State = state
}


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

abstract trait BreadthFirstVisitStrategy[Val,State] {
  def visitNode(ts: State, t: BinTree[Val]): State
  def visitNilTree (ts: State, t: BinTree[Val]): State
}