/**
 * Fractional (LexoRank-style) positions over base-62 strings.
 *
 * A position `S` maps to the value  v(S) = Σ digit(i) / 62^(i+1)  ∈ (0, 1).
 * This ordering is exactly lexicographic order (proved by the prefix
 * property: v(S+c) = v(S) + c/62^len(S) + … and the first-difference
 * property), which is also PostgreSQL/byte string order for ASCII — so
 * `ORDER BY position` works without any cast.
 *
 * `between(a, b)` computes the midpoint on a fixed grid of 62^L cells and
 * grows L (precision) until the two neighbours are not adjacent cells.
 * Nesting to arbitrary depth therefore works; the only failure mode is a
 * gap beyond 128 digits of precision, which throws and asks for a rebalance
 * (callers fall back to {@link rebalancePositions}).
 *
 * `between(a)` (append after `a`) is the hot path for "add block at the
 * END of the page" — the single most common mutation. It is a cheap,
 * non-converging extension (`a` + midpoint char), NOT a midpoint toward the
 * grid top: the latter converges on the top in one digit per append and
 * exhausts MAX_PRECISION after ~127 appends (a 93-page / 16K-word paste
 * 500'd with "position too close to the top"). With the extension rule the
 * append position keeps ~half the alphabet of headroom *below* the new
 * sibling, so interleaved inserts after an appended tail still split
 * normally, and even a million straight appends only lengthen the position
 * by ~17 characters.
 */

const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const ALPHABET_SET = new Set(ALPHABET);
const BASE = 62n;
export const MAX_PRECISION = 128;
/** Midpoint digit of the alphabet (31 → 'V'): the append extension char. */
const MID_INDEX = 31;

/** Validate a position string: non-empty base-62, bounded length. */
export function isValid(s: string): boolean {
  if (typeof s !== "string" || s.length === 0 || s.length > 512) return false;
  for (const ch of s) if (!ALPHABET_SET.has(ch)) return false;
  return true;
}

/** Lexicographic compare (== positional order): -1 | 0 | 1. */
export function compare(a: string, b: string): -1 | 0 | 1 {
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

/** Decode a position to (digits-as-base62-integer, length). */
function decode(s: string): { v: bigint; len: number } {
  let v = 0n;
  for (const ch of s) v = v * BASE + BigInt(ALPHABET.indexOf(ch));
  return { v, len: s.length };
}

/** Encode an integer as exactly `len` base-62 digits (zero-padded). */
export function encodeFixed(v: bigint, len: number): string {
  let out = "";
  for (let i = len - 1; i >= 0; i--) {
    out = ALPHABET.charAt(Number(v % BASE)) + out;
    v /= BASE;
  }
  return out;
}

/**
 * A position strictly between `a` and `b` (positional order).
 * - both omitted → first position "A"
 * - only `b`     → a position before `b`
 * - only `a`     → a position after `a`
 * Throws RangeError when the gap is beyond 128 digits of precision.
 */
export function between(a?: string, b?: string): string {
  if (!a && !b) return "A";

  if (a && !b) {
    // Append after `a` (the "add at end of the page" hot path): extend
    // `a` with one midpoint char — `a + 'V'`. The previous rule took the
    // midpoint between `a` and the grid TOP, which converged on "zzzz…"
    // (one more z per append) and exhausted MAX_PRECISION after ~127
    // appends: every large paste (93 pages / ~400 blocks) 500'd with
    // "position too close to the top". The extension is strictly greater
    // than `a` (prefix property), keeps ~half the alphabet of headroom
    // BELOW the new sibling (inserts after an appended tail still split
    // via the midpoint rules), and N straight appends add only N chars —
    // ~17 chars for a million inserts.
    if (a.length >= MAX_PRECISION) {
      throw new RangeError("position at max length — rebalance required");
    }
    return a + ALPHABET.charAt(MID_INDEX);
  }

  if (!a) {
    // Before `b`: midpoint between 0 and v(b).
    // (Unreachable unless both were omitted — handled above; type guard.)
    if (!b) return "A";
    const { v: bv, len: lb } = decode(b);
    for (let L = lb; L <= MAX_PRECISION; L++) {
      const scale = BASE ** BigInt(L);
      const b2 = bv * (scale / BASE ** BigInt(lb));
      if (b2 > 1n) {
        let mid = b2 / 2n;
        if (mid <= 0n) mid = 1n;
        if (mid < b2) return encodeFixed(mid, L);
      }
    }
    throw new RangeError("position too close to the bottom — rebalance required");
  }

  // Both sides: midpoint with growing precision.
  // (Unreachable unless `b` was omitted — that case exits above; type guard.)
  if (!b) return "A";
  const { v: av, len: la } = decode(a);
  const { v: bv, len: lb } = decode(b);
  if (compare(a, b) >= 0) throw new RangeError("between(a, b): a must sort before b");

  for (let L = Math.max(la, lb); L <= MAX_PRECISION; L++) {
    const scale = BASE ** BigInt(L);
    const a2 = av * (scale / BASE ** BigInt(la));
    const b2 = bv * (scale / BASE ** BigInt(lb));
    if (b2 - a2 > 1n) {
      const mid = (a2 + b2) / 2n;
      if (mid > a2 && mid < b2) return encodeFixed(mid, L);
    }
  }
  throw new RangeError("positions too close — rebalance required");
}

/** First position for a fresh tree. */
export function first(): string {
  return "A";
}

/**
 * Re-space a sibling list that ran out of positional headroom (positions
 * converged to 128-digit neighbours, so `between` can no longer split).
 *
 * `positions` must be the sibling list in ASCENDING order (as
 * `ORDER BY position` returns it). The result is one new position per
 * entry, equal in length and evenly spread across the 62^L grid (L = the
 * smallest precision with ≥ n·2 free cells, so every fresh position keeps
 * room for future inserts around it). Order and duplicates are preserved:
 * two rows that already share a position (a pre-existing corruption) get
 * adjacent slots, so the rebalance doubles as a repair.
 *
 * Callers run this inside the same transaction that hit the RangeError and
 * rewrite the whole sibling list — one indexed UPDATEs batch, no reindex
 * of other pages (the positions are scoped to this page/parent).
 */
export function rebalancePositions(positions: readonly string[]): string[] {
  const n = positions.length;
  if (n === 0) return [];
  // Smallest grid with at least 2 cells per row (≥1 spare on each side).
  // For any JS-sized list (n ≤ 2^53) this converges at L ≤ ~25; the
  // MAX_PRECISION guard below rejects only absurdly large inputs.
  let L = 1;
  while (BASE ** BigInt(L) < BigInt(n) * 2n) L += 1;
  if (L > MAX_PRECISION) throw new RangeError("sibling list too large to rebalance");
  const scale = BASE ** BigInt(L);
  const step = scale / BigInt(n);
  const out: string[] = [];
  for (let i = 0; i < n; i++) {
    out.push(encodeFixed(BigInt(i) * step + step / 2n, L));
  }
  return out;
}