scala/ScalaBook/chapter-11/src/main/scala/scalabook/iter/iter.scala

package scalabook.iter

import java.io._
import scalabook.file.{NativeFile, VFile}
trait NodeChildrenProvider[T] {
  def childrenOf(node: T): Iterator[T]
}

class FileChildrenProvider extends NodeChildrenProvider[File] {
  def childrenOf(file: File) = file.listFiles match {
    case null => Iterator.empty
    case array => array.elements
  }
}

class VFileChildrenProvider[T <: VFile[T]] extends NodeChildrenProvider[T] {
  def childrenOf(node: T) = node.children.elements
}

object NativeChildrenProvider extends VFileChildrenProvider[NativeFile]

class NodeIterator[T](root: T)(implicit provider: NodeChildrenProvider[T]) extends Iterator[T] {
  private[this] var currentRoot = root
  private[this] val visited = new collection.mutable.HashSet[T]
  // We check these nodes to produce children
  private[this] val toVisit = new collection.mutable.Stack[T]
  toVisit.push(root)
  // The node which produces the currently iterating children
  private[this] var currentNode: Option[T] = None
  // The children of currentNode
  private[this] var currentIterator: Iterator[T] = Iterator.empty

  private[this] var computedHasNext = false
  //private[this] var _hasNext = false
  private[this] var _next: Option[T] = None
  private[this] var nextIsCurrentNode = false

  // hasNext must remember state
  def hasNext = false

  // The workhorse is hasNext, our job then is easy
  def next: T =
    if (hasNext) {
      val result = _next.get
      _next = None
      result
    }
    else
      throw new NoSuchElementException
}

abstract class NodeIteratorSkeleton[T]
  (start: T, provider: NodeChildrenProvider[T]) extends Iterator[T] {
  // None <==> no next value has been computed
  // We could make this private and have computeNext just return an Option[T]
  protected var _next: Option[T] = None

  protected def computeNext: Boolean

  def hasNext = {
    if (_next.isDefined)
      true
    else
      computeNext
  }

  def next = {
    if(hasNext) {
      val result = _next.get
      _next = None
      result
    } else
      throw new NoSuchElementException
  }

  def toString(mapper: T => String): String

  override def toString = toString(_.toString)
}

/**
 *         1
 *       /  \
 *     2     6
 *   / \    / \
 *  3   4  7   8
 *      |
 *      5
 *
 * Preorder:  1, 2, 3, 4, 5, 6, 7, 8
 * PostOrder: 3, 5, 4, 2, 7, 8, 6, 1
 * BFS:       1, 2, 6, 3, 4, 7, 8, 5
 */
// A straightforward implementation for a preorder DFS iterator
class PreOrderDFS[T](start: T, provider: NodeChildrenProvider[T]) extends NodeIteratorSkeleton(start, provider) {
  private[this] val toExplore = new LIFOStore[T].addNode(start)

  protected def computeNext: Boolean = {
    toExplore.remove match {
      case nodeOpt@Some(node) =>
        _next = nodeOpt
        toExplore.addChildrenOf(node, provider)
        true
      case None =>
        _next = None
        false
    }
  }

  def toString(mapper: T => String) =
    Map("toExplore" -> toExplore.map(mapper)).toString
}

// A straightforward implementation for a postorder DFS iterator
class PostOrderDFS[T](start: T, provider: NodeChildrenProvider[T]) extends NodeIteratorSkeleton(start, provider) {
  private[this] val toExplore = new LIFOStore[T].addNode(start) //.addChildrenOf(start, provider)
  private[this] var processed = Set[T]()

  protected def computeNext: Boolean = {
    toExplore.remove match {
      case nodeOpt@Some(node) =>
        if (processed.contains(node)) {
          _next = nodeOpt
          processed -= node
          true
        }
        else {
          toExplore.addNode(node)
          toExplore.addChildrenOf(node, provider)
          processed += node

          computeNext
        }
      case None =>
        _next = None
        false
    }
  }

  def toString(mapper: T => String) =
    Map("toExplore" -> toExplore.map(mapper),
      "processed" -> processed.map(mapper)).toString
}

class BFS[T](start: T, provider: NodeChildrenProvider[T]) extends NodeIteratorSkeleton(start, provider) {
  private[this] val toExplore = new FIFOStore[T].addNode(start)

  protected def computeNext: Boolean = {
    toExplore.remove match {
      case nodeOpt@Some(node) =>
        _next = nodeOpt
        toExplore.addChildrenOf(node, provider)
        true
      case None =>
        _next = None
        false
    }
  }

  def toString(mapper: T => String) =
    Map("toExplore" -> toExplore.map(mapper)).toString
}

trait NodeStore[T] {
  def addNode(node: T): NodeStore[T]

  def addChildrenOf(node: T,
                    provider: NodeChildrenProvider[T]): NodeStore[T]

  def remove: Option[T]

  def map[S](f: T => S): NodeStore[S]
}

class LIFOStore[T] extends NodeStore[T] {
  private var stack = List[T]()

  def addNode(node: T) = {stack = node :: stack; this}

  def addChildrenOf(node: T, provider: NodeChildrenProvider[T]) = {
    val children = provider.childrenOf(node).toList.reverse
    for (child <- children) addNode(child)
    this
  }

  def remove = stack match {
    case node :: rest =>
      stack = rest
      Some(node)
    case Nil =>
      None
  }

  def map[S](f: T => S) = {
    val result = new LIFOStore[S]
    result.stack = stack.map(f)
    result
  }

  override def toString = stack.toString
}

class FIFOStore[T] extends NodeStore[T] {
  private var queue = new collection.immutable.Queue[T]

  def addNode(node: T) = {
    queue = queue.enqueue(node)
    this
  }

  def addChildrenOf(node: T, provider: NodeChildrenProvider[T]) = {
    val children = provider.childrenOf(node)
    val buf = new collection.mutable.ListBuffer[T]
    for (child <- children) {
      addNode(child)
      buf += child
    }
    buf.clear
    this
  }

  def remove =
    if (queue.isEmpty)
      None
    else {
      val (end, newQueue) = queue.dequeue
      queue = newQueue
      Some(end)
    }

  def map[S](f: T => S) = {
    val result = new FIFOStore[S]
    queue.foreach(t => result.addNode(f(t)))
    result
  }

  override def toString = queue.toString
}