import { describe, expect, it } from "vitest";
import * as fc from "fast-check";

import {
  POSITION_ALPHABET,
  afterPosition,
  beforePosition,
  betweenPosition,
  comparePositions,
  generatePosition,
  isValidPosition,
  maxPosition,
  minPosition,
  needsRebalance,
  positionForSlotNeighbors,
  rebalancePositions,
  sortPositions,
} from "./positions.js";
import { LIMITS } from "./constants.js";

// Arbitrary: valid position strings over the alphabet.
const positionArb = fc
  .stringOf(fc.constantFrom(...Array.from(POSITION_ALPHABET)), { minLength: 1, maxLength: 8 })
  .map((s) => s);

// Arbitrary strictly-ordered pair (a < b) with a non-empty gap (immediate
// successors are un-splittable by design — rebalance instead).
const orderedPairArb: fc.Arbitrary<[string, string]> = fc
  .tuple(positionArb, positionArb)
  .filter(([a, b]) => a !== b)
  .map(([a, b]): [string, string] => (a < b ? [a, b] : [b, a]))
  .filter(([lo, hi]) => hi !== lo + "0");

describe("comparePositions", () => {
  it("orders by content with prefix rule", () => {
    const sorted = sortPositions(["a", "a0", "a1", "aa", "b", "0", "z9"]);
    expect(sorted).toEqual(["0", "a", "a0", "a1", "aa", "b", "z9"]);
  });

  it("is a total order (property)", () => {
    fc.assert(
      fc.property(positionArb, positionArb, (a, b) => {
        const ab = comparePositions(a, b);
        const ba = comparePositions(b, a);
        expect(ab * ba).toBeLessThanOrEqual(0);
        if (a === b) expect(ab).toBe(0);
      }),
    );
  });
});

describe("minPosition / maxPosition", () => {
  it("min < max", () => {
    expect(comparePositions(minPosition(), maxPosition())).toBe(-1);
  });

  it("min/max are valid single characters", () => {
    expect(isValidPosition(minPosition())).toBe(true);
    expect(isValidPosition(maxPosition())).toBe(true);
    expect(minPosition()).toBe("0");
    expect(maxPosition()).toBe("z");
  });
});

describe("generatePosition", () => {
  it("defaults to a0 (matches prisma @default)", () => {
    expect(generatePosition()).toBe("a0");
  });

  it("with start: result is valid and strictly greater", () => {
    fc.assert(
      fc.property(positionArb, (start) => {
        const p = generatePosition(start);
        expect(isValidPosition(p)).toBe(true);
        expect(comparePositions(start, p)).toBe(-1);
      }),
    );
  });

  it("distinct starts yield distinct positions (uniqueness)", () => {
    // 180 distinct starts (the full period of (i % 36, i % 10)).
    const starts: string[] = [];
    for (let i = 0; i < 180; i++) starts.push(`${POSITION_ALPHABET[i % 36]}${i % 10}`);
    expect(new Set(starts).size).toBe(180);
    const seen = new Set<string>();
    for (const s of starts) {
      const p = generatePosition(s);
      expect(seen.has(p)).toBe(false);
      seen.add(p);
    }
  });

  it("throws on invalid start", () => {
    expect(() => generatePosition("ABC!")).toThrow(RangeError);
  });
});

describe("afterPosition / beforePosition", () => {
  it("after > p and before < p (property)", () => {
    fc.assert(
      fc.property(positionArb, (p) => {
        const after = afterPosition(p);
        expect(comparePositions(p, after)).toBe(-1);
      }),
    );
    fc.assert(
      fc.property(
        positionArb.filter((p) => p !== "0"),
        (p) => {
          const before = beforePosition(p);
          expect(comparePositions(before, p)).toBe(-1);
        },
      ),
    );
  });

  it("before(after(p)) lands strictly between p and after(p)", () => {
    for (const p of ["a0", "a0i", "5", "zz", "1"]) {
      const b = beforePosition(afterPosition(p));
      expect(comparePositions(p, b)).toBe(-1);
      expect(comparePositions(b, afterPosition(p))).toBe(-1);
    }
  });

  it("beforePosition strips trailing zeros and decrements", () => {
    expect(beforePosition("a0")).toBe("9");
    expect(beforePosition("a900")).toBe("a8");
    expect(beforePosition("a0p")).toBe("a0o");
    expect(beforePosition("00")).toBe("0");
  });

  it("throws when nothing is below", () => {
    expect(() => beforePosition("0")).toThrow(RangeError);
  });
});

