
package de.ivu.elect.business.sitzberechnung.control.varianten;

import static java.math.BigInteger.ONE;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import de.ivu.elect.business.ergebnis.entity.ErgebnisLogEintrag;
import de.ivu.elect.business.ergebnis.entity.ErgebnisLogEintragArt;
import de.ivu.elect.business.ergebnis.entity.Gewaehlt;
import de.ivu.elect.business.ergebnis.entity.GewaehltStatus;
import de.ivu.elect.business.ergebnis.entity.Sitze;
import de.ivu.elect.business.ergebniskonflikt.control.util.ErgebnisKonfliktLoeser;
import de.ivu.elect.business.ergebniskonflikt.entity.ErgebnisKonflikt;
import de.ivu.elect.business.gruppeimgebiet.entity.GruppeImGebiet;
import de.ivu.elect.business.sitzberechnung.control.util.SitzberechnungLogger;
import de.ivu.elect.business.sitzberechnung.entity.HinweisAnVariantenberechner;
import de.ivu.elect.business.sitzberechnung.entity.SitzberechnungsalgorithmusKonfiguration;
import de.ivu.elect.business.sitzberechnung.entity.Sitzberechnungseingabe;
import de.ivu.elect.business.sitzberechnung.entity.Sitzberechnungsergebnis;

/**
 * Von einem Kern-Algorithmus wird "nur" erwartet, dass er im Fall eines ungelösten Konflikts ein "leeres" Ergebnis
 * (also ohne Sitze und Gewählte) zurückgibt. Eine "Was-wäre-wenn"-Betrachtung soll ein Kern-Algorithmus nicht
 * durchführen.
 * <p/>
 * Um im Fall von ungelösten Konflikten mehr über das mögliche Ergebnis der Sitzberechnung zu erfahren, wird die
 * Sitzberechnung iterativ (Back-Tracking, Tiefensuche) mehrfach aufgerufen. Bei ungelösten Konflikten werden dabei alle
 * möglichen Konfliktlösungen "ausprobiert", durch Optimierungen auch nur eine Teilmenge der möglichen Lösungen. Bei
 * Folge-Konflikten wird für diese wieder "ausprobiert" und so der Baum aller möglichen Varianten erzeugt.
 * <p/>
 * Den "Blättern" dieses Baums entsprechen die Berechnungen, bei denen alle Konflikte gelöst sind, so dass sich ein
 * reguläres Sitzberechnungsergebnis ergibt. Diese heißen auch "Varianten". Alle diese möglichen varianten-Ergebnisse
 * werden verglichen und zu einem "Gesamt-Ergebnis" zusammengefasst. Das Gesamt-Ergebnis umfasst
 * <ul>
 * <li>alle {@link Gewaehlt}-Objekte, die in allen Varianten-Ergebnissen gleich sind</li>
 * <li>{@link Gewaehlt}-Objekte mit Status {@link GewaehltStatus.LOS_OFFEN} für alle Kandidaturen, bei denen sich das
 * Ergebnis in den Varianten unterscheidet</li>
 * <li>alle {@link Sitze}-Objekte, die in allen Varianten-Ergebnissen gleich sind</li>
 * <li>keine {@link Sitze}-Objekte für alle {@link GruppeImGebiet}, bei denen sich das Ergebnis in den Varianten
 * unterscheidet</li>
 * <li>alle {@link ErgebnisKonflikt}e, die in mindestens einer Variante auftreten</li>
 * <li>Ein Ergebnis-Protokoll der ersten gefundenen Variante.</li>
 * <li>Nur wenn es einen ungelösten Konflikt gab: Zusätzliche Informationen des Varianteberechners:</li>
 * <li>Statistik der Variantenberechung</li>
 * <li>Information, welche Konflikte nur bedingt (also nicht in allen Varianten) auftreten (TODO ELECT-3379).</li>
 * <li>Information, für welche {@link GruppeImGebiet} kein {@link Sitze}-Objekt angezeigt wird, weil das Ergebnis nicht
 * feststeht (TODO ELECT-3379).</li>
 * </ul>
 * <p/>
 * Anforderungen an den Kern-Algorithmus:
 * <ul>
 * <li>Für jeden ungelösten Konflikt muss in der {@link Sitzberechnungsergebnis#konfliktLoeserMap} ein KonfliktLoeser
 * eingetragen sein.</li>
 * <li>Um Optimierung nutzen zu können, sollten für ungelöste Konflikte Hinweise im
 * {@link Sitzberechnungsergebnis#hinweiseAnVariantenberechner} gemacht werden.</li>
 * <li>Die Reihenfolge der Berechnungen sollte immer die gleiche sein, am besten sortiert nach fachlichen Kriterien,
 * notfalls sortiert nach technischen Schlüsseln. Dadurch treten auch Konflikte immer in der gleichen Reihenfolge auf.
 * Vorteil ist auch, dass das Protokoll immer die gleiche Reihenfolge hat.</li>
 * </ul>
 * 
 *
 * 
 * @param <K>
 *          Klasse zur Konfiguration des Sitzberechnungsalgorithmus
 */
