#!/usr/bin/env node
/* Branch-only directional ALT experiment. Neither production nor integrations import this. */
import { readFileSync, existsSync, writeFileSync, unlinkSync } from 'node:fs';
import { createHash } from 'node:crypto';
import { hostname } from 'node:os';
import { fileURLToPath } from 'node:url';
import { decodeGraph } from '../src/graph.ts';
import { haversineM } from '../src/geo.ts';
import { snapToGraph } from '../src/snap.ts';
import { routeAstar } from '../src/astar.ts';
import { generateCrossMetroPairs } from './measure-optimality-baseline.mjs';
import { sweepOracle } from './measure-astar-oracle-sweep.mjs';

// Source-identical isolated instrumented clone: only two settled counters are injected.
// The production file is never opened for writing; remove the ephemeral copy in finally.
async function instrumentedShipped() {
  const source = new URL('../src/astar.ts', import.meta.url);
  const clone = new URL('../src/astar-alt-measure.tmp.ts', import.meta.url);
  let code = readFileSync(source, 'utf8');
  const forward = 'if (expandForward) fClosed[u] = 1;', backward = 'else bClosed[u] = 1;';
  if (!code.includes(forward) || !code.includes(backward)) throw Error('production settled markers changed; instrumentation not valid');
  code = code.replace(forward, 'if (expandForward) { fClosed[u] = 1; globalThis.__altControlSettled.forward++; }')
    .replace(backward, 'else { bClosed[u] = 1; globalThis.__altControlSettled.backward++; }');
  if (existsSync(clone)) throw Error('temporary instrumentation clone already exists');
  try {
    writeFileSync(clone, code, { flag: 'wx' });
    return await import(clone.href);
  } finally { if (existsSync(clone)) unlinkSync(clone); }
}

const INF = Infinity, SENTINEL = 0xffff;
class Heap {
  a = [];
  push(k, g, v) {
    const a = this.a; let i = a.length; a.push({ k, g, v }); const x = a[i];
    while (i) { const p = (i - 1) >> 1; if (a[p].k <= k) break; a[i] = a[p]; i = p; } a[i] = x;
  }
  pop() {
    const a = this.a, top = a[0], x = a.pop();
    if (a.length) { let i = 0; for (;;) { let j = i * 2 + 1; if (j >= a.length) break; if (j + 1 < a.length && a[j + 1].k < a[j].k) j++; if (a[j].k >= x.k) break; a[i] = a[j]; i = j; } a[i] = x; }
    return top;
  }
  peek(dist, closed) { while (this.a.length && (closed[this.a[0].v] || dist[this.a[0].v] !== this.a[0].g)) this.pop(); return this.a[0]?.k ?? INF; }
}

const reverseCache = new WeakMap();
function reverse(graph) {
  if (reverseCache.has(graph)) return reverseCache.get(graph);
  const rows = new Uint32Array(graph.nodeCount + 1);
  for (let e = 0; e < graph.edgeCount; e++) rows[graph.edgeTarget[e] + 1]++;
  for (let v = 0; v < graph.nodeCount; v++) rows[v + 1] += rows[v];
  const source = new Uint32Array(graph.edgeCount), ids = new Uint32Array(graph.edgeCount), cursor = rows.slice(0, -1);
  for (let u = 0; u < graph.nodeCount; u++) for (let e = graph.edgeStart[u]; e < graph.edgeStart[u + 1]; e++) {
    const pos = cursor[graph.edgeTarget[e]]++; source[pos] = u; ids[pos] = e;
  }
  const result = { rows, source, ids }; reverseCache.set(graph, result); return result;
}

