package kapitel_05

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_05_07_TreeBreadthFirstIterator_App extends App {

  sealed trait BinTree[+T] extends Iterable[T] {

    import scala.collection.mutable.{Queue => MutableQueue}

    override def iterator: Iterator[T] =  new Iterator[T] {
      private val queue = MutableQueue[BinTree[T]]()
      private var treeV = BinTree.this

      override def next(): T = {
        if (treeV == Empty) {
          treeV = queue.dequeue()
        }
        treeV match {
          case Node(v, l, r) =>
            if (l != Empty) queue.enqueue(l)
            if (r != Empty) queue.enqueue(r)
            treeV = Empty
            v
          case Empty =>
            throw new IllegalStateException("must not happen")
        }
      }

      override def hasNext: Boolean = !(treeV == Empty && queue.isEmpty)
    }
  }

  case object Empty extends BinTree[Nothing]

  case class Node[+A](value:  A,
                      left:   BinTree[A],
                      right:  BinTree[A]
                     ) extends BinTree[A]

  def leaf[A](v: A) = Node(v, Empty, Empty)

  val tree: BinTree[Int] =
    Node( 1,
      Node(2,
        Node(4,
          leaf(8),
          leaf(9)),
        leaf(5)),
      Node(3,
        Node(6,
          leaf(10),
          leaf(11)),
        leaf(7))
    )

  for (v <- tree) {
    println(v)
  }

}