package kapitel_13

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

object AuD_13_11_AlignmentDivideConquer_App extends App {

  /*
   * Abbildung 13.11 skizziert ein Verfahren nach dem Prinzip Teilen und Herrschen für das Alignment von zwei Strings.
   * Auf einfachste Art mit Listen und wieder von vorn nach hinten, statt von hinten nach vorn, kann das implementiert
   * werden als:
   */

  def align(x: List[Char], y: List[Char]): List[(Char, Char)] = (x, y) match {
    case (_, Nil) => x.map(c => (c, '~'))
    case (Nil, _) => y.map(c => ('~', c))
    case (a :: tail_x, b :: tail_y) => List(
      (a, b) :: align(tail_x, tail_y),
      (a, '~') :: align(tail_x, y),
      ('~', b) :: align(x, tail_y)
    ).minBy(_.count { case (c1, c2) => c1 != c2 })
  }

  /*
   * Hier können wir wieder wie bei der Editierdistanz vom vorderen auf das hintere Ende übergehen
   * und das jeweils  letzte Zeichen durch einen Index ersetzen:
   */

  def alignI(x: String, y: String): List[(Char, Char)] = {

    def align(n: Int, m: Int): List[(Char, Char)] = (n, m) match {
      case (_, 0) => (0 until n).map(i => (x(i), '~')).toList
      case (0, _) => (0 until m).map(j => ('~', y(j))).toList
      case (i, j) => List(
        (x(i - 1), y(j - 1)) :: align(i - 1, j - 1),
        (x(i - 1), '~') :: align(i - 1, j),
        ('~', y(j - 1)) :: align(i, j - 1)
      ).minBy(
        _.count { case (c1, c2) => c1 != c2 }
      )
    }

    align(x.length, y.length).reverse
  }


  val a1 = align("LIEBEN".toList, "FLIEGEN".toList)

  println(a1.map( _._1).mkString(" ")) // ~ L I E B E N
  println(a1.map( _._2).mkString(" ")) // F L I E G E N

  println()

  val a2 = alignI("LIEBEN", "FLIEGEN")
  println(a2.map( _._1).mkString(" ")) // ~ L I E B E N
  println(a2.map( _._2).mkString(" ")) // F L I E G E N

  println()

  //------------------------------------------------------------------------------------------
  // Hier erkennt man leicht, dass die Funktion align tabellarisiert werden kann:

  def alignWithTable(x: String, y: String): List[(Char, Char)] = {

    val alignTable = Array.ofDim[List[(Char, Char)]](x.length+1, y.length+1)

    for (n <- 0 to x.length;
         m <- 0 to y.length) {
      (n, m) match {
        case (_, 0) =>
          alignTable(n)(m) = (0 until n).map(i => (x(i), '~')).toList
        case (0, _) =>
          alignTable(n)(m) = (0 until m).map(j => ('~', y(j))).toList
        case (i, j) =>
          alignTable(n)(m) = List(
            (x(i - 1), y(j - 1)) :: alignTable(i - 1)(j - 1),
            (x(i - 1), '~') :: alignTable(i - 1)(j),
            ('~', y(j - 1)) :: alignTable(i)(j - 1)
          ).minBy(
            _.count { case (c1, c2) => c1 != c2 }
          )
      }
    }
    alignTable(x.length)(y.length).reverse
  }

  val a = alignWithTable("LIEBEN", "FLIEGEN")
  println(a.map( _._1).mkString(" ")) // ~ L I E B E N
  println(a.map( _._2).mkString(" ")) // F L I E G E N

}