public class Variantenberechner<K extends SitzberechnungsalgorithmusKonfiguration> implements Sitzberechnung<K> {

  private static final Logger LOG = LoggerFactory.getLogger(Variantenberechner.class);

  // Nur Default-Wert. Besser sitzberechnungseingabe.getKonfiguration().getMaximaleAnzahlSitzberechnungenInVariantenberechnung() verwenden.
  public static final int DEFAULT_MAX_ANZAHL_SITZBERECHNUNGEN = 100;

  private final Sitzberechnung<K> kern;
  private final Deque<SitzberechnungseingabeUndErgebnis<K>> deque = new LinkedList<>();
  private final SitzberechnungsergebnisVergleicher sitzberechnungsergebnisVergleicher = new SitzberechnungsergebnisVergleicher();
  private final List<ErgebnisKonflikt> alleKonflikte = new ArrayList<>();
  private List<ErgebnisLogEintrag> ergebnisLogEintraege = null;
  private final boolean isTiefensuche = true;

  private final VariantenStatistik variantenStatistik = new VariantenStatistik();
  private boolean berechnungAbbrechen = false;
  private Sitzberechnungsergebnis erstesErgebnis;

  public Variantenberechner(Sitzberechnung<K> kern) {
    this.kern = kern;
  }

  @Override
  public Sitzberechnungsergebnis fuehreSitzberechnungDurch(Sitzberechnungseingabe<K> sitzberechnungseingabe) {
    deque.push(new SitzberechnungseingabeUndErgebnis<>(sitzberechnungseingabe, ONE));
    variantenStatistik.incrementAnzahlDurchzufuehrendeSitzberechnungenBy(1);

    while (!deque.isEmpty() && !berechnungAbbrechen) {
      SitzberechnungseingabeUndErgebnis<K> next = deque.pop();

      // Das Protokoll der ersten Variante wird gemerkt. Danach muss kein Protokoll mehr erstellt werden.
      boolean beiNaechsterBerechnungProtokollErstellen = (ergebnisLogEintraege == null);
      variantenStatistik.incrementAnzahlDurchgefuehrteSitzberechnungen();
      next.fuehreSitzberechnungDurch(kern, beiNaechsterBerechnungProtokollErstellen);
      if (erstesErgebnis == null) {
        // Merke das erste Ergebnis. Wenn die Variantenberechnung abgebrochen werden muss, kann man das immer noch verwenden.
        erstesErgebnis = next.getSitzberechnungsergebnis();
      }

      sammleAlleKonflikte(next.getSitzberechnungsergebnis().getKonflikte());
      if (next.sindAlleKonflikteGeloest()) {
        varianteGefunden(next);
      } else {
        ungeloesteKonflikteGefunden(next);
      }
    }

    logVariantenStatistik();

    if (berechnungAbbrechen) {
      // Da die Variantenberechnung abgebrochen wurde, wird nicht das Protokoll der ersten Variante verwendet,
      // sondern das Protokoll der ersten Berechnung überhaupt.
      ergebnisLogEintraege = new ArrayList<>(erstesErgebnis.getErgebnisLogEintraege());
      schreibeInsBerechnungsProtokoll(sitzberechnungseingabe);

      Sitzberechnungsergebnis result = new Sitzberechnungsergebnis(erstesErgebnis.getSitze(),
          erstesErgebnis.getGewaehlte(), erstesErgebnis.getKonflikte(), ergebnisLogEintraege,
          erstesErgebnis.getDHondtQuotienten(), variantenStatistik, erstesErgebnis.getBemerkung());
      return result;
    } else {
      schreibeInsBerechnungsProtokoll(sitzberechnungseingabe);

      Sitzberechnungsergebnis result = sitzberechnungsergebnisVergleicher.getSitzberechnungsergebnis(alleKonflikte, ergebnisLogEintraege, variantenStatistik);
      return result;
    }
  }

