package pl.edu.pw.mini.sg.compactlp

import pl.edu.pw.mini.sg.compactlp.model.{Flow, GridPosition, GridSpacetime}
import pl.edu.pw.mini.sg.util.TraversableUtils.combs
import pl.edu.pw.mini.sg.compactlp.util.{Attacker, Position, PureStrategy}
import pl.edu.pw.mini.sg.compactlp.util.SparseUtils._

import scala.collection.mutable

/** Klasa generuje strategie w nastepujacy sposob:
  * 1. Stworzenie grafu przeplywow z wartosci przeplywu
  * 2. Dopoki istnieje sciezka w grafie z pozycji startowych do wierzcholkow koncowych:
  * 2a.   Zamien sciezke na sciezke niezagregowana (wydluzona, nie rozproszona na razie) i dodaj do sciezek obroncy
  * 2b.   Pomniejsz przeplyw w grafie wzdluz sciezki o minimalna wartosc przeplywu na sciezce
  * 2c.   Usuniecie krawedzi o zerowym przeplywie z grafu
  * 3. Dla kazdego punktu startowego obroncow:
  * 3a.   Wyznacz sciezki startujacego z tego punktu
  * 3b.   Rozdziel te sciezki na wszystkich obroncow startujacych z tego punktu
  * (dzielimy prawd. sciezki przez ilosc obroncow na jaka ja rozdzielamy)
  * 4. Wygenerowanie wszystkich kombinacji pozycji dla obroncow
  * (zamiast listy sciezek mamy liste strategii, gdzie strategia to lista pozycji obroncow dla kazdego czasu)
  * 5. Powielenie otrzymanych pozycji w taki sposob, aby pokrywaly caly zagregowany kwadrat (kazda sciezka jest powielana s*s razy)
  *
  * @param eps - Dokladnosc obliczen numerycznych. Wartosci przeplywu mniejsze rowne eps sa ignorowane przy generowaniu strategii
  */
class SparseStrategyGenerator(eps: Double) extends StrategyGenerator {

  override def getStrategy(flow: Map[Flow, Double], grid: Seq[GridSpacetime], game: CompactGameWrapper, sparsity: Int): List[PureStrategy] = {
    def flowValuesToGraph(flowValues: mutable.Map[Flow, Double]): Map[GridSpacetime, Map[GridSpacetime, Double]] = {
      grid.filterNot(_.time == game.getTimeSteps(sparsity)).map {
        case GridSpacetime(t, position) =>
          (GridSpacetime(t, position), game.getGridNeighbours(position, sparsity).map(p => (GridSpacetime(t + 1, p), flowValues(Flow(position, p, t)))).filter(_._2 > eps).toMap)
      }.filter(_._2.nonEmpty).toMap
    }

    val flowValues = mutable.Map(grid.filterNot(_.time == game.getTimeSteps(sparsity)).flatMap {
      case GridSpacetime(t, position) =>
        game.getGridNeighbours(position, sparsity).map(p => (Flow(position, p, t), flow(Flow(position, p, t))))
    }.toMap.toSeq: _*)
    var change = true
    val paths = mutable.ArrayBuffer[(Double, Seq[GridPosition])]()
    while (change) {
      change = false
      val flowGraph = flowValuesToGraph(flowValues)
      //pozycje startowe jeszcze nie pokryte w calosci przez sciezki
      val startingPoints = game.getDefenderStartingPositions(sparsity).filter(s => flowGraph.contains(GridSpacetime(0, s)))
      var result = List[(GridSpacetime, Double)]()
      if (startingPoints.nonEmpty) {
        change = true
        var p = flowGraph.filter(_._1.time == 0).keys.head
        result = result :+ (p, 1.0)
        //Bierzemy pierwsza lepsza sciezke
        while (flowGraph.contains(p)) {
          val next = flowGraph(p).head
          result = result :+ next
          p = next._1
        }
        //Minimalny coverage wzdluz sciezki
        val minProb = result.map(_._2).min
        //zmniejszamy coverage wzdluz sciezki o minimalny
        result.zip(result.tail).foreach {
          case ((from, _), (to, _)) => flowValues(Flow(from.position, to.position, from.time)) -= minProb
        }
        val path = (minProb, result.map { case (gridSpaceTime, _) => gridSpaceTime.position })
        paths += sparsePathToReal(path, sparsity, game.getTimeSteps(sparsity = 1))

      }
    }
    //sciezki rozdzielone na obronce
    val pathPerDefender = mutable.ArrayBuffer[Seq[(Double, Seq[GridPosition])]]()
    val defenderStarts = game.getDefenderStartingPositions(sparsity).map(p => sparseToPosition(p, sparsity))
    for (s <- defenderStarts.distinct) {
      val pathsStartingFromPos = paths.filter(_._2.head == s)
      val defenderCountFromPos = defenderStarts.count(_ == s)
      (1 to defenderCountFromPos).foreach(_ => pathPerDefender += pathsStartingFromPos.map(p => (p._1 / defenderCountFromPos, p._2)))
    }

    val mixedStrategy = combs(pathPerDefender).map(strategy => {
      val prob = strategy.map(_._1).foldLeft(1.0)(_ * _)
      //zamiana listy sciezek na liste pozycji
      val positions = strategy.map(_._2).transpose.map(_.toList).tail.toList //tail bo pomijamy pierwsza pozycje (ta startowa)
      (prob, positions)
    }).toList

    //powielenie sciezek, aby pokrywaly caly zagregowany kwadrat
    mixedStrategy.flatMap {
      case (prob, positions) =>
        positions.map(p => p.map(getSparseGridForPosition(_, sparsity).map(gridPos => {
          val realPos = game.gridToRealPosition(gridPos)
          Position(realPos.x, realPos.y)
        })).transpose).transpose.map(PureStrategy(prob / (sparsity * sparsity), _))
    }
  }
}
