import type { Command, CommandOf } from "./operations";
import type { CardLocation } from "./types";
import { assert } from "./utils";

// Impose a somewhat arbitrary ordering on commands.
const commandOrder = [
  "moveCard",
  "createPile",
  "removeEmptyPile",
  "movePile",
  "namePile",
  "spliceCards",
] as const satisfies Command[0][];

type ExhaustiveTuple<U extends string, T extends readonly string[]> = [U] extends [T[number]]
  ? T
  : never;

const _commandOrderIsExhaustive: ExhaustiveTuple<Command[0], typeof commandOrder> = commandOrder;

type TakeBefore<T extends readonly string[], K extends string> = T extends readonly [
  infer H extends string,
  ...infer Rest extends string[],
]
  ? H extends K
    ? []
    : [H, ...TakeBefore<Rest, K>]
  : [];

type CommandNamesBefore<K extends Command[0]> = TakeBefore<typeof commandOrder, K>[number];

type CommandAtOrAfter<K extends Command[0]> = Exclude<Command, [CommandNamesBefore<K>, ...any[]]>;

const commandOrderIndex = Object.fromEntries(
  commandOrder.map((name, index) => [name, index]),
) as Record<Command[0], number>;

function assertOrdered<K extends Command[0]>(
  aName: K,
  b: Command,
): asserts b is CommandAtOrAfter<K> {
  assert(commandOrderIndex[aName] <= commandOrderIndex[b[0]]);
}

function arrayLT(a: any[], b: any[]) {
  for (let i = 0; i < a.length && i < b.length; i++) {
    if (a[i]! < b[i]!) return true;
    if (a[i]! > b[i]!) return false;
  }
  return a.length < b.length;
}

function opLT(a: Command, b: Command) {
  const oa = commandOrderIndex[a[0]];
  const ob = commandOrderIndex[b[0]];
  if (oa !== ob) return oa < ob;
  for (let i = 1; i < a.length && i < b.length; i++) {
    if (a[i]! !== b[i]!) {
      if (Array.isArray(a[i]) && Array.isArray(b[i])) {
        return arrayLT(a[i] as any[], b[i] as any[]);
      }
      return a[i]! < b[i]!;
    }
  }
  return a.length < b.length;
}

// Type system ensures we consider all operation pairs.
function unreachableOperations(a: Command, b: never): never {
  throw new Error(`Unhandled xform pair: ${a[0]}, ${b[0]}`);
}

function adjustPileForCreatePile(p: number, createdPileIndex: number) {
  return p >= createdPileIndex ? p + 1 : p;
}

function xform_createPile(
  a: CommandOf<"createPile">,
  b: CommandAtOrAfter<"createPile">,
): [Command[], Command[]] {
  const i = a[1];
  if (b[0] === "createPile") {
    const j = b[1];
    assert(i <= j);
    return [[a], [["createPile", j + 1]]];
  } else if (b[0] === "spliceCards") {
    const [, p, c, d, cardIds] = b;
    return [[a], [["spliceCards", adjustPileForCreatePile(p, i), c, d, cardIds]]];
  } else if (b[0] === "namePile") {
    const [, p, name] = b;
    return [[a], [["namePile", adjustPileForCreatePile(p, i), name]]];
  } else if (b[0] === "removeEmptyPile") {
    const j = b[1];
    return [[["createPile", i > j ? i - 1 : i]], [["removeEmptyPile", j >= i ? j + 1 : j]]];
  } else if (b[0] === "movePile") {
    const [, p, q] = b;
    // Special case for creating a pile at the destination of a reverse move.
    const index = q < p && i == q ? i : adjustDestForMove(i, p, q, false);
    return [
      [["createPile", index]],
      [["movePile", adjustPileForCreatePile(p, i), adjustPileForCreatePile(q, i)]],
    ];
  } else {
    unreachableOperations(a, b);
  }
}

function adjustPileForRemovePile(p: number, removedAt: number): number {
  return p > removedAt ? p - 1 : p;
}