/** Returns null on an unreachable pair; throws on a violated proof assumption. */
export function routeDirectionSplit(graph, o, g) {
  const n = graph.nodeCount;
  if (!Number.isInteger(o) || !Number.isInteger(g) || o < 0 || g < 0 || o >= n || g >= n) return null;
  if (o === g) return { nodes: [o], seconds: 0, expansionsForward: 0, expansionsBackward: 0, activeTo: 0, activeFrom: 0 };
  const T = [], F = [], Q = graph.landmarkQuantumS;
  for (let l = 0; l < graph.landmarkCount; l++) {
    const base = l * n;
    if (graph.landmarkTo[base + g] !== SENTINEL) {
      if (graph.landmarkTo[base + o] === SENTINEL) return null;
      T.push([base, graph.landmarkTo[base + g]]);
    }
    if (graph.landmarkFrom[base + o] !== SENTINEL) {
      if (graph.landmarkFrom[base + g] === SENTINEL) return null;
      F.push([base, graph.landmarkFrom[base + o]]);
    }
  }
  const domain = new Int8Array(n);
  function inside(v) {
    if (domain[v]) return domain[v] === 1;
    for (const [base] of T) if (graph.landmarkTo[base + v] === SENTINEL) { domain[v] = -1; return false; }
    for (const [base] of F) if (graph.landmarkFrom[base + v] === SENTINEL) { domain[v] = -1; return false; }
    domain[v] = 1; return true;
  }
  const scale = 3.6 / graph.maxSpeedKmh;
  if (!(scale > 0 && Number.isFinite(scale))) throw Error('nonpositive graph maxSpeedKmh');
  const hf = new Float64Array(n).fill(NaN), hb = new Float64Array(n).fill(NaN);
  function heuristic(v, forward) {
    const cache = forward ? hf : hb;
    if (!Number.isNaN(cache[v])) return cache[v];
    const target = forward ? g : o;
    let h = haversineM({ lat: graph.lat[v], lng: graph.lng[v] }, { lat: graph.lat[target], lng: graph.lng[target] }) * scale;
    for (const [base, constant] of (forward ? T : F)) {
      const cell = (forward ? graph.landmarkTo : graph.landmarkFrom)[base + v];
      if (cell === SENTINEL) throw Error('sentinel in included domain');
      h = Math.max(h, (cell - constant) * Q);
    }
    cache[v] = h; return h;
  }
  const df = new Float64Array(n).fill(INF), db = new Float64Array(n).fill(INF);
  const prev = new Int32Array(n).fill(-1), next = new Int32Array(n).fill(-1);
  const cf = new Uint8Array(n), cb = new Uint8Array(n), a = new Heap(), b = new Heap(), rev = reverse(graph);
  df[o] = 0; db[g] = 0; a.push(heuristic(o, true), 0, o); b.push(heuristic(g, false), 0, g);
  let U = INF, meeting = -1, expansionsForward = 0, expansionsBackward = 0;
  while (true) {
    const fa = a.peek(df, cf), bb = b.peek(db, cb);
    if (fa === INF || bb === INF || fa >= U || bb >= U) break;
    const forward = a.a.length <= b.a.length;
    const heap = forward ? a : b, distances = forward ? df : db, other = forward ? db : df;
    const closed = forward ? cf : cb, chain = forward ? prev : next;
    const u = heap.pop().v, du = distances[u]; closed[u] = 1;
    if (forward) expansionsForward++; else expansionsBackward++;
    if (du + other[u] < U) { U = du + other[u]; meeting = u; }
    const start = forward ? graph.edgeStart[u] : rev.rows[u], end = forward ? graph.edgeStart[u + 1] : rev.rows[u + 1];
    for (let r = start; r < end; r++) {
      const e = forward ? r : rev.ids[r];
      if (graph.edgeFlags[e] & 1) continue;
      const v = forward ? graph.edgeTarget[e] : rev.source[r];
      if (!inside(v)) continue;
      const seconds = graph.edgeSeconds[e];
      // Enforce both directed inequalities on each inspected edge. Tiny f64 rounding tolerance only in assertion.
      const delta = heuristic(u, forward) - heuristic(v, forward);
      if (delta > seconds + 1e-7) throw Error(`inconsistent ${forward ? 'forward' : 'backward'} potential ${u}->${v}: delta=${delta}, seconds=${seconds}, Q=${Q}`);
      const tentative = du + seconds;
      if (tentative < distances[v]) {
        if (closed[v]) throw Error('improved closed label');
        distances[v] = tentative; chain[v] = u; heap.push(tentative + heuristic(v, forward), tentative, v);
      }
      if (distances[v] + other[v] < U) { U = distances[v] + other[v]; meeting = v; }
    }
  }
  if (meeting < 0) return null;
  const left = []; for (let v = meeting; v !== -1; v = prev[v]) left.push(v); left.reverse();
  const right = []; for (let v = next[meeting]; v !== -1; v = next[v]) right.push(v);
  const nodes = left.concat(right);
  let seconds = 0;
  for (let i = 1; i < nodes.length; i++) {
    let e = graph.edgeStart[nodes[i - 1]], end = graph.edgeStart[nodes[i - 1] + 1];
    while (e < end && (graph.edgeTarget[e] !== nodes[i] || (graph.edgeFlags[e] & 1))) e++;
    if (e === end) throw Error('invalid reconstructed edge');
    seconds += graph.edgeSeconds[e];
  }
  if (Math.abs(seconds - U) > 1e-6) throw Error(`reconstructed seconds mismatch: ${seconds} vs ${U}`);
  return { nodes, seconds, expansionsForward, expansionsBackward, activeTo: T.length, activeFrom: F.length };
}

