/**
 * @factory/shared — fractional (LexoRank-style) position engine.
 *
 * ## Why fractional positions
 *
 * Blocks, pages, records and properties are ordered by a `position` **string**
 * that is compared **lexicographically**, never by an array index. Inserting
 * between two siblings only rewrites the single row that changes; no other
 * row moves. This is what keeps a 100k-block page cheap to reorder
 * (ARCHITECTURE.md invariant 4; PRODUCT-SPEC §4 / §8).
 *
 * ## Alphabet
 *
 * Base-36, lowercase, digits first (10 digits + 26 letters = 36 chars):
 *
 *     0123456789abcdefghijklmnopqrstuvwxyz
 *
 * (Referred to as "base-32" in older notes; the alphabet string above is the
 * single source of truth — the code derives `BASE` from its length.)
 * Digit-first is deliberate: it matches the prisma default position `"a0"`
 * and keeps generated keys human-readable.
 *
 * ## Order model
 *
 * Comparison is plain lexicographic with the prefix rule ("a" < "a0" < "a1").
 * Consequence worth knowing: **the immediate successor of any position `x`
 * is `x + "0"`** — there is no valid position strictly between `"a"` and
 * `"a0"`. All other gaps are splittable. Every split by {@link betweenPosition}
 * adds at most one character in the common case, so positions grow slowly
 * until {@link needsRebalance} (length > {@link LIMITS.MAX_POSITION_LENGTH})
 * says the sibling list should be re-spaced with
 * {@link rebalancePositions}.
 *
 * ## Algorithm (`betweenPosition`)
 *
 * Walk both strings over their common prefix `P`, then:
 *
 * 1. **`a` is a strict prefix of `b`** (`b = P + R`, `R` non-empty): the
 *    answer is `P + t` where `t` is a balanced *non-empty* string strictly
 *    smaller than `R` (see {@link beforeMidpoint}). If `R === "0"` the gap is
 *    empty — `b` is the immediate successor of `a` — and the caller must
 *    rebalance instead.
 * 2. **First differing character**, `a[i] < b[i]`:
 *    - if `idx(b[i]) - idx(a[i]) >= 2`, emit the midpoint character and stop;
 *    - if the characters are adjacent (`b[i] = a[i]+1`), keep `a[i]` and
 *      append {@link afterMidpoint} of `a`'s remaining suffix — a balanced
 *      string strictly greater than that suffix. The result is `> a` and
 *      automatically `< b`.
 *
 * `beforeMidpoint` / `afterMidpoint` are the two "one-sided" midpoints used
 * above; each adds at most one character per recursion level, so the output
 * length is bounded by `max(len(a), len(b)) + 1` per split.
 *
 * ## Invariants (property-tested in `positions.test.ts`)
 *
 * - `comparePositions(a, between(a, b), b)` → strictly `a < mid < b`.
 * - `between` throws on `a >= b`, invalid positions, empty gaps
 *   (`b === a + "0"`) and when the result would exceed
 *   {@link LIMITS.MAX_POSITION_LENGTH}.
 * - Repeated halving of one gap produces a strictly ordered chain of valid
 *   positions until rebalance is needed.
 * - `rebalancePositions` preserves order and always emits positions of
 *   length ≤ 1 + `ceil(log32(n))`.
 *
 * References: LexoRank (https://github.com/facebook/lexorank),
 * "Fractional Indexing" (https://blog.jcoglan.com/2017/10/12/fractional-indexing/).
 */

import { LIMITS } from "./constants.js";

/** The 36-character alphabet: digits first, then lowercase letters. */
export const POSITION_ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyz" as const;

/** A fractional ordering key: any non-empty string over the alphabet. */
export type Position = string;

const BASE = POSITION_ALPHABET.length; // 36
const MAX_LEN = LIMITS.MAX_POSITION_LENGTH; // 64
const MID = BASE >> 1; // 18 → 'i', the balanced one-char midpoint

/** True when every character of `p` is in the alphabet and length is legal. */
export function isValidPosition(p: Position): boolean {
  if (typeof p !== "string" || p.length === 0 || p.length > MAX_LEN) return false;
  for (let i = 0; i < p.length; i++) {
    const c = p.charCodeAt(i);
    const okDigit = c >= 48 && c <= 57; // 0-9
    const okLetter = c >= 97 && c <= 122; // a-z
    if (!okDigit && !okLetter) return false;
  }
  return true;
}

