import { leiteAb } from '../geometrie/ableitung';
import { buildSignalPlan } from './signalPlan';
import { createPhase } from '../model/factory';
import type { Project } from '../model/project';
import type { Seconds } from '../units';

/**
 * Zulaessige Phaseneinteilungen aufzaehlen und reihen.
 *
 * DIE BEDINGUNG, UNTER DER ES DIESES MODUL UEBERHAUPT GEBEN DARF, und sie ist
 * keine Feinheit: Eine Reihung nach kleinster Umlaufzeit bevorzugt WENIGE
 * Phasen, also viele gleichzeitig freigegebene Signalgruppen. Gleichzeitigkeit
 * ist im Datenbestand aber schon dann erlaubt, wenn kein Konflikt ERFASST ist -
 * "geprueft vertraeglich" und "noch nicht betrachtet" sehen darin gleich aus.
 * Mit jedem entfallenden Phasenuebergang faellt zudem eine Zwischenzeit
 * ersatzlos weg.
 *
 * Deshalb: OHNE POSITIVEN BELEG DER VERTRAEGLICHKEIT JEDES PAARES ERSCHEINT
 * KEIN EINZIGER VORSCHLAG. Nicht ein gekennzeichneter, nicht ein grauer - gar
 * keiner. Statt dessen sagt die Auskunft, welche Paare unbelegt sind.
 *
 * WOHER DER BELEG KOMMT (Weg A des Befunds, ohne Schemasprung): aus dem
 * massstaeblich auswertbaren Lageplan. Kreuzen sich die gezeichneten Fahrlinien
 * zweier Gruppen nicht, ist das eine Aussage ueber die Oertlichkeit und keine
 * Abwesenheit einer Eingabe. Wo kein solcher Lageplan vorliegt, gibt es diese
 * Auskunft nicht - und dann eben keine Vorschlaege.
 */

/** Wie die Vertraeglichkeit eines Paares belegt ist. */
export type Belegart = 'feindlich' | 'belegt' | 'ohne-beleg';

export interface Paarbeleg {
  readonly aId: string;
  readonly bId: string;
  readonly aName: string;
  readonly bName: string;
  readonly art: Belegart;
  readonly grund: string;
}

export interface Belegstand {
  readonly paare: readonly Paarbeleg[];
  /** Die Paare, die den Vorschlaegen im Weg stehen. */
  readonly ohneBeleg: readonly Paarbeleg[];
  readonly vollstaendig: boolean;
}

/**
 * Wieviele Einteilungen hoechstens aufgezaehlt werden.
 *
 * GEZAEHLT WIRD, BEVOR AUFGEZAEHLT WIRD (zweites Risiko des Befunds): Der
 * Suchraum haengt an der Zahl der ERFASSTEN Konflikte, nicht an der Zahl der
 * Gruppen - ausgerechnet das schlecht gepflegte Projekt haette den groessten
 * Suchraum und bekaeme die meisten Vorschlaege. Beide Schranken sind gesetzt
 * und stammen aus keinem Regelwerk.
 */
export const MAX_PHASENMENGEN = 400;
export const MAX_VORSCHLAEGE = 12;

export interface Phasenvorschlag {
  /** Die Signalgruppen je Phase, in der Reihenfolge des Vorschlags. */
  readonly phasen: readonly (readonly string[])[];
  readonly umlaufzeit: Seconds;
  /** Entspricht der Vorschlag der heutigen Einteilung des Projekts? */
  readonly heutige: boolean;
}

export type Suchhindernis = 'ohne-beleg' | 'zu-wenige-gruppen' | 'zu-viele-moeglichkeiten';

export interface Einteilungssuche {
  readonly hindernis: Suchhindernis | null;
  readonly beleg: Belegstand;
  /** Wieviele Phasenmengen betrachtet wurden - die Zahl vor dem Aufzaehlen. */
  readonly phasenmengen: number;
  readonly vorschlaege: readonly Phasenvorschlag[];
}

function paarSchluessel(a: string, b: string): string {
  return a < b ? `${a}|${b}` : `${b}|${a}`;
}

