package kapitel_11

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 11, Probleme totschlagen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_11_05_BinTreePaths_App extends App {

  /*
   * Alle Pfade von der Wurzel zu einem Blatt in einem perfekten Baum der Tiefe n können mit einem
   * Algorithmus aufgezählt werden, der den Baum gar nicht sehen muss.
   * Es ist klar, welche Pfade es in einem solchem Baum gibt.
   * Wenn der Baum nicht so perfekt gebaut ist, dann muss man ihn sich ansehen, wenn man alle Pfade von
   * der Wurzel zu irgendeinem Blatt erzeugen will.
   */

  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]

  def AllPaths[A](t: BinTree[A]): List[List[String]] = {
    var result: List[List[String]] = Nil

    def APR(t: BinTree[A], path: List[String]): Unit = t match {
      case Empty =>
        result = result ++ List(path)
      case Node(_, l, r) =>
        for (d <- List("l", "r")) {
          APR(( (s:String) => s match {
            case "l" => l
            case "r" => r })(d),
            path ++ List(d)
          )
        }
    }

    t match {
      case Empty =>
      case _ => APR(t, Nil)
    }
    result
  }

  // zur Vereinfachung des Baumaufbaus
  def leaf[A](a: A): Node[A] = Node(a, 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)))
    )

  def flatten[A](t: BinTree[A]): String = t match {
    case Empty => "."
    case Node(v, l, r) =>
      s"[${v.toString}, ${flatten(l)}, ${flatten(r)}]"
  }

  println(flatten(tree))

  println(AllPaths(tree).map( _.mkString("")).mkString(", "))

}