How your ride app finds a driver: the code

These are the files that do most of the work. The comments explain why each part works the way it does. If anything is unclear, or you would do it differently, tell me. I will also send you the full code for free, with nothing to sign up for. Ask for the full code

import { dist } from "../../geo.ts";
import { PARAMS } from "../../params.ts";
import { Best } from "./best.ts";
import { createCellMap, usableRadius } from "./cellmap.ts";
import type { SearchResult, SpatialIndex } from "./types.ts";

const S = PARAMS.index.gridCellMetres;
// Numeric keys keep the search free of string building; strings are made only when recording.
const STRIDE = 4194304;
const numKey = (i: number, j: number): number => i * STRIDE + j;

export function createGridIndex(): SpatialIndex {
  const map = createCellMap<number>((x, y) => numKey(Math.floor(x / S), Math.floor(y / S)));
  return {
    kind: "grid",
    upsert: map.upsert,
    remove: map.remove,
    size: map.size,
    nearest(x, y, _lat, _lng, k, maxRadius, opts): SearchResult {
      if (!(k > 0)) return { cars: [], cellsSearched: [], rings: 0 };
      const radius = usableRadius(maxRadius);
      const record = opts?.record !== false;
      const best = new Best(k);
      const searched: string[] = [];
      const ci = Math.floor(x / S);
      const cj = Math.floor(y / S);
      const visit = (i: number, j: number): void => {
        if (record) searched.push(`${i},${j}`);
        const set = map.bucket(numKey(i, j));
        if (!set) return;
        for (const e of set) {
          const d = dist(x, y, e.x, e.y);
          if (d <= radius) best.offer(e.id, d);
        }
      };
      let r = 0;
      for (;; r++) {
        if (r === 0) visit(ci, cj);
        else {
          for (let i = ci - r; i <= ci + r; i++) { visit(i, cj - r); visit(i, cj + r); }
          for (let j = cj - r + 1; j <= cj + r - 1; j++) { visit(ci - r, j); visit(ci + r, j); }
        }
        // anything outside rings 0..r is at least r cells away from the query point
        const bound = r * S;
        if (bound > radius || (best.full && best.worst < bound)) break;
      }
      return { cars: best.ids, cellsSearched: searched, rings: r };
    },
  };
}

// Give every row and column a price (u, v) so each pair costs at least the sum of its prices.
// Add rows one at a time and grow an augmenting path along pairs where that bound is tight.
// Missing and forbidden pairs cost BIG, more than any real total, so real pairs win first.
export function hungarian(cost: number[][]): number[] {
  const rows = cost.length;
  const cols = rows ? cost[0].length : 0;
  const result = new Array<number>(rows).fill(-1);
  // a row with no finite option can never be matched, so it stays out of the solve
  const live: number[] = [];
  for (let r = 0; r < rows; r++) if (cost[r].some((x) => Number.isFinite(x))) live.push(r);
  if (!live.length || !cols) return result;

  // each added row scans every column, so the smaller side goes in rows: the work is small^2 x large, never large^3
  const flip = live.length > cols;
  const n = flip ? cols : live.length;
  const m = flip ? live.length : cols;
  const real = new Float64Array(n * m);
  let maxFinite = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      const x = flip ? cost[live[j]][i] : cost[live[i]][j];
      real[i * m + j] = x;
      if (Number.isFinite(x)) maxFinite = Math.max(maxFinite, Math.abs(x));
    }
  }
  // costs are road seconds, never negative, so n real pairs total at most n * maxFinite, which is under BIG
  const BIG = (maxFinite + 1) * (n + 1);
  const a = real.map((x) => (Number.isFinite(x) ? x : BIG));

  const u = new Float64Array(n + 1); // row prices
  const v = new Float64Array(m + 1); // column prices
  const p = new Int32Array(m + 1); // p[j] = row holding column j (1-based, 0 = none)
  const way = new Int32Array(m + 1); // previous column on the path to j
  const minv = new Float64Array(m + 1);
  const used = new Uint8Array(m + 1);

  for (let i = 1; i <= n; i++) {
    // column 0 is a placeholder that holds the new row; the path search starts there and stops at a free column
    p[0] = i;
    let j0 = 0;
    minv.fill(Infinity);
    used.fill(0);
    do {
      used[j0] = 1;
      const i0 = p[j0];
      const base = (i0 - 1) * m - 1;
      let delta = Infinity;
      let j1 = 0;
      for (let j = 1; j <= m; j++) {
        if (used[j]) continue;
        const cur = a[base + j] - u[i0] - v[j];
        if (cur < minv[j]) {
          minv[j] = cur;
          way[j] = j0;
        }
        if (minv[j] < delta) {
          delta = minv[j];
          j1 = j;
        }
      }
      for (let j = 0; j <= m; j++) {
        if (used[j]) {
          u[p[j]] += delta;
          v[j] -= delta;
        } else minv[j] -= delta;
      }
      j0 = j1;
    } while (p[j0] !== 0);
    do {
      const j1 = way[j0];
      p[j0] = p[j1];
      j0 = j1;
    } while (j0 !== 0);
  }

  for (let j = 1; j <= m; j++) {
    const i = p[j] - 1;
    if (i < 0 || !Number.isFinite(real[i * m + j - 1])) continue;
    if (flip) result[live[j - 1]] = i;
    else result[live[i]] = j - 1;
  }
  return result;
}

Ask for the full codeBack to the case study