
package de.ivu.elect.sitzberechnung.math;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;

/**
 * Dieses Utility hilft bei der Aufgabe, aus einer gegebenen Rangfolge die vorderen <i>n</i> auszuwählen, wobei <i>n</i>
 * eine vorgegebene ganze Zahl ist. In der Rangfolge können Elemente gleich sein. Falls an der Grenze zwischen den
 * "Vorderen" und den "Hinteren" mehrere Elemente auf dem gleichen Rang stehen, kann es zu Losentscheiden kommen.
 * 
 *
 * @see NachStimmenSortierer
 */
public class VordereInRangfolgeErmittler<T> {

  private final List<T> vordere = new ArrayList<>();
  private final List<T> unentschiedene = new ArrayList<>();
  private final List<T> hintere = new ArrayList<>();
  private final int anzahlSitze;
  private final int anzahlUnverteilterSitze;

  /**
   * @param unsorted
   *          Liste von Objekten, die mit ihrer natürlichen Ordnung sortiert werden sollen
   */
  public static <T extends Comparable< ? super T>> VordereInRangfolgeErmittler<T> ermittleVordereInRangfolge(
      List<T> unsorted, long anzahlSitze) {
    return new VordereInRangfolgeErmittler<>(unsorted, new NaturalComparator<>(), anzahlSitze);
  }
 
  /**
   * @param Map
   *          Map mit von Objekten, deren Rangfolge bestimmt werden soll, als <code>key</code>s und deren "Wert" (z.B.
   *          Anzahl Stimmen) als <code>value</code>s.
   * @param <T>
   *          Typ der Objekte, deren Rangfolge bestimmt werden soll
   * @param <N>
   *          nach den Werten dieses Typs wird absteigend sortiert. N ist üblicherweise ein Subtyp von Number, der die
   *          Stimmenzahl angibt
   */
  public static <T, N extends Comparable< ? super N>> VordereInRangfolgeErmittler<T> ermittleVordereInRangfolge(
      Map<T, N> map, long anzahlSitze) {

    List<T> unsorted = new ArrayList<>(map.keySet());
    Comparator<T> comparator = new ComparatorByValue<>(map, null).reversed();
    return new VordereInRangfolgeErmittler<>(unsorted, comparator, anzahlSitze);
  }

  public VordereInRangfolgeErmittler(List<T> list, Comparator<T> comparator, long anzahl) {
    assert anzahl >= 0 : "Anzahl Sitze darf nicht negativ sein";
    anzahlSitze = (int) anzahl;
    List<T> sorted = new ArrayList<>(list);
    Collections.sort(sorted, comparator);
    if (anzahlSitze >= sorted.size()) {
      vordere.addAll(sorted);
    } else {
      T vergleichsElement = sorted.get(this.anzahlSitze);

      for (T element : sorted) {
        int compared = comparator.compare(element, vergleichsElement);
        if (compared < 0) {
          vordere.add(element);
        } else if (compared == 0 && vordere.size() < this.anzahlSitze) {
          unentschiedene.add(element);
        } else {
          hintere.add(element);
        }
      }
    }

    anzahlUnverteilterSitze = this.anzahlSitze - vordere.size();
  }

  /**
   * @return die sortierte Liste der Elemente, die auf jeden Fall zu den <code>anzahlSitze</code> vordersten gehören
   */
  public List<T> getVordere() {
    return vordere;
  }

  /**
   * @return die Liste der Elemente, die in der Rangfolge gleich sind und nur zum Teil zu den <code>anzahlSitze</code>
   *         vordersten gehören können.
   */
  public List<T> getUnentschiedene() {
    return unentschiedene;
  }

  /**
   * @return die sortierte Liste der Elemente, die auf keinen Fall zu den <code>anzahlSitze</code> vordersten gehören
   */
  public List<T> getHintere() {
    return hintere;
  }

  public int getAnzahlSitze() {
    return anzahlSitze;
  }

  public int getAnzahlUnverteilterSitze() {
    return anzahlUnverteilterSitze;
  }

  /**
   * @return <code>true</code>, wenn kein Losentscheid mehr nötig ist
   */
  public boolean isEntschieden() {
    return unentschiedene.isEmpty();
  }

  /**
   * @return <code>true</code>, wenn die Rangfolge nicht genügend Elemente enthalten hat
   */
  public boolean isErschoepft() {
    return isEntschieden() && anzahlUnverteilterSitze > 0;
  }

  private static class NaturalComparator<T2 extends Comparable< ? super T2>> implements Comparator<T2> {

    @Override
    public int compare(T2 x, T2 y) {
      return x.compareTo(y);
    }
  }
}
