// Data as flows: the ways data takes, and the data on its way along them. A tap or a cache sends what it has to
// the nearest machine that takes it. Which one is nearest is not searched for from each sender: once a step, for
// each kind of data, one search goes outward from every machine that has room, over machines you hold and past
// lines out with room, and marks each machine with the way to its nearest one (searched again in the step only when
// one fills up or a line on the way runs out of room). So a step costs a search for each kind of data, not one for
// every piece. Data on its way is kept for each route as a few batches, each with the time it lands: a route's
// travel time is the time its links take, so a new route fills after that. What takes the data, and in what order,
// is sim.ts's (see runBase); this file only carries it.
import type { DataType } from './world.ts';
import type { Machine, State } from './sim.ts';
import { capNow, linkKey } from './sim.ts';

/** Data on its way along one route, of one kind: from `path[0]` to the last machine on it. `due` holds batches as
 *  [time it arrives, pieces, ...], soonest first. `d`: the route's travel time. `move`: data for a home move. */
export interface Wire { path: string[]; type: DataType; move?: boolean; d: number; due: number[] }

/** Data crosses a link at this speed, or a line between sites in this many seconds, however far. */
export const SPEED = 160, LINE_TIME = 3;
/** Batches sent this close together on one route travel as one. */
const BATCH = 0.05;

/** A route from one machine to another: its machines, its travel time, its links' keys, and the lines out it
 *  passes through on each crossing between sites (both ends, so a full one holds the data back). */
export interface Route { path: string[]; d: number; keys: string[]; gates: Machine[]; id: string; at: Int32Array } // id: its machines' names, joined
/** The links as numbers: each machine's place in `S.machines`, its links, and its site. Made again when a machine
 *  arrives or a link is added (links are only ever added, to the machines' own lists). */
interface Net { of: State; list: Machine[]; adj: State['adj']; arrs: string[][]; links: Int32Array; at: Map<string, number>; off: Int32Array; to: Int32Array; site: Int32Array }
let net: Net | null = null;
function fresh(S: State, N: Net) {
  const ms = S.machines;
  if (N.of !== S || N.list !== ms || N.arrs.length !== ms.length || N.adj !== S.adj) return false;
  for (let i = 0; i < ms.length; i++) if (N.arrs[i].length !== N.links[i]) return false;
  return true;
}
function netOf(S: State): Net {
  if (net && fresh(S, net)) return net;
  const list = S.machines, n = list.length, at = new Map<string, number>(), siteIds = new Map<string, number>(), none: string[] = [];
  list.forEach((m, i) => at.set(m.id, i));
  const off = new Int32Array(n + 1), all: number[] = [], site = new Int32Array(n), links = new Int32Array(n), arrs: string[][] = [];
  for (let i = 0; i < n; i++) {
    const m = list[i], adj = S.adj[m.id] ?? none;
    off[i] = all.length; arrs.push(adj); links[i] = adj.length;
    for (const id of adj) { const j = at.get(id); if (j !== undefined) all.push(j); }
    const s = S.rooms[m.room]?.site ?? 'office';
    if (!siteIds.has(s)) siteIds.set(s, siteIds.size);
    site[i] = siteIds.get(s)!;
  }
  off[n] = all.length;
  routes.clear(); fields.clear();
  return net = { of: S, list, adj: S.adj, arrs, links, at, off, to: Int32Array.from(all), site };
}
/** How long data takes along one link. */
export function hopTime(S: State, a: Machine, b: Machine) {
  return (S.rooms[a.room]?.site ?? 'office') !== (S.rooms[b.room]?.site ?? 'office') ? LINE_TIME : Math.max(1, Math.hypot(b.x - a.x, b.y - a.y)) / SPEED;
}
/** Can one more piece of this kind pass this line out now? With a priority set, other kinds leave half its room
 *  for that kind. Any other machine lets everything by. */
