language: TypeScript
15 KB / 470 lines / 429 loc
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];
}