  private void sammleAlleKonflikte(List<ErgebnisKonflikt> konflikte) {
    for (ErgebnisKonflikt konflikt : konflikte) {
      if (!enthaeltFachlichGleichenKonflikt(alleKonflikte, konflikt)) {
        alleKonflikte.add(konflikt);
      }
    }
  }

  private void logVariantenStatistik() {
    LOG.info("Durchgeführte Sitzberechnungen: " + variantenStatistik.getAnzahlDurchgefuehrteSitzberechnungen());
    LOG.info("Durchzuführende Sitzberechnungen: " + variantenStatistik.getAnzahlDurchzufuehrendeSitzberechnungen());
    LOG.info("Anzahl Varianten: " + variantenStatistik.getAnzahlVariantenErmittelt());
    LOG.info("Anzahl Varianten berechnet: " + variantenStatistik.getAnzahlVariantenBerechnet());
    LOG.info("Tiefe des Variantenbaums (= Anzahl ungelöster Konflikte), min: "
        + variantenStatistik.getMinimaleTiefeDesVariantenbaums() + ", max: "
        + variantenStatistik.getMaximaleTiefeDesVariantenbaums());
  }

  /**
   * Versieht das Protokoll in <code>ergebnisLogEintraege</code> mit einen "Vorspann" mit Informationen des
   * Variantenberechners
   */
  private void schreibeInsBerechnungsProtokoll(Sitzberechnungseingabe<K> sitzberechnungseingabe) {
    if (variantenStatistik.getAnzahlDurchgefuehrteSitzberechnungen() == 1
        || variantenStatistik.getAnzahlVariantenBerechnet() == 1) {
      // Normale Berechnung ohne offenen Konflikt -> kein Vorspann
      return;
    }

    SitzberechnungLogger logger = new SitzberechnungLogger(sitzberechnungseingabe.getKonfiguration().getMessages(),
        true);
    // Varianten
    logger.log(ErgebnisLogEintragArt.UEBERSCHRIFT1, "sitzberechnung.algorithmus.protokoll.variantenberechnung.title");
    // Das Ergebnis der Sitzverteilung steht noch nicht eindeutig fest. Es gibt noch offene Losentscheide.
    logger.log(ErgebnisLogEintragArt.INFO, "sitzberechnung.algorithmus.protokoll.variantenberechnung.durchgefuehrt.1");
    // Um die möglichen Ergebnisse der Sitzverteilung zu ermitteln, wurden die offenen Losentscheide auf unterschiedliche Weise automatisch entschieden. Die Ergebnisse wurden verglichen.
    logger.log(ErgebnisLogEintragArt.INFO, "sitzberechnung.algorithmus.protokoll.variantenberechnung.durchgefuehrt.2");
    long min = variantenStatistik.getMinimaleTiefeDesVariantenbaums();
    long max = variantenStatistik.getMaximaleTiefeDesVariantenbaums();
    if (min == max) {
      // Um zu einem Ergebnis zu kommen, mussten {0} offene Losentscheide entschieden werden.
      logger.log(ErgebnisLogEintragArt.INFO,
          "sitzberechnung.algorithmus.protokoll.variantenberechnung.tiefe.des.variantenbaums", min);
    } else {
      // Um zu einem Ergebnis zu kommen, mussten zwischen {0} und {1} offene Losentscheide entschieden werden.
      logger.log(ErgebnisLogEintragArt.INFO,
          "sitzberechnung.algorithmus.protokoll.variantenberechnung.tiefe.des.variantenbaums.min.max", min, max);
    }
    // Es gibt insgesamt {0} Varianten (mögliche Kombinationen, wie die offenen Losentscheide gelöst werden können).
    logger.log(ErgebnisLogEintragArt.INFO, "sitzberechnung.algorithmus.protokoll.variantenberechnung.anzahl.varianten",
        variantenStatistik.getAnzahlVariantenErmittelt());
    // {0} dieser Varianten wurden berechnet und verglichen.
    logger.log(ErgebnisLogEintragArt.INFO,
        "sitzberechnung.algorithmus.protokoll.variantenberechnung.anzahl.varianten.berechnet",
        variantenStatistik.getAnzahlVariantenBerechnet());

    if (berechnungAbbrechen) {
      long maxAnzahlSitzberechnungen = sitzberechnungseingabe.getKonfiguration()
          .getMaximaleAnzahlSitzberechnungenInVariantenberechnung();
      // Die Anzahl der erforderlichen Sitzberechnungen ({0}) hat den zulässigen Höchstwert {1} überschritten. Die Berechnung weiterer Varianten wird abgebrochen.
      logger.log(ErgebnisLogEintragArt.WARNUNG, "sitzberechnung.algorithmus.protokoll.variantenberechnung.abgebrochen",
          variantenStatistik.getAnzahlDurchzufuehrendeSitzberechnungen(), maxAnzahlSitzberechnungen);
      // Die Listen der gewählten Kandidaten und Sitze der politischen Gruppen wird aus diesem Grund leer oder unvollständig angezeigt.
      logger.log(ErgebnisLogEintragArt.INFO,
          "sitzberechnung.algorithmus.protokoll.variantenberechnung.sitze.und.gewaehlte.unvollstaendig");
      // Setzen Sie den Höchstwert für die Anzahl der Sitzberechnungen hoch oder lösen Sie Losentscheide manuell, um die Berechnung fortzusetzen.
      logger.log(ErgebnisLogEintragArt.INFO,
          "sitzberechnung.algorithmus.protokoll.variantenberechnung.parameter.hochsetzen.oder.konflikte.loesen");
      // Das folgende Protokoll der Sitzberechnung zeigt NUR DEN VERLAUF bis zum ersten offenen Losentscheid.
      logger.log(ErgebnisLogEintragArt.INFO,
          "sitzberechnung.algorithmus.protokoll.variantenberechnung.abgebrochen.protokoll");
    } else {

      // Das folgende Protokoll der Sitzberechnung zeigt NUR EINEN MÖGLICHEN VERLAUF der Berechnung.
      logger
          .log(ErgebnisLogEintragArt.INFO, "sitzberechnung.algorithmus.protokoll.variantenberechnung.durchgefuehrt.3");
      // Auf offene Losentscheide, die beispielhaft automatisch gelöst wurden, wird entsprechend hingewiesen.
      logger
          .log(ErgebnisLogEintragArt.INFO, "sitzberechnung.algorithmus.protokoll.variantenberechnung.durchgefuehrt.4");
    }

    // Zusätzliche Log-Einträge vorne anhängen
    List<ErgebnisLogEintrag> tmp = new ArrayList<>();

    List<ErgebnisLogEintrag> logDesVariantenberechners = logger.getErgebnisLogEintraege();
    // Zuerste das Beispielhafte log des Algorithmus (die erste Variante, die berechnet wurde)
    tmp.addAll(ergebnisLogEintraege);
    // Dann das Log des Variantenberechners mit den Meta-Betrachtungen
    tmp.addAll(logDesVariantenberechners);

    ergebnisLogEintraege = tmp;
  }

