/**
 * The jump network — the galaxy's highway layer (config: data/gates.json).
 *
 * Given the roster (a 2-D map of star systems) this builds, for EVERY
 * system, the list of OTHER systems its jump gates jump to, subject to:
 *
 *   LOCAL    — a gate only ever jumps to a star in the system's own
 *              neighbor pool (its `pool` nearest stars, or one that lists
 *              the system among ITS nearest — the symmetric union). The
 *              gate then sits on the side of the system facing that star
 *              (SystemGenerator.layoutGates), so "upper-right gate" means
 *              "a star to the upper right on the map".
 *   COMPLETE — no closed systems, no trapped sets: the directed graph is
 *              STRONGLY CONNECTED — from any star the player can reach
 *              any other (dev/jumps.test.mjs verifies forward AND
 *              backward reachability from the home system).
 *   BOUNDED  — minGates ≤ gates(system) ≤ maxGates (1..3 in practice).
 *   MAZE     — with shortcuts OFF (the current config, data/gates.json →
 *              shortcuts:false) the graph is a PURE SPANNING TREE: exactly
 *              one route between any two systems, no closed loops. The
 *              galaxy reads as a maze of dead ends and long hauls — and
 *              every barren system (the `barren` set, gate-only dead ends)
 *              is a LEAF: exactly one gate, in and out the same way.
 *   BRIDGES  — the deliberate exception to the maze (data/gates.json →
 *              bridges): cross-branch links in the MIDDLE belt of the
 *              galaxy. A branch is a top-level subtree of the tree (a
 *              subtree rooted at one of the home system's gate
 *              neighbors); without bridges, branch-to-branch travel means
 *              ALL the way back to the trunk (home). For each pair of
 *              branches, `perPair` bidirectional gate-pairs join two
 *              systems of the middle belt (record.d in dMin..dMax), so
 *              the branches interconnect around the middle of the galaxy
 *              (a triangle, for three branches) and a branch-to-branch
 *              trip is ONE EXTRA HOP, not a trek to the trunk — the
 *              faction design's "reach each other without routing through
 *              home" (data/factions.json). Hard rules: both ends in each
 *              other's neighbor pool (the LOCAL rule — a bridge is still
 *              a gate to a NEAR star, like any other), both ends
 *              non-barren (a dead end keeps its single gate), both ends
 *              within the maxGates budget (the cap never breaks). Soft
 *              rule: the middle-belt preference — an out-of-band pool
 *              pair is the fallback; a pair with NO pool candidate
 *              degrades (a console note — the maze still connects them).
 *              Each bridge runs BOTH ways (a return gate at each end —
 *              the "every jump has a return gate" rule), so planRoute's
 *              Dijkstra simply prefers the shorter of bridge vs trunk —
 *              the maze gains loops by design, nothing else changes.
 *   PURE     — no Math.random: every tie is broken by index. Same seed
 *              ⇒ same network (deterministic across machines and runs).
 *
 * Construction:
 *   1. The undirected neighbor graph (u~v iff v ∈ nn(u) or u ∈ nn(v)).
 *   2. A spanning tree of it with every node's degree ≤ maxGates, grown
 *      BFS-outward from the home system with a "save the stranded first"
 *      child heuristic: attach the unvisited neighbor with the FEWEST
 *      unvisited non-barren neighbors (its other possible adopters)
 *      first — a star nobody else can adopt must not wait for a budget
 *      slot. Ties keep the "keep the frontier open" order (most unvisited
 *      neighbors first — they grow the tree for others). A BARREN node
 *      never adopts children (it keeps its single gate — the maze's
 *      dead end).
 *   3. Tree edges run BOTH ways. A bidirected tree is strongly connected
 *      by construction (the unique tree path between any two systems can
 *      be walked in either direction), and every node's gate count is its
 *      tree degree — at least 1 (no isolated node) and at most maxGates.
 *      Every jump therefore has a RETURN gate (the destination's gate
 *      pointing back), so the player can always jump back the way they
 *      came.
 *   4. Optional SHORTCUTS (OFF in the current config): any spare degree
 *      budget (nodes under maxGates) buys extra one-way local edges — the
 *      web, not just the roads. Adding edges never removes reachability,
 *      so the strong connectivity survives.
 *   5. Optional BRIDGES (ON in the current config): the cross-branch
 *      middle-belt links described above — the "don't go back to the
 *      trunk" routes. They add loops to the tree; everything downstream
 *      (planRoute's Dijkstra, the strong-connectivity proof, the gate
 *      counts) already copes, because a bridge is just two more local
 *      gates.
 *
 * The repair pass (below) is defensive: it fires only if the neighbor
 * graph is disconnected (effectively impossible at this scale), and it
 * NEVER breaks the invariants: it only ever attaches to NON-BARREN nodes
 * (a dead end keeps its single gate — even in repair), and its swap
 * option re-homes a child onto a node outside the child's own subtree
 * (the tree stays a tree).
 */

