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

import Foundation

struct AuD_08_06_KnapsackDomi {

    struct Item: CustomStringConvertible {
        let name: String
        let gewicht: Int
        let wert: Int
        var description: String {
            "(\(name), \(gewicht), \(wert))"
        }
    }

    // "sorting in Swift is not guaranteed to be stable"
    // MergeSort ist stabil
    static func MergeSort<A>(a: inout [A], l: Int, r: Int, leq: (A, A) -> Bool) {

        func Merge(l: Int, m: Int, r: Int) {
            var b = [A](repeating: a[0], count: a.count)
            var i_l = l
            var i_r = m
            var j = l
            while (i_l < m || i_r <= r) {
                if ( i_r > r || (i_l < m) && leq(a[i_l], a[i_r]) ) {
                    b[j] = a[i_l]
                    i_l = i_l + 1
                } else {
                    b[j] = a[i_r]
                    i_r = i_r + 1
                }
                j = j + 1
            }
            for i in l ... r {
                a[i] = b[i]
            }
        }

        if (l < r) {
            let m: Int = (l + r + 1) / 2 // AUF-gerundete ganzahlige Division !
            MergeSort(a: &a, l: l, r: m - 1, leq: leq)
            MergeSort(a: &a, l: m, r: r, leq: leq)
            Merge(l: l, m: m, r: r)
        }

    }

    static func stableSortItems(items: inout [[Item]]) {
        MergeSort(
            a: &items,
            l: 0,
            r: items.count-1,
            leq: { (itemsA, itemsB) in
                let aGewicht = itemsA.map({ (item: Item) in item.gewicht}).reduce(0, +)
                let bGewicht = itemsB.map({ (item: Item) in item.gewicht}).reduce(0, +)
                return aGewicht <= bGewicht
            })
    }


    static func KnapsackDomi(M: [Item], T: Int) -> [Item] {

        func GetDominants(L: inout [[Item]]) -> [[Item]] {

            //sortiere L absteigend nach dem Wert
            L = L.sorted(by: { (a: [Item], b: [Item]) in
                let bValue = b.map({ (item: Item) in item.wert }).reduce(0, +)
                let aValue = a.map({ (item: Item) in item.wert}).reduce(0, +)
                return bValue > aValue
            })

            //sortiere L stabil aufsteigend nach dem Gewicht
            stableSortItems(items: &L)


            var combi = L[0]
            var D: [[Item]] = []
            D = D + [combi]
            for l in L.dropFirst() {
                if (l.map({ (item: Item) in item.wert }).reduce(0, +) > combi.map({ (item: Item) in item.wert }).reduce(0, +)) {
                    combi = l
                    D = D + [combi]
                }
            }
            return D
        }

        var D: [[Item]] = [[]]
        for mi in M {
            var L: [[Item]] = []
            for combi in D {
                L = L + [combi]
                if (combi.map({ (item: Item) in item.gewicht }).reduce(0, +) + mi.gewicht <= T) {
                    L = L + [[mi] + combi]
                }
            }
            D = GetDominants(L: &L)
        }
        return D.last!
    }

    static func run() {
        let items1 = [Item(name: "A", gewicht: 7, wert: 42), Item(name: "B", gewicht: 3, wert: 12), Item(name: "C", gewicht: 4, wert: 40), Item(name: "D", gewicht: 5, wert: 25)]
        let items2 = [Item(name: "Goldkorn", gewicht: 1, wert: 10), Item(name: "Silberbarren", gewicht: 200, wert: 500)]
        let items3 = [Item(name: "Computer", gewicht: 3, wert: 300), Item(name: "TV", gewicht: 12, wert: 200), Item(name: "Uhr", gewicht: 10, wert: 150), Item(name: "Vase", gewicht: 7, wert: 100)]

        let selection1 = KnapsackDomi(M: items1, T: 10)
        let selection2 = KnapsackDomi(M: items2, T: 200)
        let selection3 = KnapsackDomi(M: items3, T: 20)

        print("1: " + selection1.map({ (i) in i.description}).joined(separator: ", "))
        print("2: " + selection2.map({ (i) in i.description}).joined(separator: ", "))
        print("3: " + selection3.map({ (i) in i.description}).joined(separator: ", "))
    }

}