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

  import scala.collection.mutable.Map

  case class Trie[T](
                      val succ: Map[Symbol, Trie[T]],
                      var info: Option[T])            // None = unmarked node

  def insert[T](t: Trie[T], v: List[Symbol], info: T) : Unit = v match {
    case head::Nil  => // leaf node
      val next = t.succ.get(head) // is head already present
      next match {
        case None => // not present add new node in pace
          t.succ += (head -> Trie[T](Map(), Some(info)))
        case Some(trie) => // leaf node add info (mark node)
          trie.info = Some(info)
      }
    case head::tail => // inner node
      val next = t.succ.get(head)
      next match {
        case None => // create new trie, insert in new trie, add to given trie
          val nt = Trie[T](Map(), None)
          insert(nt, tail, info)
          t.succ += (head -> nt)
        case Some(trie) => insert(trie, tail, info)
      }
    case _ => throw new IllegalArgumentException()
  }

  def find[T](t: Trie[T], l: List[Symbol]) : Option[T] = {
    val next = t.succ.get(l.head)
    next match {
      case None => None
      case Some(Trie(suc, info)) => l match {
        case head::Nil => info
        case head::tail => find(t.succ(head), tail)
        case _ => throw new IllegalArgumentException() // malformed trie
      }
    }
  }

  val t = Trie[String](Map[Symbol, Trie[String]](), None)
  val words = List("der", "dampf", "dauer", "da", "daumen")
  for (word <- words) {
    insert(t, (word.split("")).map(Symbol(_)).toList, word)
  }
  for (word <- words) {
    println(find(t, (word.split("")).map(Symbol(_)).toList))
  }

}