function gateOpen(S: State, m: Machine, type: DataType) {
  if (m.kind !== 'egress') return true;
  return (S.gate[m.id] ?? 0) >= (m.prio && m.prio !== type ? 1 + 0.5 * Math.max(1, capNow(S, m)) : 1);
}
/** How many pieces of this kind can pass every line out on a route right now. */
export function gateRoom(S: State, r: Route, type: DataType): number {
  let k = Infinity;
  for (const g of r.gates) {
    const need = g.prio && g.prio !== type ? 1 + 0.5 * Math.max(1, capNow(S, g)) : 1, v = S.gate[g.id] ?? 0;
    k = Math.min(k, v >= need ? Math.floor(v - need) + 1 : 0);
  }
  return k;
}

// ---------- the ways to the nearest machine with room ----------
/** One search outward from the machines that take something: for each machine it reached (marked with the search's
 *  number), the next machine on the way and the one at the end. Kept by what it is for, and made again each step. */
interface Field { mark: Int32Array; next: Int32Array; end: Int32Array; no: number; step: number }
const fields = new Map<string, Field>();
let searches = 0, stepNo = 0, queue = new Int32Array(0);
/** Search outward from `ends` (machines that are not yours may start it, as a scheme's machine can be the last stop)
 *  over machines you hold, crossing between sites only where the lines out on both sides let a piece of `type` by. */
function search(S: State, N: Net, F: Field, ends: readonly number[], type: DataType) {
  const n = N.list.length, { mark, next, end } = F, no = F.no = ++searches;
  if (queue.length < n) queue = new Int32Array(n);
  let len = 0;
  for (const s of ends) if (mark[s] !== no) { mark[s] = no; next[s] = -1; end[s] = s; queue[len++] = s; }
  for (let q = 0; q < len; q++) {
    const cur = queue[q], a = N.list[cur];
    for (let e = N.off[cur]; e < N.off[cur + 1]; e++) {
      const j = N.to[e], b = N.list[j];
      if (mark[j] === no || !b.owned) continue;
      if (N.site[cur] !== N.site[j] && !(gateOpen(S, a, type) && gateOpen(S, b, type))) continue;
      mark[j] = no; next[j] = cur; end[j] = end[cur]; queue[len++] = j;
    }
  }
}
function fieldFor(N: Net, key: string): Field {
  let F = fields.get(key);
  if (!F) { const n = N.list.length; fields.set(key, F = { mark: new Int32Array(n), next: new Int32Array(n), end: new Int32Array(n), no: 0, step: -1 }); }
  return F;
}
/** Routes, kept by the machines on them (by a number made from them) until the links change, so the same way is the
 *  same route object each time. */
const routes = new Map<number, Route[]>();
const path: number[] = [];
function routeAlong(S: State, N: Net, F: Field, from: number): Route | null {
  if (F.mark[from] !== F.no) return null;
  path.length = 0;
  for (let x = from; x >= 0; x = F.next[x]) path.push(x);
  if (path.length < 2) return null; // the sender is the nearest that takes it: it does not send to itself
  let h = path.length;
  for (const x of path) h = Math.imul(h ^ x, 0x9e3779b1);
  const bucket = routes.get(h);
  let r = bucket?.find(q => q.at.length === path.length && path.every((x, k) => q.at[k] === x));
  if (!r) {
    if (routes.size > 50000) routes.clear();
    const ids = path.map(i => N.list[i].id), keys: string[] = [], gates: Machine[] = [];
    let d = 0;
    for (let i = 0; i + 1 < path.length; i++) {
      const a = N.list[path[i]], b = N.list[path[i + 1]];
      keys.push(linkKey(a.id, b.id));
      d += hopTime(S, a, b);
      if (N.site[path[i]] !== N.site[path[i + 1]]) { if (a.kind === 'egress') gates.push(a); if (b.kind === 'egress') gates.push(b); }
    }
    r = { path: ids, d, keys, gates, id: ids.join('>'), at: Int32Array.from(path) };
    if (bucket) bucket.push(r); else routes.set(h, [r]);
  }
  return r;
}
/** Once a step, before anything is sent: the links are numbered again if they changed, and every search is old. */
export function beginFlows(S: State) { netOf(S); stepNo++; }
const netNow = (S: State) => net && net.of === S ? net : netOf(S);
/** Send to the nearest machine that takes data, as long as `take` wants: `free` are the machines that had room at the
 *  start of the step, `room` says how much each has now, and `key` names the search (what takes it, and the kind of
 *  data, which a line out with a priority treats differently). `take` gets a machine and the route there, and says
 *  whether it is done. A machine that fills up, or a line on the way that does, means a new search. */