function xform_removeEmptyPile(
  a: CommandOf<"removeEmptyPile">,
  b: CommandAtOrAfter<"removeEmptyPile">,
): [Command[], Command[]] {
  const i = a[1];
  if (b[0] === "removeEmptyPile") {
    const j = b[1];
    assert(i <= j);
    if (i === j) return [[], []];
    return [[a], [["removeEmptyPile", j - 1]]];
  } else if (b[0] === "spliceCards") {
    const [, p, c, d, cardIds] = b;
    if (p === i) return [[], [["createPile", i], b]]; // cancel removeEmptyPile
    return [[a], [["spliceCards", adjustPileForRemovePile(p, i), c, d, cardIds]]];
  } else if (b[0] === "namePile") {
    const [, p, name] = b;
    if (p === i) return [[a], []];
    return [[a], [["namePile", adjustPileForRemovePile(p, i), name]]];
  } else if (b[0] === "movePile") {
    const [, p, q] = b;
    if (p === i) return [[["removeEmptyPile", q]], []];
    return [
      [["removeEmptyPile", remapIndexForMove(i, p, q)]],
      [["movePile", adjustPileForRemovePile(p, i), adjustPileForRemovePile(q, i)]],
    ];
  } else {
    unreachableOperations(a, b);
  }
}

// Returns the element's new index after a move from src to dest.
function remapIndexForMove(index: number, src: number, dest: number): number {
  if (index === src) return dest;
  if (index > src) index--;
  if (index >= dest) index++;
  return index;
}

// Similar to remapMove, but points to the "hole" left by src instead of
// following it to dest.
function adjustDestForMove(index: number, src: number, dest: number, biasAfter: boolean): number {
  // On forward move the "hole" is after src instead of before it.
  if (biasAfter ? index >= src : index > src) index--;
  if (index >= dest) index++;
  return index;
}

function xformMove(
  a: [number, number],
  b: [number, number],
): [[number, number] | null, [number, number] | null] {
  const [aSrc, aDest] = a;
  const [bSrc, bDest] = b;
  if (aSrc === bSrc) {
    if (aDest === bDest) {
      // Discard duplicate move.
      return [null, null];
    } else {
      // Same source; A wins.
      return [[bDest, aDest], null];
    }
  } else if (aDest === bDest && aSrc < aDest === bSrc < bDest) {
    // Same destination in the same direction; A wins.
    return [
      [remapIndexForMove(aSrc, ...b), aDest],
      [remapIndexForMove(bSrc, ...a), remapIndexForMove(bDest, ...a)],
    ];
  } else {
    return [
      [remapIndexForMove(aSrc, ...b), adjustDestForMove(aDest, ...b, aSrc < aDest)],
      [remapIndexForMove(bSrc, ...a), adjustDestForMove(bDest, ...a, bSrc < bDest)],
    ];
  }
}

function xform_movePile_movePile(
  a: CommandOf<"movePile">,
  b: CommandOf<"movePile">,
): [Command[], Command[]] {
  const [aMove, bMove] = xformMove([a[1], a[2]], [b[1], b[2]]);
  const aPrime: Command[] = aMove == null ? [] : [["movePile", ...aMove]];
  const bPrime: Command[] = bMove == null ? [] : [["movePile", ...bMove]];
  return [aPrime, bPrime];
}

function xform_movePile(
  a: CommandOf<"movePile">,
  b: CommandAtOrAfter<"movePile">,
): [Command[], Command[]] {
  const [, p1, q1] = a;
  if (b[0] === "movePile") {
    return xform_movePile_movePile(a, b);
  } else if (b[0] === "spliceCards") {
    const [, p, c, d, cardIds] = b;
    return [[a], [["spliceCards", remapIndexForMove(p, p1, q1), c, d, cardIds]]];
  } else if (b[0] === "namePile") {
    const [, p, name] = b;
    return [[a], [["namePile", remapIndexForMove(p, p1, q1), name]]];
  } else {
    unreachableOperations(a, b);
  }
}

function xform_namePile(
  a: CommandOf<"namePile">,
  b: CommandAtOrAfter<"namePile">,
): [Command[], Command[]] {
  if (b[0] === "namePile") {
    if (a[1] === b[1]) return [[a], []];
    return [[a], [b]];
  } else if (b[0] === "spliceCards") {
    return [[a], [b]];
  } else {
    unreachableOperations(a, b);
  }
}

