/* Breadth-First Search 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 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.
*/

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

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

  // 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 != null && l.isInstanceOf[Node]) nodeQ += l
    if (r != null && r.isInstanceOf[Node]) nodeQ += r
    state = strategy.visitNode(state,t)
    if(!nodeQ.isEmpty) nodeQ.dequeue.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
}