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

    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 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 TSPLocalSearch(_ S: [Place]) -> [Place] {

        func TSPImproveTour(_ L: [Place]) -> [Place] {
            let s_L = length(L)
            for i in 0 ..< L.count-1 {
                for j in 1 ..< L.count {
                    var a = L
                    let t = a[i]
                    a[i] = a[j]
                    a[j] = t
                    let l = length(a)
                    if l < Double(Int.max) && l < s_L {
                        return a
                    }
                }
            }
            return L
        }

        var L: [Place] = S

        while (true) {
            let L_ = TSPImproveTour(L)
            if (L == L_) {
                return L
            }
            L = 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 run() {
        let trip = TSPLocalSearch(places)
        print(trip)
        print(length(trip))
    }
}