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_06_TreeInorderIterator_App extends App {

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

    override def iterator: Iterator[T] =  new Iterator[T] {
      private var stack: List[BinTree[T]] = Nil
      private var treeV = BinTree.this

      override def next(): T = {
        while (treeV != Empty) {
          treeV match {
            case node@Node(_, l, _) =>
              stack = node :: stack
              treeV = l
          }
        }
        assert(treeV == Empty)
        stack match {
          case Nil =>
            throw new NoSuchElementException("da ist nichts mehr")
          case Node(v, _, r) :: tail =>
            stack = tail
            val result = v
            treeV = r
            result
        }
      }

      override def hasNext: Boolean = !(treeV == Empty && stack.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( 7,
      Node(5, Node(1, Empty, leaf(3)), leaf(6)),
      Node(12, Empty, Node(19, leaf(15), leaf(66)))
    )

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

}