describe("betweenPosition", () => {
  it("throws when a >= b", () => {
    expect(() => betweenPosition("b", "a")).toThrow(RangeError);
    expect(() => betweenPosition("a", "a")).toThrow(RangeError);
  });

  it("throws on invalid positions", () => {
    expect(() => betweenPosition("aB", "c")).toThrow(RangeError);
    expect(() => betweenPosition("", "a")).toThrow(RangeError);
  });

  it("throws on the empty gap (immediate successor)", () => {
    expect(() => betweenPosition("a", "a0")).toThrow(/empty gap/);
    expect(() => betweenPosition("a0", "a00")).toThrow(/empty gap/);
  });

  it("orders correctly for hand-picked cases", () => {
    const cases: Array<[string, string]> = [
      ["a", "b"],
      ["a0", "b0"],
      ["a", "a0i"],
      ["a0", "a1"],
      ["az", "b"],
      ["a", "zzzz"],
      ["9", "a"],
    ];
    for (const [a, b] of cases) {
      const mid = betweenPosition(a, b);
      expect(isValidPosition(mid)).toBe(true);
      expect(comparePositions(a, mid)).toBe(-1);
      expect(comparePositions(mid, b)).toBe(-1);
    }
  });

  it("result stays strictly inside the gap (property)", () => {
    fc.assert(
      fc.property(orderedPairArb, ([a, b]) => {
        const mid = betweenPosition(a, b);
        expect(isValidPosition(mid)).toBe(true);
        expect(comparePositions(a, mid)).toBe(-1);
        expect(comparePositions(mid, b)).toBe(-1);
      }),
      { numRuns: 500 },
    );
  });

  it("result is shorter than or near the inputs (bounded growth)", () => {
    fc.assert(
      fc.property(orderedPairArb, ([a, b]) => {
        const mid = betweenPosition(a, b);
        expect(mid.length).toBeLessThanOrEqual(Math.max(a.length, b.length) + 1);
      }),
      { numRuns: 500 },
    );
  });

  it("repeated halving 100× stays valid until rebalance is needed", () => {
    // Alternate halving from both ends of the gap (the strategy the API uses
    // when many blocks are inserted between the same two neighbors). Each
    // halving adds ≤1 char, so 100 halvings stay far under the 64-char
    // rebalance bound.
    let lo = "0";
    let hi = "z";
    const positions: string[] = [lo, hi];
    let halvings = 0;

    for (let step = 0; step < 100; step++) {
      if (needsRebalance(positions)) break;
      const mid = betweenPosition(lo, hi);
      positions.push(mid);
      expect(isValidPosition(mid)).toBe(true);
      expect(comparePositions(lo, mid)).toBe(-1);
      expect(comparePositions(mid, hi)).toBe(-1);
      // Alternate which side we descend into.
      if (step % 2 === 0) hi = mid;
      else lo = mid;
      halvings++;
    }

    // All 100 halvings succeed — lengths stay far below the hard bound.
    expect(halvings).toBe(100);
    expect(positions.every((p) => p.length <= LIMITS.MAX_POSITION_LENGTH)).toBe(true);
    expect(Math.max(...positions.map((p) => p.length))).toBeLessThanOrEqual(32);
  });

  it("single-side descent halts at the empty gap (rebalance signal)", () => {
    // Repeatedly halving only the upper half of (a0, b0) eventually reaches
    // the immediate-successor gap ("x", "x0"), where the engine must refuse
    // — that is the signal for rebalancePositions.
    const lo = "a0";
    let hi = "b0";
    const positions = [lo, hi];
    let steps = 0;
    for (let step = 0; step < 50; step++) {
      if (needsRebalance(positions)) break;
      let mid: string;
      try {
        mid = betweenPosition(lo, hi);
      } catch {
        break; // empty gap reached
      }
      positions.push(mid);
      hi = mid;
      steps++;
    }
    expect(steps).toBeGreaterThan(5);
    expect(positions.every((p) => p.length <= LIMITS.MAX_POSITION_LENGTH)).toBe(true);
    // After a rebalance the same list is short again.
    const mapping = rebalancePositions(positions);
    for (const next of Object.values(mapping)) {
      expect(next.length).toBeLessThanOrEqual(4);
    }
  });

  it("throws when the result would exceed max length", () => {
    // a and b are both at the max length (64); splitting the adjacent
    // "a…z" / "b…0" gap needs a 65-char result → the engine refuses.
    const a = "a" + "z".repeat(LIMITS.MAX_POSITION_LENGTH - 1);
    const b = "b" + "0".repeat(LIMITS.MAX_POSITION_LENGTH - 1);
    expect(isValidPosition(a)).toBe(true);
    expect(isValidPosition(b)).toBe(true);
    expect(() => betweenPosition(a, b)).toThrow(/max length/);
  });
});