/**
 * Der Belegstand jedes Signalgruppenpaares.
 *
 * Drei Faelle, und der dritte ist der wichtige:
 *   1. Eine erfasste Konfliktbeziehung - feindlich, und das ist eine Aussage.
 *   2. Der Lageplan zeigt kreuzungsfreie Fahrlinien beider Gruppen -
 *      vertraeglich, und auch das ist eine Aussage.
 *   3. Alles Uebrige - KEINE Aussage. Nicht "vertraeglich", sondern "nicht
 *      betrachtet".
 */
export function vertraeglichkeitsbelege(project: Project): Belegstand {
  const gruppen = project.signalGroups;
  const feindlich = new Set(project.conflicts.map((c) => paarSchluessel(c.fromId, c.toId)));

  const ableitung = leiteAb(project, project.lageplan);
  const linieZuGruppe = new Map(
    project.lageplan.linien
      .filter((l) => l.signalGroupId !== null)
      .map((l) => [l.id, l.signalGroupId!]),
  );
  /*
   * Je Gruppenpaar: Wieviele Linienpaare hat die Ableitung beurteilt, und
   * wieviele davon sprechen fuer Vertraeglichkeit? Ein einziges Paar mit
   * "kreuzt" oder "zu pruefen" verdirbt den Beleg - eine Gruppe faehrt so
   * viele Stroeme, wie sie fuehrt, und jeder einzelne muss vertraeglich sein.
   */
  const beurteilt = new Map<string, { gut: number; schlecht: number }>();
  for (const vorschlag of ableitung.vertraeglichkeit) {
    const a = linieZuGruppe.get(vorschlag.aLinieId);
    const b = linieZuGruppe.get(vorschlag.bLinieId);
    if (a === undefined || b === undefined || a === b) continue;
    const schluessel = paarSchluessel(a, b);
    const stand = beurteilt.get(schluessel) ?? { gut: 0, schlecht: 0 };
    if (!vorschlag.feindlich && !vorschlag.zuPruefen) stand.gut += 1;
    else stand.schlecht += 1;
    beurteilt.set(schluessel, stand);
  }

  const paare: Paarbeleg[] = [];
  for (let i = 0; i < gruppen.length; i += 1) {
    for (let j = i + 1; j < gruppen.length; j += 1) {
      const a = gruppen[i]!;
      const b = gruppen[j]!;
      const schluessel = paarSchluessel(a.id, b.id);
      const gemeinsam = { aId: a.id, bId: b.id, aName: a.name, bName: b.name };
      if (feindlich.has(schluessel)) {
        paare.push({
          ...gemeinsam,
          art: 'feindlich',
          grund: 'Als feindliche Beziehung erfasst.',
        });
        continue;
      }
      /*
       * KEIN ZWEITER VORBEHALT AUF `ableitung.auswertbar`: Ohne auswertbaren
       * Lageplan gibt `leiteAb` eine leere Vertraeglichkeitsliste zurueck, und
       * `beurteilt` ist dann leer - die Abfrage waere ein Zweig, den keine
       * Eingabe erreicht. Ein unerreichbarer Zweig sieht aus wie Vorsicht und
       * ist eine Luecke im Nachweis. Die Auswertbarkeit steht dafuer im Grund
       * des unbelegten Paares, wo sie der Bearbeiter braucht.
       */
      const stand = beurteilt.get(schluessel);
      if (stand !== undefined && stand.gut > 0 && stand.schlecht === 0) {
        paare.push({
          ...gemeinsam,
          art: 'belegt',
          grund: `Im Lageplan geprüft: ${String(stand.gut)} Strompaar(e), keine Kreuzung.`,
        });
        continue;
      }
      paare.push({
        ...gemeinsam,
        art: 'ohne-beleg',
        grund: !ableitung.auswertbar
          ? 'Kein maßstäblich auswertbarer Lageplan – die Verträglichkeit ist nicht belegt, ' +
            'sondern nur nicht erfasst.'
          : 'Für dieses Paar liegt keine geprüfte Aussage vor: Es fehlen gezeichnete Fahrlinien ' +
            'beider Gruppen, oder die Zeichnung ist uneindeutig.',
      });
    }
  }

  const ohneBeleg = paare.filter((p) => p.art === 'ohne-beleg');
  return { paare, ohneBeleg, vollstaendig: ohneBeleg.length === 0 };
}