export function dijkstra(graph, o, g) {
  const dist = new Float64Array(graph.nodeCount).fill(INF), closed = new Uint8Array(graph.nodeCount), heap = new Heap();
  dist[o] = 0; heap.push(0, 0, o);
  while (heap.peek(dist, closed) !== INF) {
    const u = heap.pop().v; if (u === g) return dist[u]; closed[u] = 1;
    for (let e = graph.edgeStart[u]; e < graph.edgeStart[u + 1]; e++) {
      if (graph.edgeFlags[e] & 1) continue;
      const v = graph.edgeTarget[e], nd = dist[u] + graph.edgeSeconds[e];
      if (nd < dist[v]) { dist[v] = nd; heap.push(nd, nd, v); }
    }
  }
  return INF;
}

if (process.argv[1] && fileURLToPath(import.meta.url) === process.argv[1]) {
  const path = new URL('../data/kl-roadgraph.v1.bin', import.meta.url);
  if (!existsSync(path)) { console.error('NOT MEASURED: missing ARG2 binary'); process.exitCode = 2; }
  else {
    const bytes = readFileSync(path), graph = decodeGraph(bytes.buffer.slice(bytes.byteOffset, bytes.byteOffset + bytes.byteLength));
    if (!graph) { console.error('NOT MEASURED: undecodable ARG2 binary'); process.exitCode = 2; }
    else {
      console.log(`host=${hostname()} node=${process.version} sha256=${createHash('sha256').update(bytes).digest('hex')} graph=${graph.nodeCount}/${graph.edgeCount}`);
      const raw = generateCrossMetroPairs(graph.bbox, { count: 600, seed: 0x08f1, minPairKm: 12, haversineM });
      const pairs = [], missing = { snap: 0 };
      for (const pair of raw) { if (pairs.length === 200) break; if (!snapToGraph(graph, pair.origin) || !snapToGraph(graph, pair.destination)) missing.snap++; else pairs.push(pair); }
      if (pairs.length < 200) throw Error(`only ${pairs.length}/200 snapped pairs`);
      const verdict = sweepOracle(graph, pairs, { snap: snapToGraph, astar: routeDirectionSplit, oracle: dijkstra });
      console.log(`oracle: compared=${pairs.length} snap-miss=${missing.snap} routed=${verdict.routed} unreachable=${verdict.unreachable} suboptimal=${verdict.suboptimal} oracle-mismatch=${verdict.oracleMismatch} class-break=${verdict.classBreaks} pass=${verdict.pass}`);
      if (!verdict.pass) { console.error(verdict.rows.filter(r => !['pass', 'unreachable'].includes(r.verdict))); process.exitCode = 1; }
      globalThis.__altControlSettled = { forward: 0, backward: 0 };
      const control = (await instrumentedShipped()).routeAstar;
      const extended = generateCrossMetroPairs(graph.bbox, { count: 100, seed: 0x08a1, minPairKm: 12, haversineM });
      const warm = (fn) => { const a = process.hrtime.bigint(); fn(); return Number(process.hrtime.bigint() - a) / 1e6; };
      const warmExp = warm(() => routeDirectionSplit(graph, 0, 1));
      const warmShipped = warm(() => routeAstar(graph, 0, 1));
      const warmClone = warm(() => control(graph, 0, 1));
      console.log(`warm-up ms (unmeasured): experimental=${warmExp.toFixed(3)} original-shipped=${warmShipped.toFixed(3)} instrumented-clone=${warmClone.toFixed(3)}`);
      globalThis.__altControlSettled = { forward: 0, backward: 0 };
      const times = [[], [], []], counts = [0, 0], misses = { snap: 0, unreachable: 0 }, active = [0, 0];
      for (let round = 0; round < 2; round++) for (let i = 0; i < extended.length; i++) {
        const pair = extended[i], s = snapToGraph(graph, pair.origin), t = snapToGraph(graph, pair.destination);
        if (!s || !t) { if (round === 0) misses.snap++; continue; }
        const results = [];
        for (const k of ((i + round) % 2 ? [2, 1, 0] : [0, 1, 2])) {
          const st = process.hrtime.bigint(), result = k === 0 ? routeDirectionSplit(graph, s.node, t.node) : k === 1 ? control(graph, s.node, t.node) : routeAstar(graph, s.node, t.node);
          const ms = Number(process.hrtime.bigint() - st) / 1e6; results[k] = { result, ms };
        }
        if (results[0].result === null || results[1].result === null || results[2].result === null) {
          if (results[0].result !== results[1].result || results[0].result !== results[2].result) throw Error(`paired reachability mismatch ${pair.pairId}`);
          if (round === 0) misses.unreachable++; continue;
        }
        if (Math.abs(results[0].result.seconds - results[1].result.seconds) > 1e-6 || Math.abs(results[1].result.seconds - results[2].result.seconds) > 1e-6) throw Error(`paired cost mismatch ${pair.pairId}`);
        for (let k = 0; k < 3; k++) times[k].push(results[k].ms);
        counts[0] += results[0].result.expansionsForward + results[0].result.expansionsBackward;
        active[0] += results[0].result.activeTo; active[1] += results[0].result.activeFrom;
      }
      const stats = a => { a.sort((x, y) => x - y); return `n=${a.length} median=${a[Math.floor(a.length / 2)].toFixed(3)} mean=${(a.reduce((x,y) => x + y,0)/a.length).toFixed(3)} p95=${a[Math.ceil(a.length * .95)-1].toFixed(3)} ms`; };
      console.log(`extended snap-miss=${misses.snap} unreachable=${misses.unreachable} (outside routed p95), 2 alternating rounds`);
      console.log(`experimental: ${stats(times[0])} expansions=${counts[0]} active-to/from=${active.join('/')}`);
      counts[1] = globalThis.__altControlSettled.forward + globalThis.__altControlSettled.backward;
      console.log(`shipped isolated instrumented clone: ${stats(times[1])} expansions=${counts[1]} forward/backward=${globalThis.__altControlSettled.forward}/${globalThis.__altControlSettled.backward}; experimental/control expansion ratio=${(counts[0]/counts[1]).toFixed(3)}`);
      console.log(`original shipped routeAstar (paired unmodified haversine-only control): ${stats(times[2])}`);
    }
  }
}