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.{TreeSet => MutableSet}
import Ordering.Double.TotalOrdering

object AuD_14_03_TSPGreedy_App extends App {

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

  def TSPGreedy(S: List[Place]): List[Place] = {
    var s: MutableSet[Place] = MutableSet(S: _*)( (p1, p2) => p1.name.compareTo(p2.name) )
    var a = s.head
    s -= a
    var L = List(a)

    while (s.nonEmpty) {
      val b = s.minBy( p => a.distTo(p) )
      s.remove(b)
      L = b :: L
      a = b
    }
    L.reverse
  }

  // 15 places
  val places = List(
    (1,1),    // a
    (11,1),   // b
    (5,3),    // c
    (16,5),   // d
    (9,5),    // e
    (5,9),   // f
    (17,9),   // g
    (14,10),  // h
    (13,13),  // i
    (1,14),   // j
    (8,15),   // k
    (13,16),  // l
    (3,19),   // m
    (12, 19), // n
    (20,20)  // o
  ).zip('a' to 'o')
    .map {
      case ((x, y), c) => Place(c.toString, x, y)
    }

  def length(vs: List[Place]): Double =
    vs.sliding(2, 1).foldLeft(0.0)( (acc, x) => acc + x(0).distTo(x(1)))

  val trip = TSPGreedy(places)
  println(trip.map( _.name).mkString(", "))
  println(s"length = ${length(trip)}")

}