/**
 * Build the gate network over the roster.
 * @param {object} o
 * @param {Array<{id:string, x:number, y:number}>} o.records — the star roster.
 * @param {(id:string) => Array<{id:string}>} o.knn — a system's nearest
 *   neighbors (its neighbor pool; `pool` is the expected pool size, only
 *   used to validate).
 * @param {number} [o.minGates=1] — validation bound.
 * @param {number} [o.maxGates=3] — hard degree budget per node.
 * @param {boolean} [o.shortcuts=true] — spend spare budget on extra local edges.
 * @param {Set<string>|null} [o.barren] — the gate-only dead-end systems
 *   (objectCount → 0, from the composition roll): a barren node never
 *   adopts children, so it ends up a tree LEAF — exactly one gate, in and
 *   out the same way (the maze's dead ends). The repair pass prefers to
 *   attach leftovers to non-barren nodes, and a barren system is never a
 *   bridge endpoint.
 * @param {string|null} [o.rootId] — grow the tree from this system (the home
 *   system) — it then keeps the lowest possible degree. Branches (for the
 *   bridge pass) are the subtrees rooted at this system's gate neighbors.
 * @param {object|null} [o.bridges] — the bridge config (data/gates.json →
 *   bridges): { enabled, perPair, dMin, dMax }. When enabled, perPair
 *   bidirectional gate-pairs link each pair of branches through the
 *   middle belt (record.d in dMin..dMax), under the LOCAL + BUDGET rules.
 * @returns {{ gates: Map<string, string[]>, repaired: number, bridges: Array<[string, string]>, branches: string[], branchOf: Map<string, string>, depth: Map<string, number> }}
 *   gates: system id → ordered list of gate destinations (parent edge
 *   first — "the road home" — then children/shortcuts, then the bridge
 *   gates).
 *   repaired: systems that needed the defensive attach (0 on real data).
 *   bridges: the bridge pairs actually placed (each pair = one gate on
 *   each end; both ends' gate lists carry the other).
 *   branches: the tree's top-level branch roots (the home system's gate
 *   neighbors), sorted — the faction pass's branch vocabulary
 *   (data/factions.json).
 *   branchOf: system id → its branch root id (the depth-1 ancestor on the
 *   SPANNING TREE — the exact tree the bridge pass used, NOT a BFS over
 *   the final gate list: the bridges add loops, and a BFS over the final
 *   graph can re-parent systems across branches, which is NOT the
 *   branch structure the faction pass assigns).
 *   depth: system id → tree depth from home (0 = home, 1 = the ring
 *   outside home) — the territory rule's bounds (depth 2 … maxDepth−1)
 *   are measured on THIS tree.
 */