/**
 * Alle maximalen Mengen paarweise vertraeglicher Gruppen (Bron-Kerbosch).
 *
 * MAXIMAL und nicht beliebig: Eine Phase, der sich eine weitere vertraegliche
 * Gruppe hinzufuegen liesse, verschenkt Freigabezeit - sie waere nie die
 * Antwort auf "welche Einteilung ergibt die kuerzeste Umlaufzeit". Die Suche
 * bricht ab, sobald `MAX_PHASENMENGEN` erreicht ist; die Zahl steht dann in
 * der Auskunft.
 */
export function maximaleMengen(
  ids: readonly string[],
  vertraeglich: (a: string, b: string) => boolean,
): { mengen: string[][]; abgebrochen: boolean } {
  const mengen: string[][] = [];
  let abgebrochen = false;

  const erweitere = (aktuell: string[], kandidaten: string[], geprueft: string[]): void => {
    if (abgebrochen) return;
    if (kandidaten.length === 0 && geprueft.length === 0) {
      mengen.push([...aktuell]);
      if (mengen.length >= MAX_PHASENMENGEN) abgebrochen = true;
      return;
    }
    const rest = [...kandidaten];
    const bereits = [...geprueft];
    for (const id of kandidaten) {
      erweitere(
        [...aktuell, id],
        rest.filter((k) => k !== id && vertraeglich(id, k)),
        bereits.filter((g) => vertraeglich(id, g)),
      );
      rest.splice(rest.indexOf(id), 1);
      bereits.push(id);
      // Der Uebersetzer sieht `abgebrochen` hier als unveraendert an: Gesetzt
      // wird es im rekursiven Aufruf darueber, und dessen Wirkung verfolgt die
      // Flussanalyse nicht. Ohne diese Abfrage laeuft die Suche nach dem
      // Abbruch weiter durch den ganzen Baum.
      // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition -- der rekursive Aufruf setzt das Merkmal; siehe darueber
      if (abgebrochen) return;
    }
  };

  erweitere([], [...ids], []);
  return { mengen, abgebrochen };
}

/** Alle Ueberdeckungen aus `anzahl` Mengen, die jede Gruppe erfassen. */
function ueberdeckungen(
  mengen: readonly (readonly string[])[],
  ids: readonly string[],
  anzahl: number,
  hoechstens: number,
): string[][][] {
  const treffer: string[][][] = [];
  const waehle = (ab: number, gewaehlt: (readonly string[])[], abgedeckt: Set<string>): void => {
    if (treffer.length >= hoechstens) return;
    if (gewaehlt.length === anzahl) {
      if (abgedeckt.size === ids.length) treffer.push(gewaehlt.map((m) => [...m]));
      return;
    }
    for (let i = ab; i < mengen.length; i += 1) {
      const menge = mengen[i]!;
      /*
       * BESCHNITTEN WIRD NUR, WAS NICHTS BEITRAEGT: Eine Menge, deren Gruppen
       * alle schon abgedeckt sind, macht die Ueberdeckung nicht vollstaendiger
       * - sie erzeugte nur dieselbe Loesung mit einer Phase mehr. Ueber die
       * VOLLSTAENDIGKEIT entscheidet allein die Abfrage oben; dieses
       * Beschneiden ist eine Abkuerzung und darf das Ergebnis nicht aendern.
       */
      const naechste = new Set([...abgedeckt, ...menge]);
      if (naechste.size === abgedeckt.size) continue;
      waehle(i + 1, [...gewaehlt, menge], naechste);
      if (treffer.length >= hoechstens) return;
    }
  };
  waehle(0, [], new Set());
  return treffer;
}

/** Die Umlaufzeit, die eine Einteilung ergibt - am wirklichen Planaufbau. */
function umlaufzeitVon(project: Project, phasen: readonly (readonly string[])[]): Seconds {
  const angelegt = phasen.map((gruppen, index) =>
    createPhase(`Phase ${String(index + 1)}`, [...gruppen]),
  );
  const probe: Project = {
    ...project,
    phases: angelegt,
    program: { ...project.program, phaseOrder: angelegt.map((p) => p.id) },
  };
  return buildSignalPlan(probe).cycleTime;
}

/** Die heutige Einteilung als Mengen von Gruppenkennungen. */
function heutigeEinteilung(project: Project): Set<string> {
  return new Set(project.phases.map((p) => [...p.signalGroupIds].sort().join('|')));
}