/**
 * Lexicographic comparison of two positions. Returns -1, 0 or 1.
 *
 * Plain code-unit comparison is correct for our alphabet (single-unit chars,
 * code-point order == rank order). Shorter prefixes sort first: "a" < "a0".
 */
export function comparePositions(a: Position, b: Position): number {
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

/** Smallest possible position. Used as a virtual lower anchor. */
export function minPosition(): Position {
  return POSITION_ALPHABET.charAt(0);
}

/**
 * Largest single-character position. A sentinel meaning "after everything
 * else" — it is not meant to be assigned to two siblings, so prefer
 * {@link afterPosition} when appending to a list.
 */
export function maxPosition(): Position {
  return POSITION_ALPHABET.charAt(BASE - 1);
}

/**
 * Generate a fresh position for a new top-level sibling list.
 *
 * - No argument → `"a0"` (matches the prisma `@default("a0")`, so newly
 *   created rows and generated keys agree).
 * - With `start` → `start + "i"` (alphabet midpoint), strictly greater than
 *   `start` with room on both sides (used when creating the first element of
 *   a new container that must sort after an existing marker).
 *
 * @throws RangeError if `start` is not a valid position.
 */
export function generatePosition(start?: Position): Position {
  if (start === undefined) return "a0";
  if (!isValidPosition(start)) {
    throw new RangeError(`invalid position: ${JSON.stringify(start)}`);
  }
  if (start.length >= MAX_LEN) {
    throw new RangeError(`position at max length, cannot extend: ${start} — rebalance the list`);
  }
  return start + POSITION_ALPHABET.charAt(MID);
}

/**
 * A position strictly greater than `p` (append to end of a sibling list).
 * Appends the alphabet midpoint `'i'`, which keeps maximal headroom below.
 *
 * @throws RangeError if `p` is invalid or already at the max length.
 */
export function afterPosition(p: Position): Position {
  if (!isValidPosition(p)) {
    throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
  }
  if (p.length >= MAX_LEN) {
    throw new RangeError(`position at max length, cannot extend: ${p} — rebalance the list`);
  }
  return p + POSITION_ALPHABET.charAt(MID);
}

/**
 * A position strictly less than `p` (prepend to start of a sibling list),
 * with as much headroom above the result as the layout allows.
 *
 * - Last char > "0" → decrement it: `"a0p"` → `"a0o"`.
 * - Trailing "0"s are dropped, then the new last char is decremented:
 *   `"a900"` → `"a8"`, `"a0"` → `"9"`.
 *
 * @throws RangeError if `p` is invalid or no smaller position exists
 *   (`p` is `"0"`-like at the bottom of the range).
 */
export function beforePosition(p: Position): Position {
  if (!isValidPosition(p)) {
    throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
  }
  let i = p.length - 1;
  while (i >= 1 && p.charAt(i) === "0") i--;
  const idx = POSITION_ALPHABET.indexOf(p.charAt(i));
  if (idx <= 0) {
    // `p` is all "0" chars. Shortening by one char yields a valid, smaller
    // position ("00" → "0"); a single "0" has nothing below it.
    if (p.length > 1) return p.slice(0, p.length - 1);
    throw new RangeError(`no position below ${p}`);
  }
  return p.slice(0, i) + POSITION_ALPHABET.charAt(idx - 1);
}

/**
 * A position strictly between `a` and `b`. **Requires `a < b`** (throws
 * otherwise). Returns the shortest balanced position splitting the gap.
 *
 * @throws RangeError if `a >= b`, either position is invalid, the gap is
 *   empty (`b === a + "0"`), or the result would exceed the max length —
 *   rebalance the sibling list in those cases.
 */
export function betweenPosition(a: Position, b: Position): Position {
  if (!isValidPosition(a) || !isValidPosition(b)) {
    throw new RangeError("betweenPosition received an invalid position");
  }
  if (comparePositions(a, b) !== -1) {
    throw new RangeError(`betweenPosition requires a < b (got a=${a}, b=${b})`);
  }

  const n = a.length;
  const m = b.length;
  let i = 0;
  // Common prefix.
  while (i < n && i < m && a.charAt(i) === b.charAt(i)) i++;

  let result: string;
  if (i === n) {
    // Case 1: a is a strict prefix of b.  b = P + R, R non-empty.
    const rest = b.slice(i);
    if (rest === "0") {
      // Empty gap: b is the immediate successor of a (a + "0"). There is no
      // valid position strictly between them — rebalance is required.
      throw new RangeError(
        `betweenPosition(${a}, ${b}) is an empty gap (b is the immediate successor of a) — rebalance the list`,
      );
    }
    result = a + beforeMidpoint(rest);
  } else {
    // Case 2: first differing character at index i (b cannot be the shorter
    // string here: a < b and a prefix of b is the only way one is shorter).
    const ca = POSITION_ALPHABET.indexOf(a.charAt(i));
    const cb = POSITION_ALPHABET.indexOf(b.charAt(i));
    if (cb - ca >= 2) {
      result = a.slice(0, i) + POSITION_ALPHABET.charAt(ca + ((cb - ca) >> 1));
    } else {
      // Adjacent characters: keep a[i], descend past a's suffix.
      result = a.slice(0, i + 1) + afterMidpoint(a.slice(i + 1));
    }
  }

  if (result.length > MAX_LEN) {
    throw new RangeError(
      `betweenPosition(${a}, ${b}) exceeds max length ${MAX_LEN} — rebalance the list`,
    );
  }
  return result;
}

/**
 * Balanced non-empty string strictly smaller than `rest` (`rest` non-empty,
 * `rest !== "0"`). Used for the "a is a prefix of b" case: the gap is
 * exactly the non-empty `t < rest`.
 *
 * Finds the first index `j` with `rest[j] > "0"`:
 * - `rest` is all "0"s (length ≥ 2): return `rest` minus its last char.
 * - `rest = 0^j · c · T`, `idx(c) ≥ 2`: return `0^j · char(idx(c) >> 1)`.
 * - `rest = 0^j · "1" · T`: return `0^j · "0"` (+ recurse into `T` when it
 *   itself contains a non-zero).
 */
function beforeMidpoint(rest: string): string {
  let j = 0;
  while (j < rest.length && rest.charAt(j) === "0") j++;

  if (j === rest.length) {
    // All zeros, length ≥ 2 guaranteed by the caller ("0" is the empty gap).
    return rest.slice(0, rest.length - 1);
  }

  const cIdx = POSITION_ALPHABET.indexOf(rest.charAt(j));
  const head = rest.slice(0, j);
  if (cIdx >= 2) {
    return head + POSITION_ALPHABET.charAt(cIdx >> 1);
  }
  // c === '1'
  const tail = rest.slice(j + 1);
  if (tail.length === 0 || isAllZeros(tail)) {
    return head + "0";
  }
  return head + "0" + beforeMidpoint(tail);
}

/**
 * Balanced string strictly greater than `suffix` (which may be empty). Used
 * for the adjacent-character case: everything `suffix + t` with `t` in this
 * space sorts between `a` and `b`.
 *
 * - empty suffix → the alphabet midpoint `"p"`.
 * - last char < "z" → replace it with the midpoint between it and "z".
 * - last char "z" → append `"p"`.
 */
function afterMidpoint(suffix: string): string {
  if (suffix.length === 0) return POSITION_ALPHABET.charAt(MID);
  // Find the last index whose character can be INCREASED STRICTLY without
  // exceeding the alphabet max ("z"), then replace it with the midpoint
  // between it and "z" and drop the tail. Dropping the tail is safe: any
  // string with that prefix and a character greater than the original (and
  // any tail) still exceeds the original suffix; the tail-less form is the
  // minimal such value.
  //
  // Strictness matters: the midpoint formula `idx + ((BASE-1-idx)>>1)` is a
  // no-op for `idx === BASE-2` (the second-to-last char, "y"): its midpoint
  // to "z" is itself. Increasing such a char in place would return the
  // suffix UNCHANGED (e.g. betweenPosition("oy","p0") → "oy"), violating
  // the strict-inside-gap contract — so those chars are skipped. The
  // threshold `idx <= BASE-3` is exactly the set of chars whose midpoint to
  // "z" is strictly greater.
  for (let k = suffix.length - 1; k >= 0; k--) {
    const idx = POSITION_ALPHABET.indexOf(suffix.charAt(k));
    if (idx <= BASE - 3) {
      return suffix.slice(0, k) + POSITION_ALPHABET.charAt(idx + ((BASE - 1 - idx) >> 1));
    }
  }
  // No char can be increased in place ("y"/"z" tail): append the midpoint —
  // the minimal balanced strictly-greater extension (mirrors afterPosition).
  return suffix + POSITION_ALPHABET.charAt(MID);
}

function isAllZeros(s: string): boolean {
  for (let i = 0; i < s.length; i++) if (s.charAt(i) !== "0") return false;
  return true;
}

/**
 * True when the sibling list is unhealthy: any position longer than
 * {@link LIMITS.MAX_POSITION_LENGTH}. The caller should re-space the list
 * with {@link rebalancePositions} (the API also does this preemptively at a
 * softer threshold, e.g. 24 chars, to keep future writes short).
 */
export function needsRebalance(positions: readonly Position[]): boolean {
  for (const p of positions) {
    if (p.length > MAX_LEN) return true;
  }
  return false;
}

/**
 * Re-space a sibling list into short, uniformly spaced positions, preserving
 * relative order. Returns a map of old position → new position.
 *
 * Layout: `"a"` + a fixed-width base-32 encoding of the slot, where the
 * width is `max(1, ceil(log32(n)))` for `n` slots. Fixed width is required
 * because lexicographic order with the prefix rule does **not** agree with
 * variable-width numeric order ("a10" would sort before "aa"). Output length
 * is at most `1 + width` (≤ 4 chars for up to 32,768 siblings — far beyond
 * any realistic sibling list).
 *
 * The input order is ignored except for detecting duplicates; the *sorted*
 * order defines slot 0, 1, 2, …. Duplicate positions are rejected — positions
 * are unique within a sibling list (enforced by the database too).
 *
 * @throws RangeError on duplicate or invalid positions.
 */
export function rebalancePositions(positions: readonly Position[]): Record<string, string> {
  for (const p of positions) {
    if (!isValidPosition(p)) {
      throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
    }
  }
  const seen = new Set<string>();
  for (const p of positions) {
    if (seen.has(p)) throw new RangeError(`duplicate position: ${p}`);
    seen.add(p);
  }

  const n = positions.length;
  const width = n <= BASE ? 1 : Math.ceil(Math.log(n) / Math.log(BASE));
  const sorted = [...positions].sort(comparePositions);
  const mapping: Record<string, string> = {};
  for (let slot = 0; slot < sorted.length; slot++) {
    const key = sorted[slot] as string; // slot < length — index is defined
    mapping[key] = "a" + toFixedWidthBase32(slot, width);
  }
  return mapping;
}

/** Encode `slot` in base-32, zero-padded to exactly `width` digits. */
function toFixedWidthBase32(slot: number, width: number): string {
  let x = slot;
  const chars: string[] = [];
  for (let i = 0; i < width; i++) {
    chars.push(POSITION_ALPHABET.charAt(x % BASE));
    x = Math.floor(x / BASE);
  }
  chars.reverse();
  return chars.join("");
}

/**
 * Compute the new position of a block moved into a slot defined by its
 * neighbors (the API batch handler and the editor DnD layer both use this so
 * the rule lives in one place):
 *
 * - `before` + `after` → midpoint between them.
 * - `before` only → append after it.
 * - `after` only → prepend before it (midpoint from the lower anchor).
 * - neither → fresh position `"a0"`.
 */
export function positionForSlotNeighbors(
  before?: Position | null,
  after?: Position | null,
): Position {
  if (before && after) return betweenPosition(before, after);
  if (before) return afterPosition(before);
  if (after) return betweenPosition(minPosition(), after);
  return generatePosition();
}

/** Sort a list of positions ascending. */
export function sortPositions(positions: readonly Position[]): Position[] {
  return [...positions].sort(comparePositions);
}