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


  class BinSearchTree[K, V](implicit ord: K => Ordered[K]) {
    private var tree: BinTree[(K, V)] = Empty

    def insert(key: K, value: V): Unit = {
      tree = insertF(key, value, tree)
    }

    def lookup(key: K): Option[V] =
      lookupF(key, tree)


    private def insertF(key: K, value: V, t: BinTree[(K, V)]): BinTree[(K, V)] = t match {
      case Empty =>
        Node((key, value), Empty, Empty)
      case Node((k, _), _, _) if k == key =>
        t
      case Node((k, v), l, r) if k > key =>
        Node((k, v),
          insertF(key, value, l),
          r)
      case Node((k, v), l, r) if k < key =>
        Node((k, v),
          l,
          insertF(key, value, r))
    }

    private def lookupF(key: K, t: BinTree[(K, V)]): Option[V] = t match {
      case Empty => None
      case Node((k, v), _, _) if k == key =>
        Some(v)
      case Node((k, _), l, _) if k > key =>
        lookupF(key, l)
      case Node((k, _), _, r) if k < key =>
        lookupF(key, r)
    }
  }

  val BST = new BinSearchTree[Int, String]()

  BST.insert(10, "J")

  List((8, "H"), (1,"A"), (2, "B"), (5, "E"), (9, "I"), (6, "F"), (7, "G"), (3, "C"), (4, "D")).foreach {
    case (k, v) =>
      BST.insert(k,v)
  }

  for (i <- 1 to 10) {
    println(s"$i -> ${BST.lookup(i)}")
  }

}