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

struct AuD_13_11_AlignmentDivideConquer {

    /*
     * 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 von vorn nach hinten, statt von hinten nach vorn, kann das implementiert
     * werden als:
     */

    static func align(_ x: [Character], _ y: [Character]) -> [(Character, Character)] {

        func countDiffs(_ l: [(Character, Character)]) -> Int {
            l.filter({ (pair: (Character, Character)) in pair.0 != pair.1}).count
        }

        switch (x, y) {
        case (_, []):
            return x.map({ (c: Character) in (c, "-") })
        case ([], _):
            return y.map({ (c: Character) in ("-", c) })
        default:
            let a: Character = x[0]
            let tail_x: [Character] = Array(x.dropFirst())
            let b: Character = y[0]
            let tail_y: [Character] = Array(y.dropFirst())
            return  [
                [(a, b)] + align(tail_x, tail_y),
                [(a, Character("-"))] + align(tail_x, y),
                [(Character("-"), b)] + align(x, tail_y)
            ].min( by: { (l1:[(Character, Character)], l2: [(Character, Character)])
                    in countDiffs(l1) < countDiffs(l2) })!
        }
    }

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

    static func alignI(_ x: String, _ y: String)-> [(Character, Character)] {
        let X: [Character] = Array(x)
        let Y: [Character] = Array(y)

        func countDiffs(_ l: [(Character, Character)]) -> Int {
            l.filter({ (pair: (Character, Character)) in pair.0 != pair.1}).count
        }

        func align(_ n: Int, _ m: Int) -> [(Character, Character)] {
            switch (n, m) {
            case (_, 0) :
                return (0 ..< n).map( { (i) in (X[i], Character("_")) } )
            case (0, _) :
                return (0 ..< m).map( { (i) in (Character("_"), Y[i]) } )
            case (let i, let j) :
                return [
                    align(i - 1, j - 1) + [(X[i - 1], Y[j - 1])],
                    align(i - 1, j) + [(X[i - 1], Character("-"))],
                    align(i, j - 1) + [(Character("-"), Y[j - 1])]
                ].min( by: { (l1:[(Character, Character)], l2: [(Character, Character)])
                in countDiffs(l1) < countDiffs(l2) })!
            }
        }

        return align(x.count, y.count)
    }

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

    static func alignWithTable(_ x: String, _ y: String) -> [(Character, Character)]  {

        let X = Array(x)
        let Y = Array(y)

        func countDiffs(_ l: [(Character, Character)]) -> Int {
            l.filter({ (pair: (Character, Character)) in pair.0 != pair.1}).count
        }

        var alignTable: [[[(Character, Character)]]] = Array(
            repeating: Array(repeating: [] as [(Character, Character)], count: Y.count+1),
            count: X.count+1)

        for n in 0 ... X.count {
            for m in 0 ... Y.count {
                switch (n, m) {
                case (_, 0) :
                    alignTable[n][m] = (0 ..< n).map( { (i) in (X[i], Character("_")) } )
                case (0, _) :
                    alignTable[n][m] = (0 ..< m).map( { (i) in (Character("_"), Y[i]) } )
                case (let i, let j) :
                    alignTable[n][m] = [
                        alignTable[i - 1][j - 1] + [(X[i - 1], Y[j - 1])],
                        alignTable[i - 1][j] + [(X[i - 1], Character("-"))],
                        alignTable[i][j - 1] + [(Character("-"), Y[j - 1])]
                    ].min( by: { (l1:[(Character, Character)], l2: [(Character, Character)])
                    in countDiffs(l1) < countDiffs(l2) })!
                }
            }
        }

        return alignTable[X.count][Y.count]
    }

    static func run() {
        let a1 = align(Array("LIEBEN"), Array("FLIEGEN"))
        print(a1.map({ p in String(p.0)}).joined(separator: " "))
        print(a1.map({ p in String(p.1)}).joined(separator: " "))
        print()
        let a2 = alignI("LIEBEN", "FLIEGEN")
        print(a2.map({ p in String(p.0)}).joined(separator: " "))
        print(a2.map({ p in String(p.1)}).joined(separator: " "))
        print()
        let a3 = alignWithTable("LIEBEN", "FLIEGEN")
        print(a3.map({ p in String(p.0)}).joined(separator: " "))
        print(a3.map({ p in String(p.1)}).joined(separator: " "))
    }

}