describe("needsRebalance / rebalancePositions", () => {
  it("needsRebalance is false for short positions", () => {
    expect(needsRebalance(["a0", "a1", "az", "b0"])).toBe(false);
  });

  it("needsRebalance is true once any position exceeds 64 chars", () => {
    expect(needsRebalance(["a0", "a".repeat(65)])).toBe(true);
  });

  it("rebalance restores short positions while preserving order", () => {
    // Build a long list of positions by inserting midpoints repeatedly
    // (stop when the one-sided descent reaches the empty gap — exactly the
    // situation where a rebalance is needed).
    const positions: string[] = [];
    // A distinct ascending chain (generatePosition() with no arg always
    // returns "a0" — five of those would be duplicates and rebalance rejects
    // them; chain the cursor so each step is strictly greater).
    let cursor: string | undefined;
    for (let i = 0; i < 5; i++) {
      cursor = generatePosition(cursor);
      positions.push(cursor);
    }
    const lo = "c0";
    let hi = "d0";
    while (positions.length < 40) {
      if (needsRebalance([lo, hi])) break;
      let mid: string;
      try {
        mid = betweenPosition(lo, hi);
      } catch {
        break; // empty gap — rebalance time
      }
      positions.push(mid);
      hi = mid;
    }
    const mapping = rebalancePositions(positions);

    // One entry per distinct old position.
    expect(Object.keys(mapping).length).toBe(new Set(positions).size);

    // New positions are short.
    for (const next of Object.values(mapping)) {
      expect(next.length).toBeLessThanOrEqual(4);
      expect(isValidPosition(next)).toBe(true);
    }

    // Order preserved: sorting old positions and mapping keeps the order.
    const oldSorted = sortPositions(positions);
    const newSorted = oldSorted.map((p) => mapping[p] as string);
    expect(newSorted).toEqual([...newSorted].sort());
  });

  it("fixed-width encoding keeps lex order == slot order (no a10<aa bug)", () => {
    const n = 100; // width 2 (36 slots per width-1)
    const olds = Array.from({ length: n }, (_, i) =>
      generatePosition(`s${String(i).padStart(3, "0")}`),
    );
    const mapping = rebalancePositions(olds);
    const values = sortPositions(olds).map((p) => mapping[p] as string);
    expect(values).toEqual([...values].sort());
    expect(new Set(values).size).toBe(n);
    for (const v of values) expect(v.length).toBeLessThanOrEqual(3);
  });

  it("rejects duplicates and invalid positions", () => {
    expect(() => rebalancePositions(["a0", "a0"])).toThrow(/duplicate/);
    expect(() => rebalancePositions(["A0"])).toThrow(RangeError);
  });
});

describe("positionForSlotNeighbors", () => {
  it("midpoint when both neighbors are given", () => {
    const p = positionForSlotNeighbors("a0", "b0");
    expect(comparePositions("a0", p)).toBe(-1);
    expect(comparePositions(p, "b0")).toBe(-1);
  });

  it("appends after `before` only", () => {
    const p = positionForSlotNeighbors("az", null);
    expect(comparePositions("az", p)).toBe(-1);
  });

  it("prepends before `after` only", () => {
    const p = positionForSlotNeighbors(null, "a5");
    expect(comparePositions(p, "a5")).toBe(-1);
  });

  it("fresh position when neither", () => {
    expect(positionForSlotNeighbors(null, null)).toBe("a0");
  });
});