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

import Foundation

struct AuD_07_10_BubbleGnomeInsertionSort {

    static func BubbleSort<A: Comparable>(a: inout [A], l: Int, r: Int) {

        func swap(i: Int, j: Int) {
            let t = a[i]
            a[i] = a[j]
            a[j] = t
        }

        var sorted = true
        repeat {
            sorted = true
            for i in l ..< r {
                if (a[i] > a[i + 1]) {
                    swap(i: i, j: i + 1)
                    sorted = false
                }
            }
        } while (!sorted)
    }

    static func GenomeSort<A: Comparable>(a: inout [A], l: Int, r: Int) {

        func swap(i: Int, j: Int) {
            let t = a[i]
            a[i] = a[j]
            a[j] = t
        }

        var i = l
        while (i <= r) {
            if (i == l || a[i-1] <= a[i]) {
                i = i + 1
            } else {
                swap(i:i - 1, j:i)
                i = i - 1
            }
        }
    }

    static func InsertionSort<A: Comparable>(a: inout [A], l: Int, r: Int) {
        for i in l+1 ... r {
            let x = a[i]
            var j = i
            while (j > l && a[j-1] > x) {
                a[j] = a[j-1]
                j = j-1
            }
            a[j] = x
        }
    }

    struct ConstrWorker: Comparable, CustomStringConvertible {
        let name: String
        let weight: Int
        static func < (lhs: ConstrWorker, rhs: ConstrWorker) -> Bool {
            lhs.weight < rhs.weight
        }
        var description: String { "[\(name), \(weight)]" }
    }

    static let a = [ConstrWorker(name: "Alex", weight: 77),
                    ConstrWorker(name: "Bert", weight: 72),
                    ConstrWorker(name: "Claus", weight: 96),
                    ConstrWorker(name: "Dominik", weight: 111),
                    ConstrWorker(name: "Emil", weight: 96),
                    ConstrWorker(name: "Flo", weight: 122),
                    ConstrWorker(name: "Gerd", weight: 75)]

    static func run() {
        var aMutable: [ConstrWorker] = a
        BubbleSort(a: &aMutable, l: 0, r: a.count-1)
        print(aMutable.map({ (x) in x.description} ).joined(separator: ", "))

        aMutable = a
        GenomeSort(a: &aMutable, l: 0, r: a.count-1)
        print(aMutable.map({ (x) in x.description} ).joined(separator: ", "))

        aMutable = a
        InsertionSort(a: &aMutable, l: 0, r: a.count-1)
        print(aMutable.map({ (x) in x.description} ).joined(separator: ", "))
    }

}