  private void varianteGefunden(SitzberechnungseingabeUndErgebnis<K> next) {
    variantenStatistik.varianteGefunden(next);

    sitzberechnungsergebnisVergleicher.add(next.getSitzberechnungsergebnis());
    if (ergebnisLogEintraege == null) {
      ergebnisLogEintraege = new ArrayList<>(next.getSitzberechnungsergebnis().getErgebnisLogEintraege());
    }
  }

  /**
   * Die Sitzberechnung mit den Daten von next hat noch zu ungelösten Konflikten geführt. Lege die weiter zu
   * untersuchenden Alternativen auf den "Stapel durchzuführender Berechnungen".
   */
  private void ungeloesteKonflikteGefunden(SitzberechnungseingabeUndErgebnis<K> next) {
    List<ErgebnisKonflikt> geloesteKonflikte = new ArrayList<>();
    List<ErgebnisKonflikt> ungeloesteKonflikte = new ArrayList<>();
    // Sammle alle gelösten eingehenden Konflikte des letzten Aufrufs der Sitzberechnung
    for (ErgebnisKonflikt konflikt : next.getSitzberechnungseingabe().getKonflikte()) {
      if (konflikt.isGeloest()) {
        geloesteKonflikte.add(konflikt);
      }
    }
    // Sammle außerdem gelöste ausgehende Konflikte, falls sie wirklich neu sind
    for (ErgebnisKonflikt konflikt : next.getSitzberechnungsergebnis().getKonflikte()) {
      if (konflikt.isGeloest()) {
        if (!enthaeltFachlichGleichenKonflikt(geloesteKonflikte, konflikt)) {
          geloesteKonflikte.add(konflikt);
        }
      } else {
        // ... und die ungelösten Konflikte
        ungeloesteKonflikte.add(konflikt);
      }
    }

    if (ungeloesteKonflikte.size() > 1) {
      LOG.warn("Es gibt mehr als einen ungelösten Konflikt");
    }
    ErgebnisKonflikt ungeloesterKonflikt = ungeloesteKonflikte.iterator().next();
    HinweisAnVariantenberechner hinweis = next.getSitzberechnungsergebnis().getHinweiseAnVariantenberechner()
        .get(ungeloesterKonflikt);
    ErgebnisKonfliktLoeser konfliktLoeser = next.getSitzberechnungsergebnis().getKonfliktLoeserMap()
        .get(ungeloesterKonflikt);
    long maxAnzahlSitzberechnungen = next.getSitzberechnungseingabe().getKonfiguration()
        .getMaximaleAnzahlSitzberechnungenInVariantenberechnung();

    List<SitzberechnungseingabeUndErgebnis<K>> toDeque = new ArrayList<>();
    final BigInteger anzahlLoesungenExakt;
    if (HinweisAnVariantenberechner.ZYKLISCHE_LOESUNGEN_ZEIGEN_ALLE_AUSWIRKUNGEN.equals(hinweis)) {
      // Optimierung: Nur 1 bis 2 zyklische Lösungen ausprobieren
      for (int indexDerLoesung : next.getErforderlicheZyklischeLoesungen()) {
        BigInteger zaehltFuerAnzahlVarianten = BigInteger.ZERO;
        ErgebnisKonflikt alternative = ungeloesterKonflikt.cloneOhneLoesung();
        if (indexDerLoesung == 0) {
          zaehltFuerAnzahlVarianten = next.getZaehltFuerAnzahlVarianten().multiply(
              konfliktLoeser.getAnzahlLoesungen(alternative));
        }
        konfliktLoeser.loeseKonfliktZyklischFuerVariantenberechnung(alternative, indexDerLoesung, next.getStimmergebnisDaten(), next.getSitzberechnungseingabe().getKonfiguration().getMessages());
        List<ErgebnisKonflikt> neueKonflikte = new ArrayList<>(geloesteKonflikte);
        neueKonflikte.add(alternative);
        Sitzberechnungseingabe<K> neueSitzberechnungseingabe = getSitzberechnungseingabeMitKonflikten(
            next.getSitzberechnungseingabe(), neueKonflikte);
        SitzberechnungseingabeUndErgebnis<K> sitzberechnungseingabeUndErgebnis = new SitzberechnungseingabeUndErgebnis<>(
            neueSitzberechnungseingabe, zaehltFuerAnzahlVarianten, indexDerLoesung);
        toDeque.add(sitzberechnungseingabeUndErgebnis);
      }
      anzahlLoesungenExakt = BigInteger.valueOf(toDeque.size());
    } else {
      // Keine Optimierung: Probiert alle möglichen Lösungen durch, 
      // aber bereite die Berechnung für höchstens die ersten MAX_ANZAHL_SITZBERECHNUNGEN + 1 vor.
      anzahlLoesungenExakt = konfliktLoeser.getAnzahlLoesungen(ungeloesterKonflikt);
      int anzahlLoesungen = anzahlLoesungenExakt.min(BigInteger.valueOf(maxAnzahlSitzberechnungen + 1)).intValue();
      for (int indexDerLoesung = 0; indexDerLoesung < anzahlLoesungen; indexDerLoesung++) {
        // Für jede mögliche Lösung des Konflikts bereite eine Sitzberechnungseingabe vor.
        ErgebnisKonflikt alternative = ungeloesterKonflikt.cloneOhneLoesung();
        konfliktLoeser.loeseKonfliktFuerVariantenberechnung(alternative, indexDerLoesung, next.getStimmergebnisDaten(), next.getSitzberechnungseingabe().getKonfiguration().getMessages());
        List<ErgebnisKonflikt> neueKonflikte = new ArrayList<>(geloesteKonflikte);
        neueKonflikte.add(alternative);
        Sitzberechnungseingabe<K> neueSitzberechnungseingabe = getSitzberechnungseingabeMitKonflikten(
            next.getSitzberechnungseingabe(), neueKonflikte);
        SitzberechnungseingabeUndErgebnis<K> sitzberechnungseingabeUndErgebnis = new SitzberechnungseingabeUndErgebnis<>(
            neueSitzberechnungseingabe, next.getZaehltFuerAnzahlVarianten(), next.getVorgabeBeiZyklischerLoesung());
        toDeque.add(sitzberechnungseingabeUndErgebnis);
      }
    }

    variantenStatistik.incrementAnzahlDurchzufuehrendeSitzberechnungenBy(anzahlLoesungenExakt);
    if (isTiefensuche) {
      // Deque als Stack verwenden (LIFO)
      Collections.reverse(toDeque);
      for (SitzberechnungseingabeUndErgebnis<K> each : toDeque) {
        deque.addFirst(each);
      }
    } else {
      // Deque als Queue verwenden (FIFO)
      deque.addAll(toDeque);
    }

    if (variantenStatistik.getAnzahlDurchzufuehrendeSitzberechnungen() > maxAnzahlSitzberechnungen) {
      LOG.warn("Die Variantenberechnung wird abgebrochen, da die erlaubte Anzahl (" + maxAnzahlSitzberechnungen
          + ") von Sitzberechnungen bei der Variantenberechnung überschritte wurde: "
          + variantenStatistik.getAnzahlDurchzufuehrendeSitzberechnungen());
      berechnungAbbrechen = true;
    }
  }

  Sitzberechnungseingabe<K> getSitzberechnungseingabeMitKonflikten(
      Sitzberechnungseingabe<K> originalSitzberechnungseingabe, List<ErgebnisKonflikt> konflikte) {
    return new Sitzberechnungseingabe<K>(originalSitzberechnungseingabe, konflikte);
  }

  private boolean enthaeltFachlichGleichenKonflikt(List<ErgebnisKonflikt> geloesteKonflikte, ErgebnisKonflikt konflikt) {
    for (ErgebnisKonflikt each : geloesteKonflikte) {
      if (each.isFachlichGleicherKonflikt(konflikt)) {
        return true;
      }
    }
    return false;
  }

  public VariantenStatistik getVariantenStatistik() {
    return variantenStatistik;
  }
}