function adjustSpliceCards(
  orig: CommandOf<"spliceCards">,
  over: CommandOf<"spliceCards">,
): Command {
  let [, pileIndex, cardIndex, deleteCount, cardIds] = orig;
  const [, overPileIndex, overCardIndex, overDeleteCount, overCardIds] = over;
  if (pileIndex !== overPileIndex) return orig;
  if (cardIndex < overCardIndex) {
    if (cardIndex + deleteCount > overCardIndex) {
      // TODO this is valid but not a good resolution; probably should split the splice
      // orig's delete range overlaps with over's range
      // If over's edit is fully contained within orig's range, orig must also delete over's insertions
      const overCancelled = overCardIndex + overDeleteCount <= cardIndex + deleteCount;
      const extraFromOver = overCancelled ? overCardIds.length : 0;
      deleteCount =
        overCardIndex -
        cardIndex +
        extraFromOver +
        Math.max(0, cardIndex + deleteCount - overCardIndex - overDeleteCount);
    }
  } else if (cardIndex === overCardIndex) {
    if (deleteCount < overDeleteCount) {
      deleteCount = 0;
    } else if (deleteCount > overDeleteCount) {
      deleteCount -= overDeleteCount;
      cardIndex += overCardIds.length;
    } else {
      deleteCount = 0;
      if (!arrayLT(overCardIds, cardIds)) {
        cardIndex += overCardIds.length;
      }
    }
  } else if (cardIndex < overCardIndex + overDeleteCount) {
    deleteCount = Math.max(0, cardIndex + deleteCount - overCardIndex - overDeleteCount);
    cardIndex = overCardIndex + overCardIds.length;
    // TODO keep the insertion
    if (deleteCount === 0) {
      cardIds = []; // insertion point was deleted by over; cancel the insertion
    }
  } else {
    cardIndex = cardIndex - overDeleteCount + overCardIds.length;
  }
  return ["spliceCards", pileIndex, cardIndex, deleteCount, cardIds];
}

function xform_spliceCards_spliceCards(
  a: CommandOf<"spliceCards">,
  b: CommandOf<"spliceCards">,
): [Command[], Command[]] {
  return [[adjustSpliceCards(a, b)], [adjustSpliceCards(b, a)]];
}

function locationEq(a: CardLocation, b: CardLocation) {
  return a[0] === b[0] && a[1] === b[1];
}

function adjustLocationForMoveCard(
  [pileIndex, cardIndex]: CardLocation,
  src: CardLocation,
  dest: CardLocation,
  strictInsert = false,
): CardLocation {
  if (pileIndex === src[0] && cardIndex > src[1]) cardIndex--;
  if (pileIndex === dest[0] && (strictInsert ? cardIndex > dest[1] : cardIndex >= dest[1]))
    cardIndex++;
  return [pileIndex, cardIndex];
}

function remapLocationForMoveCard(
  loc: CardLocation,
  src: CardLocation,
  dest: CardLocation,
): CardLocation {
  if (locationEq(loc, src)) return dest;
  let [pileIndex, cardIndex] = loc;
  if (pileIndex === src[0] && cardIndex > src[1]) cardIndex--;
  if (pileIndex === dest[0] && cardIndex >= dest[1]) cardIndex++;
  return [pileIndex, cardIndex];
}

function adjustDestForMoveCard(
  [pileIndex, cardIndex]: CardLocation,
  src: CardLocation,
  dest: CardLocation,
  biasAfter: boolean,
): CardLocation {
  if (pileIndex === src[0] && (biasAfter ? cardIndex >= src[1] : cardIndex > src[1])) {
    cardIndex--;
  }
  if (pileIndex === dest[0] && cardIndex >= dest[1]) cardIndex++;
  return [pileIndex, cardIndex];
}

// TODO remove noops that can happen here and elsewhere
function xform_moveCard_moveCard(
  [, aSrc, aDest]: CommandOf<"moveCard">,
  [, bSrc, bDest]: CommandOf<"moveCard">,
): [Command[], Command[]] {
  if (locationEq(aSrc, bSrc)) {
    // Discard duplicate operation.
    if (locationEq(aDest, bDest)) return [[], []];
    // If only source is the same, then a wins.
    return [[["moveCard", bDest, aDest]], []];
  } else if (locationEq(aDest, bDest)) {
    // A wins.
    let aNewDest = adjustDestForMoveCard(
      aDest,
      bSrc,
      bDest,
      aSrc[0] === aDest[0] && aSrc[1] < aDest[1],
    );
    const bNewDest = adjustLocationForMoveCard(bDest, aSrc, aDest);
    // TODO understand kludge
    if (locationEq(aNewDest, bNewDest)) aNewDest = aDest;
    return [
      [["moveCard", adjustLocationForMoveCard(aSrc, bSrc, bDest), aNewDest]],
      [["moveCard", adjustLocationForMoveCard(bSrc, aSrc, aDest), bNewDest]],
    ];
  } else {
    // TODO sloppy
    const aAdjusted = [
      remapLocationForMoveCard(aSrc, bSrc, bDest),
      adjustDestForMoveCard(aDest, bSrc, bDest, aSrc[0] === aDest[0] && aSrc[1] < aDest[1]),
    ] as const;
    const bAdjusted = [
      remapLocationForMoveCard(bSrc, aSrc, aDest),
      adjustDestForMoveCard(bDest, aSrc, aDest, bSrc[0] === bDest[0] && bSrc[1] < bDest[1]),
    ] as const;
    return [[["moveCard", ...aAdjusted]], [["moveCard", ...bAdjusted]]];
  }
}

