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_04_InorderProcess_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]

  // in-order traversal
  case class InOrderTraversalWithProcess[A](process: A => Unit) {

    private def inorder(tree: BinTree[A]): Unit = tree match {
      case Empty =>
        Nil
      case Node(v, l, r) =>
        inorder(l)
        process(v)
        inorder(r)
    }

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

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

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

}