Design Uber (Ride Matching)

// Geohash: split the world in half again and again, alternating longitude and latitude,
// and write the bits 5 at a time in base 32. Each extra character makes the cell 32× smaller,
// and points that share a prefix are in the same cell.
const BASE32 = '0123456789bcdefghjkmnpqrstuvwxyz';   // no a, i, l, o
const EARTH_RADIUS_M = 6_371_000;

export function encode(lat, lon, precision = 6) {
  let latLo = -90, latHi = 90, lonLo = -180, lonHi = 180;
  let hash = '', ch = 0, bits = 0, lonBit = true;          // the first bit is longitude
  while (hash.length < precision) {
    if (lonBit) {
      const mid = (lonLo + lonHi) / 2;
      if (lon >= mid) { ch = ch * 2 + 1; lonLo = mid; } else { ch *= 2; lonHi = mid; }
    } else {
      const mid = (latLo + latHi) / 2;
      if (lat >= mid) { ch = ch * 2 + 1; latLo = mid; } else { ch *= 2; latHi = mid; }
    }
    lonBit = !lonBit;
    if (++bits === 5) { hash += BASE32[ch]; ch = 0; bits = 0; }
  }
  return hash;
}

// The cell's bounding box: replay the same halvings.
export function bounds(hash) {
  let latLo = -90, latHi = 90, lonLo = -180, lonHi = 180, lonBit = true;
  for (const c of hash) {
    const v = BASE32.indexOf(c);
    if (v < 0) throw new Error(`Not a geohash character: ${c}`);
    for (let b = 4; b >= 0; b--) {
      const bit = (v >> b) & 1;
      if (lonBit) { const mid = (lonLo + lonHi) / 2; if (bit) lonLo = mid; else lonHi = mid; }
      else { const mid = (latLo + latHi) / 2; if (bit) latLo = mid; else latHi = mid; }
      lonBit = !lonBit;
    }
  }
  return { latLo, latHi, lonLo, lonHi };
}

// The cell dRow rows north and dCol columns east of this one, at the same precision.
// Cells of one precision form a regular grid, so stepping from the centre lands in the middle of the target.
export function offset(hash, dRow, dCol) {
  const b = bounds(hash);
  const lat = (b.latLo + b.latHi) / 2 + dRow * (b.latHi - b.latLo);
  if (lat > 90 || lat < -90) return null;                    // past a pole
  const lon = (b.lonLo + b.lonHi) / 2 + dCol * (b.lonHi - b.lonLo);
  return encode(lat, ((lon + 540) % 360) - 180, hash.length); // wrap across the antimeridian
}

// The 8 cells around this one. A query must look at them too: a driver 10 m away can sit across an edge.
export function neighbours(hash) {
  return {
    n: offset(hash, 1, 0), ne: offset(hash, 1, 1), e: offset(hash, 0, 1), se: offset(hash, -1, 1),
    s: offset(hash, -1, 0), sw: offset(hash, -1, -1), w: offset(hash, 0, -1), nw: offset(hash, 1, -1),
  };
}

// Great-circle distance in metres.
export function haversineM(a, b) {
  const rad = d => (d * Math.PI) / 180;
  const dLat = rad(b.lat - a.lat), dLon = rad(b.lon - a.lon);
  const h = Math.sin(dLat / 2) ** 2 + Math.cos(rad(a.lat)) * Math.cos(rad(b.lat)) * Math.sin(dLon / 2) ** 2;
  return 2 * EARTH_RADIUS_M * Math.asin(Math.sqrt(h));
}

// Cell height and width in metres. Width shrinks with cos(latitude): cells get narrow near the poles.
export function cellSizeM(hash) {
  const b = bounds(hash);
  const lat = (b.latLo + b.latHi) / 2, lon = (b.lonLo + b.lonHi) / 2;
  return {
    heightM: haversineM({ lat: b.latLo, lon }, { lat: b.latHi, lon }),
    widthM: haversineM({ lat, lon: b.lonLo }, { lat, lon: b.lonHi }),
  };
}

// Rider's map: follow the matched driver. Fixes arrive every ~4 s; drawing them as they come makes the
// car jump. Instead, glide from where the marker is drawn now to each new fix over one update interval.
import { useEffect, useRef, useState } from 'react';
import { haversineM } from './geohash.js';

// Pure: plan the next glide when a fix arrives. `prev` is the current glide (or null before the first fix).
export function planGlide(prev, fix, now, { gapMs = 4_000, snapM = 500 } = {}) {
  if (prev && !(fix.ts > prev.to.ts)) return prev;            // duplicate or out of order: ignore
  const to = { lat: fix.lat, lon: fix.lon, heading: fix.heading ?? prev?.to.heading ?? 0, ts: fix.ts };
  if (!prev) return { from: to, to, start: now, duration: 0 };  // first fix: just place the car
  const from = markerAt(prev, now);                           // start from what the rider sees: no jump
  if (haversineM(from, to) > snapM) return { from: to, to, start: now, duration: 0 };   // after a long gap, teleport rather than slide through buildings
  return { from, to, start: now, duration: gapMs };
}

// Pure: where to draw the marker at time `now`.
export function markerAt(glide, now) {
  const t = glide.duration > 0 ? Math.min(1, Math.max(0, (now - glide.start) / glide.duration)) : 1;
  return {
    lat: glide.from.lat + (glide.to.lat - glide.from.lat) * t,
    lon: glide.from.lon + (glide.to.lon - glide.from.lon) * t,
    heading: lerpHeading(glide.from.heading, glide.to.heading, t),
  };
}

// Turn the short way round: from 350° to 10° is +20°, not −340°.
export function lerpHeading(a, b, t) {
  const d = ((((b - a) % 360) + 540) % 360) - 180;
  return (((a + d * t) % 360) + 360) % 360;
}

export function useDriverMarker(rideId, wsUrl) {
  const [marker, setMarker] = useState(null);                  // { lat, lon, heading }, or null before the first fix
  const glide = useRef(null);

  useEffect(() => {
    let ws, raf = 0, retry, attempt = 0, closed = false;
    const frame = now => {
      const g = glide.current;
      // Re-render only while a glide is running. With a map SDK, call marker.setPosition() here instead.
      if (g && now <= g.start + g.duration + 100) setMarker(markerAt(g, now));
      raf = requestAnimationFrame(frame);
    };
    const connect = () => {
      ws = new WebSocket(`${wsUrl}?ride=${encodeURIComponent(rideId)}`);
      ws.onopen = () => { attempt = 0; };                      // the server sends the latest fix first
      ws.onmessage = e => {
        const msg = JSON.parse(e.data);
        if (msg.type === 'driver_location') glide.current = planGlide(glide.current, msg, performance.now());
      };
      ws.onclose = () => {
        if (!closed) retry = setTimeout(connect, Math.random() * Math.min(30_000, 1_000 * 2 ** attempt++));   // full jitter
      };
    };
    connect();
    raf = requestAnimationFrame(frame);
    return () => {
      closed = true;
      clearTimeout(retry);
      cancelAnimationFrame(raf);
      ws?.close();
    };
  }, [rideId, wsUrl]);

  return marker;
}