export function buildJumpNetwork({
  records,
  knn,
  minGates = 1,
  maxGates = 3,
  shortcuts = true,
  barren = null,
  rootId = null,
  bridges = null,
}) {
  const n = records.length;
  const isBarren = (i) => barren instanceof Set && barren.has(records[i].id);
  const idx = new Map();
  records.forEach((r, i) => idx.set(r.id, i));
  const iOf = (id) => {
    const i = idx.get(id);
    if (i === undefined) throw new Error(`Unknown system "${id}" in jump network`);
    return i;
  };

  // Directed k-nearest per node, as indices.
  const out = new Array(n);
  for (let i = 0; i < n; i++) out[i] = knn(records[i].id).map((r) => iOf(r.id));
  // Reverse links (who lists me) — the undirected neighborhood is the union.
  const rev = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) for (const j of out[i]) rev[j].push(i);
  const nbr = new Array(n);
  for (let i = 0; i < n; i++) {
    const seen = new Set(out[i]);
    nbr[i] = out[i].slice();
    for (const j of rev[i]) {
      if (!seen.has(j)) {
        seen.add(j);
        nbr[i].push(j);
      }
    }
  }

  // A single-system "galaxy": no one to jump to (the minGates rule is
  // vacuous — there is no other star in existence).
  if (n <= 1) {
    const gates = new Map();
    for (const r of records) gates.set(r.id, []);
    return { gates, repaired: 0, bridges: [], branches: [], branchOf: new Map(), depth: new Map() };
  }

  const root = rootId ? iOf(rootId) : 0;
  const visited = new Uint8Array(n);
  const parent = new Int32Array(n).fill(-1);
  const deg = new Uint8Array(n);

  // --- The degree-limited spanning tree (BFS from the home system) ------
  const queue = [root];
  visited[root] = 1;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    if (isBarren(u)) continue; // a dead end never adopts children (it keeps its single gate)
    const budget = maxGates - deg[u];
    if (budget <= 0) continue;
    const cands = nbr[u].filter((v) => !visited[v]);
    if (cands.length === 0) continue;
    // "Save the stranded first": attach the candidate with the FEWEST
    // unvisited non-barren neighbors — those are the stars no one else
    // can adopt (barren leaves never adopt; claimed nodes can't), and
    // letting them wait is how pockets strand. Ties keep the old
    // "keep the frontier open" order (most unvisited neighbors first —
    // they grow the tree for others), then index (determinism).
    const scored = cands.map((v) => {
      let risk = 0; // unvisited NON-BARREN neighbors of v (its other adopters)
      let unv = 0;
      for (const w of nbr[v]) {
        if (visited[w]) continue;
        unv++;
        if (!isBarren(w)) risk++;
      }
      return { v, risk, unv };
    });
    scored.sort((a, b) => a.risk - b.risk || b.unv - a.unv || a.v - b.v);
    for (const { v } of scored.slice(0, budget)) {
      visited[v] = 1;
      parent[v] = u;
      deg[u]++;
      deg[v]++;
      queue.push(v);
    }
  }

  // --- Repair (defensive): attach anything the tree left behind ---------
  // A leftover node has no visited neighbor with spare degree (its whole
  // neighborhood sat in a disconnected pocket). Repair, in order of
  // preference (all deterministic — index order, strict comparisons). A
  // barren node is NEVER an attach target — a dead end keeps its single
  // gate, even in repair:
  //   1. Attach to a visited NON-BARREN neighbor with spare degree (local).
  //   2. SWAP: take one of a visited node u's tree children x, re-home x
  //      onto one of x's OWN visited NON-BARREN neighbors that has spare
  //      degree (and sits outside x's own subtree — no cycles), and use
  //      the freed budget for w. The tree stays a tree; locality is
  //      preserved (x stays inside its own neighborhood).
  //   3. Last resort (should never fire on a kNN graph): attach w to the
  //      nearest visited NON-BARREN node and accept one over-budget degree
  //      — a working network beats a broken one.
  const dist2 = (a, b) => {
    const dx = records[a].x - records[b].x;
    const dy = records[a].y - records[b].y;
    return dx * dx + dy * dy;
  };
  let repaired = 0;
  // Is `a` inside `anc`'s subtree (a ≠ anc)? — the swap must not re-home
  // a child onto one of its own descendants (that would close a cycle).
  const inSubtree = (a, anc) => {
    let p = parent[a];
    while (p >= 0) {
      if (p === anc) return true;
      p = parent[p];
    }
    return false;
  };
  for (let w = 0; w < n; w++) {
    if (visited[w]) continue;
    // (1) local attach — a barren neighbor is NEVER a target: a dead end
    // keeps its single gate, even in repair.
    let u = -1;
    for (const c of nbr[w]) if (visited[c] && deg[c] < maxGates && !isBarren(c)) { u = c; break; }
    if (u === -1) {
      // (2) swap: best (u, x) pair by dist(w, u), then indices. The new
      // parent (bestNew) must have spare degree, be non-barren, and sit
      // outside x's subtree.
      let bestU = -1, bestX = -1, bestNew = -1, bestD = Infinity;
      for (let c = 0; c < n; c++) {
        if (!visited[c] || c === w || deg[c] < 2) continue; // needs a child to free
        const d = dist2(w, c);
        if (d > bestD) continue;
        // children of c in the tree (visited nodes whose parent is c)
        for (let x = 0; x < n; x++) {
          if (parent[x] !== c) continue;
          for (const nn of nbr[x]) {
            if (nn === c || nn === w || nn === x) continue;
            if (!visited[nn] || isBarren(nn) || deg[nn] >= maxGates) continue;
            if (inSubtree(nn, x)) continue; // re-homing here would close a cycle
            if (d < bestD || (d === bestD && (c < bestU || (c === bestU && x < bestX)))) {
              bestD = d; bestU = c; bestX = x; bestNew = nn;
            }
          }
        }
      }
      if (bestU !== -1) {
        parent[bestX] = bestNew; // re-home the child
        deg[bestU]--;
        deg[bestNew]++;
        u = bestU;
      }
    }
    if (u === -1) {
      // (3) nearest visited NON-BARREN node, budget be damned
      let bestD = Infinity;
      let found = -1;
      for (let c = 0; c < n; c++) {
        if (!visited[c] || c === w || isBarren(c)) continue;
        const d = dist2(w, c);
        if (d < bestD) { bestD = d; found = c; }
      }
      if (found === -1) {
        // (4) truly nothing else (effectively unreachable on a kNN graph):
        // strong connectivity beats the leaf invariant — take ANY visited
        // node, budget be damned.
        for (let c = 0; c < n; c++) {
          if (!visited[c] || c === w) continue;
          const d = dist2(w, c);
          if (d < bestD) { bestD = d; found = c; }
        }
      }
      if (found === -1) continue; // nothing to attach to (n === 1 handled above)
      u = found;
      console.warn(`[orbit] jump network: forced attach of ${records[w].id} (degree budget exceeded)`);
    }
    visited[w] = 1;
    parent[w] = u;
    deg[u]++;
    deg[w]++;
    repaired++;
  }

  // --- Shortcuts: the spare budget buys extra one-way local edges --------
  const shortcutsOf = Array.from({ length: n }, () => []);
  if (shortcuts) {
    const linked = new Set();
    for (let i = 0; i < n; i++) if (parent[i] >= 0) linked.add(key(i, parent[i]));
    for (let u = 0; u < n; u++) {
      for (const v of out[u]) {
        if (deg[u] >= maxGates) break;
        if (linked.has(key(u, v))) continue; // already linked, either way
        linked.add(key(u, v));
        shortcutsOf[u].push(v);
        deg[u]++;
      }
    }
  }

  // --- Branches + tree depth (the faction pass's vocabulary) ----------
  // A BRANCH is a top-level subtree of the spanning tree: the subtree
  // rooted at one of the home system's gate neighbors (depth 1). Walk the
  // parent chain up to the root's child: the tree is acyclic, so this is
  // exact. Exposed (branches / branchOf / depth below) because the
  // faction pass (js/galaxy/Galaxy.js → _assignFactions) + the bridge
  // pass must agree on the SAME branch structure — a BFS over the FINAL
  // gate list (tree + bridges) can re-parent systems across branches
  // (the bridges are loops), which is not the tree's branch structure.
  const branchOfArr = new Int32Array(n).fill(-1);
  const depthArr = new Int32Array(n).fill(-1);
  depthArr[root] = 0;
  for (let i = 0; i < n; i++) {
    if (i === root || parent[i] < 0) continue;
    let b = i;
    while (parent[b] >= 0 && parent[b] !== root) b = parent[b];
    if (parent[b] === root) branchOfArr[i] = b;
  }
  for (let i = 0; i < n; i++) {
    if (i === root) continue;
    let d = 0;
    let cur = i;
    while (parent[cur] >= 0) { d++; cur = parent[cur]; }
    if (cur === root) depthArr[i] = d;
  }
  const branchList = [];
  {
    const seen = new Set();
    for (let i = 0; i < n; i++) {
      const b = branchOfArr[i];
      if (b !== -1 && !seen.has(b)) {
        seen.add(b);
        branchList.push(b);
      }
    }
  }
  branchList.sort((a, b) => a - b);

  // --- Bridges: the cross-branch middle-belt links (data/gates.json →
  // bridges — see the BRIDGES constraint above) --------------------------
  // Two hard constraints, both preserved: LOCAL (both ends sit in each
  // other's neighbor pool — `nbr`, the symmetric union: a bridge is still
  // a gate to a NEAR star, like any other) and BUDGET (both ends keep
  // degree ≤ maxGates — the cap never breaks; a barren dead end is never
  // an endpoint — it keeps its single gate). Soft: both ends in the
  // middle belt (record.d in dMin..dMax); an out-of-band pool pair is the
  // fallback, and a pair with NO pool candidate degrades (a console note).
  // The bridge list drives the gate assembly below; each bridge runs BOTH
  // ways (the return-gate rule) — planRoute's Dijkstra picks the shorter
  // of bridge vs trunk automatically, so nothing else changes.
  const bridgesPlaced = [];
  const bCfg = bridges && bridges.enabled !== false ? bridges : null;
  const perPair = bCfg ? Math.max(0, Math.floor(Number(bCfg.perPair) || 0)) : 0;
  if (perPair > 0 && n > 1 && root >= 0) {
    const dOf = (i) => (Number.isFinite(Number(records[i].d)) ? Number(records[i].d) : 0.5);
    const dMin = Number(bCfg.dMin ?? 0.37);
    const dMax = Number(bCfg.dMax ?? 0.63);
    const inBand = (i) => dOf(i) >= dMin && dOf(i) <= dMax;
    for (let bi = 0; bi < branchList.length; bi++) {
      for (let bj = bi + 1; bj < branchList.length; bj++) {
        const A = branchList[bi], B = branchList[bj];
        // Candidate pool: every (u in branch A, v in branch B) whose ends
        // are LOCAL (v ∈ nbr[u]) — non-barren, never the home root. Sort:
        // middle-belt pairs first (the soft preference), then nearest,
        // then indices (determinism).
        const cands = [];
        for (let u = 0; u < n; u++) {
          if (branchOfArr[u] !== A || isBarren(u) || u === root) continue;
          for (const v of nbr[u]) {
            if (branchOfArr[v] !== B || isBarren(v) || v === root) continue;
            cands.push({ u, v, band: inBand(u) && inBand(v), d: dist2(u, v) });
          }
        }
        cands.sort((p, q) =>
          (p.band === q.band ? 0 : p.band ? -1 : 1) ||
          p.d - q.d ||
          p.u - q.u ||
          p.v - q.v);
        // Prefer two DISTINCT endpoints (two real alternative routes);
        // only reuse an endpoint on the second pass (budget left over —
        // the "two bridges per pair" redundancy degrades gracefully).
        const usedEnds = new Set();
        let added = 0;
        for (let pass = 0; pass < 2 && added < perPair; pass++) {
          for (const c of cands) {
            if (added >= perPair || c.added) continue;
            if (pass === 0 && (usedEnds.has(c.u) || usedEnds.has(c.v))) continue;
            if (deg[c.u] >= maxGates || deg[c.v] >= maxGates) continue; // BUDGET
            c.added = true;
            deg[c.u]++;
            deg[c.v]++;
            usedEnds.add(c.u);
            usedEnds.add(c.v);
            bridgesPlaced.push([records[c.u].id, records[c.v].id]);
            added++;
          }
        }
        if (added < perPair && cands.length === 0) {
          // No LOCAL candidate at all for this pair — the pair degrades
          // to the maze (the tree still connects the two branches via the
          // trunk). A budget shortfall (cands exist, none fit) is the
          // normal, designed degradation and stays quiet.
          console.warn(`[orbit] jump network: no bridge pool between branches ${records[A].id} and ${records[B].id}`);
        }
      }
    }
  }

  // --- Assemble ----------------------------------------------------------
  // Each node's gates = the tree edges touching it — its parent first ("the
  // road home"), then its tree children in index order — plus its
  // shortcuts, then its bridge gates. A bidirected spanning tree is strongly
  // connected by construction (the unique tree path between any two systems
  // is walkable in both directions), so every system both reaches and is
  // reachable; the bridges add loops on top (Dijkstra then prefers the
  // shorter of the two routes); every node's gate count is its tree degree
  // (≥ 1 for n > 1, ≤ maxGates) plus any shortcuts/bridges it bought.
  const children = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) if (parent[i] >= 0) children[parent[i]].push(i);
  const gates = new Map();
  for (let i = 0; i < n; i++) {
    const targets = [];
    if (parent[i] >= 0) targets.push(records[parent[i]].id);
    for (const c of children[i].sort((a, b) => a - b)) targets.push(records[c].id);
    for (const v of shortcutsOf[i]) targets.push(records[v].id);
    for (const br of bridgesPlaced) {
      if (br[0] === records[i].id) targets.push(br[1]);
      else if (br[1] === records[i].id) targets.push(br[0]);
    }
    if (targets.length < minGates && n > 1) {
      // Can't happen (tree degree ≥ 1), but never emit a closed system.
      throw new Error(`Jump network left system ${records[i].id} with ${targets.length} gate(s) < minGates ${minGates}`);
    }
    gates.set(records[i].id, targets);
  }
  const branchOfMap = new Map();
  const depthMap = new Map();
  for (let i = 0; i < n; i++) {
    if (branchOfArr[i] !== -1) branchOfMap.set(records[i].id, records[branchOfArr[i]].id);
    if (depthArr[i] >= 0) depthMap.set(records[i].id, depthArr[i]);
  }
  return {
    gates,
    repaired,
    bridges: bridgesPlaced,
    branches: branchList.map((i) => records[i].id),
    branchOf: branchOfMap,
    depth: depthMap,
  };
}

const key = (a, b) => (a < b ? a : b) + '\u0000' + (a < b ? b : a);