/**
 * Sucht zulaessige Phaseneinteilungen und reiht sie nach Umlaufzeit.
 *
 * Gibt IMMER eine Auskunft zurueck - auch die, dass keine Vorschlaege gemacht
 * werden. Ein leeres Ergebnis ohne Grund waere hier das Schlimmste: Der
 * Bearbeiter hielte es fuer "es gibt keine".
 */
export function sucheEinteilungen(project: Project): Einteilungssuche {
  const beleg = vertraeglichkeitsbelege(project);
  const ids = project.signalGroups.map((g) => g.id);

  if (ids.length < 2) {
    return { hindernis: 'zu-wenige-gruppen', beleg, phasenmengen: 0, vorschlaege: [] };
  }
  if (!beleg.vollstaendig) {
    return { hindernis: 'ohne-beleg', beleg, phasenmengen: 0, vorschlaege: [] };
  }

  const belegt = new Set(
    beleg.paare.filter((p) => p.art === 'belegt').map((p) => paarSchluessel(p.aId, p.bId)),
  );
  const vertraeglich = (a: string, b: string): boolean => belegt.has(paarSchluessel(a, b));

  const { mengen, abgebrochen } = maximaleMengen(ids, vertraeglich);
  if (abgebrochen) {
    return {
      hindernis: 'zu-viele-moeglichkeiten',
      beleg,
      phasenmengen: mengen.length,
      vorschlaege: [],
    };
  }

  /*
   * Von der kleinsten Phasenzahl aufwaerts, hoechstens eine Stufe weiter: Der
   * Vorschlag mit den wenigsten Phasen ist der mit den wenigsten Uebergaengen,
   * und die naechste Stufe zeigt, was eine zusaetzliche Phase kostet. Alles
   * darueber waere eine Liste ohne Aussage.
   */
  const gefunden: string[][][] = [];
  let ersteStufe: number | null = null;
  for (let k = 1; k <= Math.min(mengen.length, ids.length); k += 1) {
    if (ersteStufe !== null && k > ersteStufe + 1) break;
    const treffer = ueberdeckungen(mengen, ids, k, MAX_VORSCHLAEGE - gefunden.length);
    if (treffer.length > 0 && ersteStufe === null) ersteStufe = k;
    gefunden.push(...treffer);
    if (gefunden.length >= MAX_VORSCHLAEGE) break;
  }

  const heute = heutigeEinteilung(project);
  const vorschlaege = gefunden
    .map((phasen) => ({
      phasen,
      umlaufzeit: umlaufzeitVon(project, phasen),
      heutige:
        phasen.length === heute.size && phasen.every((p) => heute.has([...p].sort().join('|'))),
    }))
    // Nach Umlaufzeit, bei Gleichstand nach der Zahl der Phasen: Zwei
    // Einteilungen mit derselben Umlaufzeit unterscheiden sich in den
    // Uebergaengen, und weniger Uebergaenge sind weniger Zwischenzeiten.
    .sort((a, b) => a.umlaufzeit - b.umlaufzeit || a.phasen.length - b.phasen.length);

  return { hindernis: null, beleg, phasenmengen: mengen.length, vorschlaege };
}

/** Klartext zu einem Hindernis - eine Stelle fuer Ansicht und Ausdruck. */
export const SUCHHINDERNIS_TEXT: Readonly<Record<Suchhindernis, string>> = {
  'ohne-beleg':
    'Für mindestens ein Signalgruppenpaar ist die Verträglichkeit nicht belegt. Solange das so ' +
    'ist, wird keine einzige Einteilung vorgeschlagen: Ein Vorschlag würde Gruppen gleichzeitig ' +
    'freigeben, von denen niemand geprüft hat, ob sie sich vertragen – und mit jedem ' +
    'entfallenden Phasenübergang fiele eine Zwischenzeit ersatzlos weg.',
  'zu-wenige-gruppen': 'Für eine Phaseneinteilung braucht es mindestens zwei Signalgruppen.',
  'zu-viele-moeglichkeiten':
    'Dieses Projekt lässt zu viele Phasenmengen zu, als dass eine Aufzählung eine Hilfe wäre. ' +
    'Das spricht in der Regel für zu wenige erfasste Konfliktbeziehungen: Je weniger Konflikte ' +
    'erfasst sind, desto mehr Gruppen gelten als gleichzeitig freigebbar.',
};