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

    class Item: CustomStringConvertible {
        let name: String
        let gewicht: Int
        let wert: Int

        init(name: String, gewicht: Int, wert: Int) {
            self.name = name
            self.gewicht = gewicht
            self.wert = wert
        }

        var description: String {
            "(\(name), \(gewicht), \(wert))"
        }
    }

    class ItemReduced: Item {
        let urWert: Int
        init(item: Item, r: Double) {
            self.urWert = item.wert
            super.init(name: item.name, gewicht: item.gewicht, wert: Int(Double(item.wert)/r))
        }
    }

    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<I: Item>(items: inout [[I]]) {
        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<I : Item>(M: [I], T: Int) -> [I] {

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

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

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


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

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

    static func KnapsackApprox(M: [Item], T: Int, epsilon: Double) -> [Item] {
        let w_max: Int = M.max(by: { (a, b) in a.wert > b.wert })!.wert
        let r: Double = (epsilon * Double(w_max)) / Double(M.count)
        let Mreduced: [ItemReduced] = M.map( { item in ItemReduced(item: item, r: r) } )
        let S: [ItemReduced] = KnapsackDomi(M: Mreduced, T: T)
        return S.map( { (iR: ItemReduced) in Item(name: iR.name, gewicht: iR.gewicht, wert: iR.urWert) } )
    }

    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: ", "))
    }

}