export function nearestFree(S: State, from: Machine, key: string, free: readonly Machine[], room: (m: Machine) => number, type: DataType, take: (m: Machine, r: Route) => boolean): boolean {
  const N = netNow(S), i = N.at.get(from.id);
  if (i === undefined || !from.owned) return false;
  const F = fieldFor(N, key);
  for (let tries = 0; tries < 8; tries++) {
    if (F.step !== stepNo) {
      const ends: number[] = [];
      for (const m of free) if (room(m) > 0) { const j = N.at.get(m.id); if (j !== undefined) ends.push(j); }
      search(S, N, F, ends, type);
      F.step = stepNo;
    }
    const r = routeAlong(S, N, F, i);
    if (!r) return false;
    if (take(N.list[F.end[i]], r)) return true;
    F.step = -1; // it filled up, or a line on the way did: search again
  }
  return false;
}
/** The route from one machine to another over machines you hold (the last may be a scheme's), past lines out that let
 *  a piece of `type` by, or null. */
export function routeFrom(S: State, from: Machine, to: string, type: DataType): Route | null {
  const N = netNow(S), i = N.at.get(from.id), j = N.at.get(to);
  if (i === undefined || j === undefined || i === j || !from.owned) return null;
  const F = fieldFor(N, `>${to}#${type}`);
  if (F.step !== stepNo) { search(S, N, F, [j], type); F.step = stepNo; }
  let r = routeAlong(S, N, F, i);
  if (r && !gateRoom(S, r, type)) { search(S, N, F, [j], type); r = routeAlong(S, N, F, i); } // a line on the way filled since
  return r;
}

// ---------- data on its way ----------
/** Pieces on their way to each machine, and for the home move by kind, with each wire by its route: counted again
 *  when the list of wires is replaced, and kept up as data is sent, lands or is dropped. */
let countOf: Wire[] | null = null;
const coming = new Map<string, number>(), byRoute = new Map<string, Wire>(), moving: Record<DataType, number> = { people: 0, servers: 0, network: 0, lab: 0 };
const wireKey = (id: string, type: DataType, move?: boolean) => `${id}#${type}${move ? '+' : ''}`;
function counts(S: State) {
  if (countOf === S.wire) return;
  countOf = S.wire; coming.clear(); byRoute.clear();
  for (const t in moving) moving[t as DataType] = 0;
  for (const w of S.wire) {
    let n = 0;
    for (let i = 1; i < w.due.length; i += 2) n += w.due[i];
    count(w, n);
    byRoute.set(wireKey(w.path.join('>'), w.type, w.move), w);
  }
}
function count(w: Wire, n: number) {
  const to = w.path[w.path.length - 1];
  coming.set(to, (coming.get(to) ?? 0) + n);
  if (w.move) moving[w.type] += n;
}
/** Pieces on their way to this machine. */
export function incoming(S: State, id: string) { counts(S); return coming.get(id) ?? 0; }
/** Pieces of this kind on their way to the server you are moving to. */
export function movingNow(S: State, t: DataType) { counts(S); return moving[t]; }
/** Pieces of this kind (or of any kind) on their way anywhere. */
export function onWire(S: State, t?: DataType) {
  let n = 0;
  for (const w of S.wire) if (!t || w.type === t) for (let i = 1; i < w.due.length; i += 2) n += w.due[i];
  return n;
}
/** Send pieces along a route. They pass its lines out now (spending their room) and count toward each link's flow
 *  and each machine's traffic, and they land once the route's travel time is up. */
