/**
 * User: Martin
 * Date: 06.06.2014
 * Time: 14:59
 */
case class Edge(from: Int, to: Int, weight: Double) extends Ordered[Edge] {
  override def compare(that: Edge): Int = weight.compareTo(that.weight)

  def reverse = Edge(to = from, from = to, weight = weight)
}


class NNHeuristic(val allLocations: List[Location], val constraints: List[PrecedenceConstraint]) {
  def makeCompleteGraph(ls: List[Location]) = {
    for (x <- ls; y <- ls; if x.getCityId != y.getCityId) yield Edge(x.getCityId, y.getCityId, x.distanceTo(y))
  }

  def findFailingConstraints(tour: Seq[Location]): Seq[PrecedenceConstraint] = {
    for {pc <- this.constraints
         first = pc.getFirst
         second = pc.getSecond
         i = tour.indexWhere(_.getCityId == first)
         j = tour.indexWhere(_.getCityId == second)
         if i != -1 && j != -1 && i >= j} yield new PrecedenceConstraint(first, second)
  }

  def nearestNeighborTour(tour: Vector[Location], edgesNotTaken: Set[Edge], relevantLocations: Map[Int, Location]): Vector[Location] = {
    if (tour.containsSlice(relevantLocations.values.toSeq)) {
      tour
    }

    else {
      val lastId = tour.head.getCityId
      val nextEdgeCandidates = edgesNotTaken.filter(edge => edge.from == lastId)
      val nextEdge = nextEdgeCandidates.filter(edge => relevantLocations.keySet.contains(edge.to)).toSeq.sorted.head
      val nextNode = relevantLocations(nextEdge.to)
      val newTour = tour :+ nextNode
      val failingConstraints = findFailingConstraints(newTour)

      if (failingConstraints.size == 0) {
        nearestNeighborTour(newTour, edgesNotTaken - nextEdge, relevantLocations - nextNode.getCityId)
      }
      else {
        val pc = failingConstraints.head
        val firstIndex = newTour.indexWhere(_.getCityId == pc.getFirst)
        val secondIndex = newTour.indexWhere(_.getCityId == pc.getSecond)
        val tourSwapped = newTour.updated(firstIndex, allLocations(pc.getSecond)).updated(secondIndex, allLocations(pc.getFirst))
        nearestNeighborTour(tourSwapped, edgesNotTaken - nextEdge, relevantLocations - nextNode.getCityId)
      }
    }
  }
}

object Main {
  def calcObjectiveValue(solution: Seq[Location]): Double = {
    var sumDistance: Double = 0
    var last: Location = null
    import scala.collection.JavaConversions._
    for (c <- solution) {
      if (last != null && c != null) {
        sumDistance += last.distanceTo(c)
      }
      last = c
    }
    if (last != null && (solution.get(0) ne last)) {
      sumDistance += last.distanceTo(solution.get(0))
    }
    sumDistance
  }

  def main(args: Array[String]) {
    val tspInstance = new TspLibReader("C:\\Users\\Martin\\Desktop\\asd2\\public_instances\\0001").readInstance()
    import scala.collection.JavaConverters._
    val nodeMap = tspInstance.getAllLocations.asScala.map {
      case (a, b) => (a.intValue(), b)
    }.toMap

    val start = System.nanoTime

    val nodes = tspInstance.getAllLocations.asScala.values.toList
    val constraints = tspInstance.getConstraints.asScala.toList
    val nn = new NNHeuristic(nodes, constraints)

    val tour = nn.nearestNeighborTour(Vector(nodeMap(2)), nn.makeCompleteGraph(nodes).toSet, nodeMap - 2)

    val end = System.nanoTime

    println(tour.map(_.getCityId))
    println(calcObjectiveValue(tour))

    println("t = " + (end - start) / 1e6 + " ms")
  }

}