package kapitel_14

/**
 * 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 scala.collection.mutable
import Ordering.Double.TotalOrdering

object AuD_14_02_Astar_App extends App {

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

  def dijkstraShortString(s: String,
               z: String,
               E: List[(String, String)],
               W: Map[(String, String), Double]): Option[Double] = {

    def neighbors(s: String): List[String] =
      for ((x, y) <- E
           if x == s) yield y

    var T: Set[String] = Set(s)
    val D: mutable.HashMap[String, Double] = mutable.HashMap()
    D.update(s,0)

    while (T.nonEmpty) {
      val v = T.minBy(x => D.getOrElse(x, Double.MaxValue))
      if (v == z) {
        return Some(D(z))
      }
      for (w <- neighbors(v)) {
        val dwOld = D.getOrElse(w, Double.MaxValue)
        val dwNew = D(v) + W((v, w))
        if (dwNew < dwOld) {
          D.update(w, dwNew)
          T = T + w
        }
      }
      T = T - v
    }
    None
  }

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

  def dijkstraShortGen[V](
                  s: V,
                  z: V,
                  E: List[(V, V)],
                  W: Map[(V, V), Double]): Option[Double] = {

    def neighbors(s: V): List[V] =
      for ((x, y) <- E
           if x == s) yield y

    var T: Set[V] = Set(s)
    val D: mutable.HashMap[V, Double] = mutable.HashMap()
    D.update(s,0)

    while (T.nonEmpty) {
      val v = T.minBy(x => D.getOrElse(x, Double.MaxValue))
      if (v == z) {
        return Some(D(z))
      }
      for (w <- neighbors(v)) {
        val dwOld = D.getOrElse(w, Double.MaxValue)
        val dwNew = D(v) + W((v, w))
        if (dwNew < dwOld) {
          D.update(w, dwNew)
          T = T + w
        }
      }
      T = T - v
    }
    None
  }

  /*
   * ----------------------------------------------------------------------------------------
   *  Der Algorithmus mit heuristischer Knotenwahl:
   */

  def Astar[V](s: V,
                  z: V,
                  E: List[(V, V)],
                  W: Map[(V, V), Double],
                  rest: (V, V) => Double
              ): Option[Double] = {

    def neighbors(s: V): List[V] =
      for ((x, y) <- E
           if x == s) yield y

    var T: Set[V] = Set(s)
    val D: mutable.HashMap[V, Double] = mutable.HashMap()
    D.update(s,0)

    while (T.nonEmpty) {
      val v = T.minBy(x => D.getOrElse(x, Double.MaxValue.toDouble) + rest(x,z)   )
      if (v == z) {
        return Some(D(z))
      }
      for (w <- neighbors(v)) {
        val dwOld: Double = D.getOrElse(w, Double.MaxValue)
        val dwNew: Double = D(v) + W((v, w))
        if (dwNew < dwOld) {
          D.update(w, dwNew)
          T = T + w
        }
      }
      T = T - v
    }
    None
  }

  case class Place(name: String, x: Double, y: Double) {
    def distTo(other: Place): Double =
      Math.sqrt((x-other.x)*(x-other.x) + (y-other.y)*(y-other.y))
  }

  // 15 places
  val places = List(
    (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)
  ).zip('a' to 'o')
    .map {
      case ((x, y), c) => Place(c.toString, x, y)
      case _ => throw new Throwable("will never happen")
    }

  val connections: List[(String, String)] = List (
    ("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")
  )

  val edges_oneDirection: List[(Place, Place)] =
    for (p <- connections)
      yield p match {
        case (s, d) => ( places.find( _.name == s).get, places.find( _.name == d).get )
      }

  val edges: List[(Place, Place)] = edges_oneDirection.flatMap {
    case (s, d) => List((s,d), (d, s))
  }

  // distances
  // all street are straight
  val W: Map[(Place, Place), Double] =
    edges.map {
      case (s, d) => ((s, d), s.distTo(d))
      case _ => throw new Throwable("will never happen")
    } . toMap


  for (z <- places) {
    println(s"$z -> ${dijkstraShortGen(
      places.find( _.name == "a").get,
      z,
      edges,
      W).getOrElse("Not reachable")}")

    println(s"$z -> ${Astar(
      places.find( _.name == "a").get,
      z,
      edges,
      W,
      (p1:Place, p2: Place) => p1.distTo(p2)).getOrElse("Not reachable")}")
    println()
  }


}