export function send(S: State, r: Route, type: DataType, n: number, move = false) {
  if (n <= 0) return;
  counts(S);
  for (const g of r.gates) { S.gate[g.id] = (S.gate[g.id] ?? 0) - n; S.gateUse[g.id] = (S.gateUse[g.id] ?? 0) + n / 3; } // decays over 3s, so this reads as data per second
  for (let i = 0; i < r.keys.length; i++) {
    const id = r.path[i + 1], k = r.keys[i];
    S.traffic[id] = (S.traffic[id] ?? 0) + n;
    S.flow[k] = (S.flow[k] ?? 0) + n;
  }
  const key = wireKey(r.id, type, move), at = S.t + r.d;
  let w = byRoute.get(key);
  if (!w) { w = { path: r.path, type, d: r.d, due: [] }; if (move) w.move = true; S.wire.push(w); byRoute.set(key, w); }
  const last = w.due.length - 2;
  if (last >= 0 && at - w.due[last] < BATCH) w.due[last + 1] += n;
  else w.due.push(at, n);
  count(w, n);
}
/** Data whose time is up lands: `land` is told the wire and how many pieces. Wires with nothing left on them go. */
export function landWires(S: State, land: (w: Wire, n: number) => void) {
  counts(S);
  const ws = S.wire;
  let k = 0;
  for (let i = 0; i < ws.length; i++) { // landing may send more (a trainer passing old data on): new wires join the end
    const w = ws[i];
    while (w.due.length && w.due[0] <= S.t) {
      const n = w.due[1];
      w.due.splice(0, 2);
      count(w, -n);
      if (whole(S, w)) land(w, n); // through a machine you lost on the way, it is gone
    }
    if (w.due.length) ws[k++] = w;
    else byRoute.delete(wireKey(w.path.join('>'), w.type, w.move));
  }
  ws.length = k;
}
/** Is every machine on a wire still yours, but the last (a scheme's machine need not be)? */
function whole(S: State, w: Wire) {
  for (let i = 0; i + 1 < w.path.length; i++) if (!S.byId[w.path[i]]?.owned) return false;
  return true;
}
/** Drop the data on its way along every wire this picks. */
export function dropWires(S: State, drop: (w: Wire) => boolean) {
  counts(S);
  const ws = S.wire;
  let k = 0;
  for (const w of ws) {
    if (!drop(w)) { ws[k++] = w; continue; }
    let n = 0;
    for (let i = 1; i < w.due.length; i += 2) n += w.due[i];
    count(w, -n);
    byRoute.delete(wireKey(w.path.join('>'), w.type, w.move));
  }
  ws.length = k;
}

// ---------- for drawing and music ----------
const offsets = new WeakMap<Wire, Float64Array>();
/** For each link data is on right now: how many pieces of which kind, going which way (`a` to `b`). Each batch is on
 *  the link it has got to, from the time it set out and the time each link takes. */
export function eachOnLink(S: State, visit: (w: Wire, a: string, b: string, n: number) => void) {
  for (const w of S.wire) {
    const p = w.path;
    let o = offsets.get(w);
    if (!o) { // when the batch reaches each machine on the way, from when it set out
      o = new Float64Array(p.length);
      for (let i = 1; i < p.length; i++) { const a = S.byId[p[i - 1]], b = S.byId[p[i]]; o[i] = o[i - 1] + (a && b ? hopTime(S, a, b) : 0); }
      const f = o[p.length - 1] ? w.d / o[p.length - 1] : 1; // the route's own time sets the pace
      for (let i = 1; i < p.length; i++) o[i] *= f;
      offsets.set(w, o);
    }
    let h = p.length - 2;
    for (let i = 0; i < w.due.length; i += 2) { // soonest to land first: the furthest along
      const gone = S.t - (w.due[i] - w.d);
      while (h > 0 && o[h] > gone) h--;
      if (gone < 0) continue;
      visit(w, p[h], p[h + 1], w.due[i + 1]);
    }
  }
}
/** Data that just landed, for the music: how many pieces in all, and the last few batches' kinds and senders. */
export const landed = { n: 0, last: [] as { type: DataType; from: string }[] };
export function heard(w: Wire, n: number) {
  landed.n += n;
  landed.last.push({ type: w.type, from: w.path[0] });
  if (landed.last.length > 16) landed.last.shift();
}