function adjustLocationForCreatePile(loc: CardLocation, createdPileIndex: number): CardLocation {
  return [adjustPileForCreatePile(loc[0], createdPileIndex), loc[1]];
}

function adjustLocationForRemovePile(loc: CardLocation, removedAt: number): CardLocation {
  return [adjustPileForRemovePile(loc[0], removedAt), loc[1]];
}

function remapLocationForMovePile(loc: CardLocation, from: number, to: number): CardLocation {
  return [remapIndexForMove(loc[0], from, to), loc[1]];
}

function xform_moveCard(
  a: CommandOf<"moveCard">,
  b: CommandAtOrAfter<"moveCard">,
): [Command[], Command[]] {
  if (b[0] === "moveCard") {
    return xform_moveCard_moveCard(a, b);
  } else if (b[0] === "createPile") {
    const p = b[1];
    const a1 = adjustLocationForCreatePile(a[1], p);
    const a2 = adjustLocationForCreatePile(a[2], p);
    return [[["moveCard", a1, a2]], [b]];
  } else if (b[0] === "removeEmptyPile") {
    const [, src, dest] = a;
    const p = b[1];
    if (dest[0] === p) return [[["createPile", p], a], []];
    // TODO should never move from an empty pile?
    if (src[0] === p) return [[], []];
    const a1 = adjustLocationForRemovePile(src, p);
    const a2 = adjustLocationForRemovePile(dest, p);
    return [[["moveCard", a1, a2]], [b]];
  } else if (b[0] === "movePile") {
    const [, p, q] = b;
    const a1 = remapLocationForMovePile(a[1], p, q);
    const a2 = remapLocationForMovePile(a[2], p, q);
    return [[["moveCard", a1, a2]], [b]];
  } else if (b[0] === "namePile") {
    return [[a], [b]];
  } else if (b[0] === "spliceCards") {
    // TODO should only cancel if moved card is within splice range
    if (a[1][0] === b[1] || a[2][0] === b[1]) return [[], [["moveCard", a[2], a[1]], b]]; // cancel moveCard
    return [[a], [b]];
  } else {
    unreachableOperations(a, b);
  }
}

function xformNormalized(a: Command, b: Command): [Command[], Command[]] {
  if (a[0] === "moveCard") {
    return xform_moveCard(a, b);
  } else if (a[0] === "createPile") {
    assertOrdered(a[0], b);
    return xform_createPile(a, b);
  } else if (a[0] === "removeEmptyPile") {
    assertOrdered(a[0], b);
    return xform_removeEmptyPile(a, b);
  } else if (a[0] === "movePile") {
    assertOrdered(a[0], b);
    return xform_movePile(a, b);
  } else if (a[0] === "namePile") {
    assertOrdered(a[0], b);
    return xform_namePile(a, b);
  } else if (a[0] === "spliceCards") {
    assertOrdered(a[0], b);
    return xform_spliceCards_spliceCards(a, b);
  }
  unreachableOperations(a, b as never);
}

export function xform(a: Command, b: Command): [Command[], Command[]] {
  if (opLT(a, b)) return xformNormalized(a, b);
  // Swap operation order.
  const [b_, a_] = xformNormalized(b, a);
  return [a_, b_];
}

// TODO understand
export function xformMany(as: Command[], bs: Command[]): [Command[], Command[]] {
  let asTransformed = as.slice();
  const bsTransformed: Command[] = [];

  for (const bp of bs) {
    let bPending: Command[] = [bp];
    const aNew: Command[] = [];

    for (const ap of asTransformed) {
      let aPending: Command[] = [ap];
      const bNext: Command[] = [];

      for (const b of bPending) {
        const aNext: Command[] = [];
        for (const a of aPending) {
          const [aPrime, bPrime] = xform(a, b);
          aNext.push(...aPrime);
          bNext.push(...bPrime);
        }
        aPending = aNext;
      }

      aNew.push(...aPending);
      bPending = bNext;
    }

    asTransformed = aNew;
    bsTransformed.push(...bPending);
  }

  return [asTransformed, bsTransformed];
}