import { Node } from "prosemirror-model";
import { mutatingSortedInsert } from "@heydovetail/array";
import { encodeToPlainSingleLine, EncodeToPlainSingleLineConstraints } from "./encodeToPlainSingleLine";
import { groupBy } from "./iter";
import * as set from "./set";
import { sortComparatorAsc } from "@heydovetail/array";

export interface Range {
  id: string;
  from: number;
  to: number;
}

export interface Label {
  id: string;
  rangeId: string;
}

export interface Segment {
  rangeId?: string;
  labelIds: ReadonlySet<string>;
  text: string;
  textAfter: string;
  textBefore: string;
}

/**
 * Slice a node into segments, returning an array of combinations.
 */
export function segmentRanges(
  node: Node,
  ranges: ReadonlyArray<Range>,
  labels: ReadonlyArray<Label>,
  options: {
    constraints?: EncodeToPlainSingleLineConstraints;
  } = {}
): Array<Segment> {
  // Examples:
  //
  // Single non-overlapping:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a"], text: "brown fox jumped", … }
  //     ]
  //
  // ----
  //
  // Multiple non-overlapping:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       } {   b  }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a"], text: "brown fox jumped", … },
  //       { labelIds: ["b"], text: "over the", … }
  //     ]
  //
  // ----
  //
  // Two overlapping ends:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //                       {       b     }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a"],      text: "brown fox jumped", … },
  //       { labelIds: ["a", "b"], text: "jumped", … },
  //       { labelIds: ["b"],      text: "jumped over the", … }
  //     ]
  //
  // ----
  //
  // One encompases another:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //             {          b        }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a", "b"], text: "brown fox jumped", … },
  //       { labelIds: ["b"],      text: "brown fox jumped over", … }
  //     ]
  //
  // ----
  //
  // One encompases another, encompased by another:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //             {          b        }
  //             {            c          }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a", "b", "c"], text: "brown fox jumped", … },
  //       { labelIds: ["b", "c"],      text: "brown fox jumped over", … }
  //       { labelIds: ["c"],           text: "brown fox jumped over the", … }
  //     ]
  //
  // ----
  //
  // 3 overlapping (offset):
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //                   {      b      }
  //                       {     c       }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a"],           text: "brown fox jumped", … },
  //       { labelIds: ["a", "b"],      text: "fox jumped", … },
  //       { labelIds: ["a", "b", "c"], text: "jumped", … },
  //       { labelIds: ["b"],           text: "fox jumped over", … }
  //       { labelIds: ["b", "c"],      text: "jumped over", … }
  //       { labelIds: ["c"],           text: "jumped over the", … }
  //     ]
  //
  // ----
  //
  // 4 overlapping:
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //                   {      b      }
  //                       {     c       }
  //                       {  d }
  //
  // Result:
  //
  //     [
  //       { labelIds: ["a"],           text: "brown fox jumped", … },
  //       { labelIds: ["a", "b"],      text: "fox jumped", … },
  //       { labelIds: ["a", "b", "c"], text: "jumped", … },
  //       { labelIds: ["b"],           text: "fox jumped over", … }
  //       { labelIds: ["b", "c"],      text: "jumped over", … }
  //       { labelIds: ["c"],           text: "jumped over the", … }
  //       { labelIds: ["d"],           text: "jumped", … }
  //     ]
  //
  // ----
  //
  // 4 overlapping (offset, and duplicate):
  //
  //     A quick brown fox jumped over the lazy dog.
  //             {      a       }
  //                   {      b      }
  //                       {     c       }
  //       {    a    }
  //       {    d    }
  //
  //       ^     ^   ^ ^   ^    ^    ^   ^
  //       1     2   3 4   5    6    7   8
  //

  const rangeIdIndex = new RangeIdIndex();
  for (const range of ranges) {
    rangeIdIndex.set(range.from, range.to, range.id);
  }

  const ops = buildOpSequence(ranges, labels);

  const openStack: Array<{
    pos: number;
    labels: ReadonlySet<string>;
  }> = [];
  const segments: Segment[] = [];

  for (const op of ops) {
    switch (op.type) {
      case OpType.START: {
        openStack.push({ pos: op.pos, labels: op.labels });
        break;
      }
      case OpType.STOP: {
        let openLabels: ReadonlySet<string> = new Set();
        let foundOpenStart = false;
        for (let i = 0; i < openStack.length; i++) {
          const openOp = openStack[i];
          if (openOp.pos >= op.pos) {
            break;
          }

          openLabels = set.union(openLabels, openOp.labels);
          if (foundOpenStart || set.some(openOp.labels, label => op.labels.has(label))) {
            foundOpenStart = true;

            segments.push({
              ...encodeToPlainSingleLine(node, { range: [openOp.pos, op.pos], constraints: options.constraints }),
              rangeId: rangeIdIndex.get(openOp.pos, op.pos),
              labelIds: openLabels
            });

            const newOpenOpLabels = set.subtraction(openOp.labels, op.labels);
            if (newOpenOpLabels.size > 0) {
              openOp.labels = newOpenOpLabels;
            } else {
              openStack.splice(i, 1);
              i--;
            }
          }
        }
        break;
      }
    }
  }

  return segments;
}

