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

  sealed trait BinTree[+A]
  case object Empty extends BinTree[Nothing]
  case class Node[+A](value:  A,
                      left:   BinTree[A],
                      right:  BinTree[A]
                     ) extends BinTree[A]


  case class Inorder2[A](process: A => Unit) {

    var stack: List[BinTree[A]] = Nil

    def inorderStack(tree: BinTree[A]): Unit = {
      var treeV = tree
      while (treeV != Empty) {
        treeV match {
          case node@Node(_, l, _) =>
            stack = node :: stack
            treeV = l
        }
      }
      processStack()
    }

    def processStack(): Unit = {
      stack match {
        case Nil =>
        case Node(v, _, r) :: tail =>
          stack = tail
          process(v)
          inorderStack(r)
      }
    }

    def apply(tree: BinTree[A]): Unit =
      inorderStack(tree)
  }

  val tree: BinTree[Int] =
    Node(4,
      Node(2,
        Node(1, Empty, Empty),
        Node(3, Empty, Empty)),
      Node(6,
        Node(5, Empty, Empty),
        Node(7, Empty, Empty)
      )
    )

  Inorder2(
    (x:Int) => println(x)
  )(tree)


}