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
 */

import scala.collection.mutable.ListBuffer

object AuD_13_14_GetAlgnment_App extends App {

  def getAlignment(a: String, b: String): List[(Char, Char)] =  {
    val n = a.length
    val m = b.length

    val Tab = Array.ofDim[Int](n+1, m+1)
    for(i <- 0 to n;
        j <- 0 to m) {
      Tab(i)(j) = (i, j) match {
        case (0, _) => j
        case (_, 0) => i
        case (_, _) =>
          List(
            Tab(i - 1)(j - 1) + (if (a(i-1) != b(j-1)) 1 else 0),
            Tab(i - 1)(j) + 1,
            Tab(i)(j - 1) + 1
          ).min
      }
    }

    var i = n
    var j = m
    val A: ListBuffer[(Char, Char)] = ListBuffer()

    while (i > 0 || j > 0) {
      if (i == 0) {
        A.prepend(('~', b(j-1)))
        j = j-1
      } else if (j == 0) {
        A.prepend((a(j-1), '~'))
        i = i - 1
      } else {
        val D = Tab(i-1)(j-1) + (if (a(i-1) != b(j-1)) 1 else 0 )
        val V = Tab(i-1)(j)
        val H = Tab(i)(j-1)
        if (D == Tab(i)(j)) {
          A .prepend((a(i-1), b(j-1)))
          i = i - 1
          j = j - 1
        } else if (V == Tab(i)(j)) {
          A.prepend((a(i-1), '~'))
          i = i - 1
        } else if (H == Tab(i)(j)) {
          A.prepend(('~', b(j-1)))
          j = j -1
        }
      }
    }

    A.toList
  }

  // NeedlemanWunsch
  // Rückverweise rekonstruieren (speichereffizienter)
  val a1 = getAlignment("LIEBEN", "FLIEGEN")
  println(a1.map( _._1).mkString(" ")) // ~ L I E B E N
  println(a1.map( _._2).mkString(" ")) // F L I E G E N


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

    val align = 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) => align(n)(m) = (0 until n).map(i => (x(i), '~')).toList
        case (0, _) => align(n)(m) = (0 until m).map(j => ('~', y(j))).toList
        case (i, j) => align(n)(m) = 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
  }

  println()

  // Rueckverweise als Bestandteil der Tabelle (einfacher)
  val a2 = alignIiter("LIEBEN", "FLIEGEN")
  println(a1.map( _._1).mkString(" ")) // ~ L I E B E N
  println(a1.map( _._2).mkString(" ")) // F L I E G E N

}