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

    /*
     * Die knappe Form des Algorithmus von Dijkstra ist:
     */

    struct Edge: Hashable {
        let s: String
        let e: String

        init (_ s: String, _ e: String) {
            self.s = s
            self.e = e
        }
    }

    static func dijkstraShortString(_ s: String,
                                    _ z: String,
                                    _ E: [Edge],
                                    _ W: [Edge : Double]) -> Double? {

        func neighbors(_ s: String) -> [String] {
            E.flatMap({ (e) in e.s == s ? [e.e] : [] } )
        }

        var T: [String] = [s]
        var D: [String : Double] = [ : ]
        D[s] = 0

        while (T.count > 0) {
            let v = T.min(by: { (x, y) in D[x] ?? Double(Int.max) < D[y] ?? Double(Int.max) } )!
            if (v == z) {
                return D[z]
            }
            for w in neighbors(v) {
                let dwOld = D[w] ?? Double(Int.max)
                let dwNew = D[v]! + W[Edge(v, w)]!
                if dwNew < dwOld {
                    D[w] = dwNew
                    T = T + [w]
                }
            }
            T = T.filter({ x in x != v })
        }
        return nil
    }

    /*
     * ----------------------------------------------------------------------------------------
     * Das geht auch generisch:
     */

    struct EdgeG<V: Hashable>: Hashable {
        let s: V
        let e: V

        init (_ s: V, _ e: V) {
            self.s = s
            self.e = e
        }
    }


    static func dijkstraShortGen<V: Hashable>(_ s: V,
                                    _ z: V,
                                    _ E: [EdgeG<V>],
                                    _ W: [EdgeG<V> : Double]) -> Double? {

        func neighbors(_ s: V) -> [V] {
            E.flatMap({ (e) in e.s == s ? [e.e] : [] } )
        }

        var T: [V] = [s]
        var D: [V : Double] = [ : ]
        D[s] = 0

        while (T.count > 0) {
            let v = T.min(by: { (x, y) in D[x] ?? Double(Int.max) < D[y] ?? Double(Int.max) } )!
            if (v == z) {
                return D[z]
            }
            for w in neighbors(v) {
                let dwOld = D[w] ?? Double(Int.max)
                let dwNew = D[v]! + W[EdgeG(v, w)]!
                if dwNew < dwOld {
                    D[w] = dwNew
                    T = T + [w]
                }
            }
            T = T.filter({ x in x != v })
        }
        return nil
    }

    /*
     *  Der Algorithmus mit heuristischer Knotenwahl:
     */
    static func Astar<V: Hashable>(_ s: V,
                                   _ z: V,
                                   _ E: [EdgeG<V>],
                                   _ W: [EdgeG<V> : Double],
                                   _ rest: (V, V) -> Double ) -> Double? {

        func neighbors(_ s: V) -> [V] {
            E.flatMap({ (e) in e.s == s ? [e.e] : [] } )
        }

        var T: [V] = [s]
        var D: [V : Double] = [ : ]
        D[s] = 0

        while (T.count > 0) {
            let v = T.min(by: { (x, y) in (D[x] ?? Double(Int.max) + rest(x,z)) < (D[y] ?? Double(Int.max) + rest(y,z)) } )!
            if (v == z) {
                return D[z]
            }
            for w in neighbors(v) {
                let dwOld = D[w] ?? Double(Int.max)
                let dwNew = D[v]! + W[EdgeG(v, w)]!
                if dwNew < dwOld {
                    D[w] = dwNew
                    T = T + [w]
                }
            }
            T = T.filter({ x in x != v })
        }
        return nil
    }

    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
        }
    }

    // 15 places
    static let places: [Place] = zip(
        [(1,1), (11,1), (5,3), (16,5), (5,9),
        (10,8), (17,9), (14,10), (13, 13), (1,13),
        (8,15), (13,16), (3,19), (13, 19), (20,20)],
        ["a", "b", "c", "d", "e", "f", "g", "h",
         "i", "j", "k", "l", "m", "n", "o"])
        .map ( { (p, c) in
            let (x, y) = p;
            return Place(c, x, y)
        } )

    static let connections: [(String, String)] = [
        ("a", "c"), ("c", "f"), ("f", "e"), ("c", "e"), ("b", "e"),
        ("b", "d"), ("d", "g"), ("g", "h"), ("e", "h"), ("e", "i"),
        ("e", "k"), ("k", "l"), ("k", "j"),("k", "m"),("n", "o"),
        ("h", "o")
    ]

    static let edges_oneDirection: [(Place, Place)] =
        connections.map( { (pp) in
            let (s, d) = pp;
            return (places.filter({ (p) in p.name == s})[0], places.filter({ (p) in p.name == d})[0])
        })

    static let edges: [EdgeG<Place>] =
        edges_oneDirection.flatMap({ (place1: Place, place2: Place) -> [EdgeG<Place>] in
            [EdgeG(place1, place2), EdgeG(place2, place1)]
    })

    static var W: [EdgeG<Place> : Double] = Dictionary(
         uniqueKeysWithValues: edges.map( {
             (edge: EdgeG<Place>) in (edge, edge.s.distTo(edge.e))
         })
    )

    static func run() {
        let a: Place = places.filter({ (p) in p.name == "a" })[0]
        for z: Place in places {
            if let dist: Double =
                Astar(
                    a,
                    z,
                    edges,
                    W,
                    { (p1:Place, p2: Place) -> Double in p1.distTo(p2) }
                ) {
                print("distance \(a) to \(z) is \(dist)")
            } else {
                print("\(z) is not reachable from \(a)")
            }
        }

    }

}