482 lines
22 KiB
JavaScript
482 lines
22 KiB
JavaScript
/**
|
||
* 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);
|