export class LabelsLookup {
  private readonly map = new Map<string, Set<string>>();

  public add(id: string, label: string): void {
    const lookup = this.map.get(id);
    const set = lookup !== undefined ? lookup : new Set<string>();
    set.add(label);
    this.map.set(id, set);
  }

  public get(id: string): Set<string> | undefined {
    return this.map.get(id);
  }
}

class RangeIdIndex {
  private readonly index: { [key: string]: string | undefined } = {};

  public set(from: number, to: number, rangeId: string): void {
    this.index[`${from}|${to}`] = rangeId;
  }

  public get(from: number, to: number): string | undefined {
    return this.index[`${from}|${to}`];
  }
}

export const enum OpType {
  STOP = 1,
  START = 2
}

export interface StartOp {
  type: OpType.START;
  pos: number;
  labels: ReadonlySet<string>;
}

export interface StopOp {
  type: OpType.STOP;
  pos: number;
  labels: ReadonlySet<string>;
}

export type Op = StartOp | StopOp;

export function buildOpSequence(ranges: ReadonlyArray<Range>, labels: ReadonlyArray<Label>) {
  const labelsLookup = new LabelsLookup();
  for (const label of labels) {
    labelsLookup.add(label.rangeId, label.id);
  }

  const comparators = [sortComparatorAsc<Op>(op => op.pos)];
  const ops: Array<Op> = [];
  for (const range of ranges) {
    const labels = labelsLookup.get(range.id);
    if (labels === undefined || range.from >= range.to) {
      // Ignore collapsed ranges, or ranges that have no labels associated.
      continue;
    }
    // The decision to store labels in the op was done for performance, as it
    // avoids multiple lookup. The lookup can be done once here, then stored
    // in the op, and avoid two lookups when processing the ops (one for
    // start, one for stop).
    mutatingSortedInsert(ops, { type: OpType.START, pos: range.from, labels }, comparators);
    mutatingSortedInsert(ops, { type: OpType.STOP, pos: range.to, labels }, comparators);
  }

  // Normalise the operations to join adjacent labels (remove unnecessary
  // stop→start), and to merge overlaps.
  const normalisedOps: Array<Op> = [];
  let state = new set.CountedSet<string>();

  // The strategy here is to batch up all the operations for each position, and
  // apply them together, and then look at the aggregate results. This means
  // that multiple start/stop for a label at a single position can be evaluated
  // from their "net" effect.
  for (const opsAtPos of groupBy(ops, op => op.pos)) {
    const newState = state.copy();
    const pos = opsAtPos[0].pos;
    const touchedLabels = new Set<string>();

    for (const op of opsAtPos) {
      if (op.type === OpType.START) {
        for (const label of op.labels) {
          newState.add(label);
          touchedLabels.add(label);
        }
      } else {
        for (const label of op.labels) {
          newState.remove(label);
          touchedLabels.add(label);
        }
      }
    }

    const startLabels = new Set<string>();
    const stopLabels = new Set<string>();
    for (const label of touchedLabels) {
      const prevCount = state.count(label);
      const newCount = newState.count(label);

      if (prevCount === 0 && newCount > 0) {
        startLabels.add(label);
      } else if (prevCount > 0 && newCount === 0) {
        stopLabels.add(label);
      }
    }

    if (stopLabels.size > 0) {
      normalisedOps.push({ type: OpType.STOP, pos, labels: stopLabels });
    }
    if (startLabels.size > 0) {
      normalisedOps.push({ type: OpType.START, pos, labels: startLabels });
    }

    state = newState;
  }

  return normalisedOps;
}