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

import Foundation

struct AuD_14_03_TSPGreedy {

    struct Place: Hashable, CustomStringConvertible {
        let name: String
        let x: Double
        let y: Double

        init(_ name: String, _ x: Int, _ y: Int) {
            self.name = name
            self.x = Double(x)
            self.y = Double(y)
        }

        func distTo(_ other: Place) -> Double {
            sqrt((x-other.x)*(x-other.x) + (y-other.y)*(y-other.y))
        }

        var description: String {
            name
        }
    }

    static func TSPGreedy(_ S: [Place]) -> [Place] {
        var s: [Place] = S
        var a: Place = s[0]
        var L: [Place] = [a]

        s = Array(s.dropFirst())

        while (s.count > 0) {
            let b: Place = s.min(by: { (p1, p2) in a.distTo(p1) < a.distTo(p2) } )!
            s = s.filter({(p) in p != b})
            L = L + [b]
            a = b
        }
        return L
    }

    static let places: [Place] = [
        Place("a",1,1),
        Place("b",11,1),
        Place("c",5,3),
        Place("d",16,5),
        Place("e",9,5),
        Place("f",5,9),
        Place("g",17,9),
        Place("h",14,10),
        Place("i",13,13),
        Place("j",1,14),
        Place("k",8,15),
        Place("l",13,16),
        Place("m",3,19),
        Place("n",12, 19),
        Place("o",20,20)
    ]

    static func length(_ vs: [Place]) -> Double {
        var l = 0.0
        for i in 1 ..< vs.count {
            l = l + vs[i-1].distTo(vs[i])
        }
        return l
    }

    static func run() {
        let trip = TSPGreedy(places)
        print(trip)
        print(length(trip))
    }
}