1// The plan's invariants, written as properties.2//3// They run over invented grounds and invented locations — numbers no capture4// ever contained, so nothing here can be a transcript of an implementation5// agreeing with itself.6//7// Four properties, each over a plane and a sphere:8//9// Containment. A child cell's extent lies within its parent's, and the10// parent contains what the child holds.11// Hierarchy. parent() and children() are inverse both ways, and the12// ordinal is the position in the stable child order.13// Carry. The ⌘G crossing (equivalentCell): the place and the14// precision survive, the address does not.15// Plan order. cellPlan emits in the documented positional order, and16// nothing follows a leaf.1718import assert from "node:assert/strict";19import { describe, it } from "node:test";2021import type { CellID, CellSystem, GroundedCellSystem } from "../cellsystems/contract.ts";22import type { Coordinate, Extent, Ground } from "../cellsystems/ground.ts";23import { extentArea } from "../cellsystems/ground.ts";24import { cellPlan } from "../cellsystems/plan.ts";25import { equivalentCell } from "../cellsystems/registry.ts";26import { geohashSystem } from "../cellsystems/geohash.ts";27import { s2System } from "../cellsystems/s2.ts";28import { districtSystem } from "./districts.ts";29import { anchored } from "./grounds.ts";3031// --- the invented worlds -----------------------------------------------------32//33// Deliberately none of the recorded numbers: a 2048 world with an off-centre34// lens window, and a 4096x2048 sphere half the recorded one's size. If these35// tests pass because an implementation memorized a fixture, they will fail36// here, which is the point of inventing.3738/** A 2048 plane whose lens covers an off-centre window, districted for the third system. */39const field: Ground = {40 tileGridSize: 2048,41 lens: { surface: { x: 96, y: 160, width: 1536, height: 1280 }, bounds: null },42 world: { attrs: { "atlas.district.grid": "3x3" } },43};4445/** A 4096x2048 world square declared as a whole equirectangular sphere. */46const globe: Ground = {47 tileGridSize: 4096,48 lens: { surface: { x: 0, y: 0, width: 4096, height: 2048 }, bounds: null },49 world: {50 attrs: {51 "atlas.geometry.surface": "sphere",52 "atlas.geometry.projection": "equirect",53 "atlas.geometry.equirect.px": "0,0,4096,2048",54 "atlas.geometry.equirect.deg": "-180,90,180,-90",55 },56 },57};5859/** Invented locations: mid-ground, near a corner, near the seam, near a pole. */60const fieldProbes: readonly Coordinate[] = [61 [700.25, -500.75],62 [1601.5, -1400.125],63 [100.03125, -170.0625],64];6566const globeProbes: readonly Coordinate[] = [67 [1234.5, -567.875],68 [4090.25, -1023.5],69 [17.75, -1990.0625],70 [2048.5, -60.25],71];7273/**74 * Invented locations on the earth-anchored plane (analysis/test/grounds.ts,75 * `anchored`): inside its 4096 window, none of them a recorded number.76 */77const anchoredProbes: readonly Coordinate[] = [78 [1111.25, -900.5],79 [3300.5, -2800.125],80 [512.0625, -3900.75],81];8283/** The systems on trial, each with the ground it divides and the points that drive it. */84const subjects: readonly {85 name: string;86 system: CellSystem;87 ground: Ground;88 probes: readonly Coordinate[];89}[] = [90 { name: "geohash on the plane", system: geohashSystem, ground: field, probes: fieldProbes },91 { name: "districts on the plane", system: districtSystem, ground: field, probes: fieldProbes },92 { name: "geohash on the sphere", system: geohashSystem, ground: globe, probes: globeProbes },93 { name: "s2 on the sphere", system: s2System, ground: globe, probes: globeProbes },94 // Real mode: the same four families over an earth-anchored plane, where95 // geohash is genuine WGS84 and the plan is the window's.96 { name: "geohash on the anchored plane", system: geohashSystem, ground: anchored, probes: anchoredProbes },97 { name: "districts on the anchored plane", system: districtSystem, ground: anchored, probes: anchoredProbes },98];99100/** The descent chain under a probe, root first, down to the telescope's floor. */101function chainUnder(102 on: GroundedCellSystem,103 probe: Coordinate,104 floor: number,105): CellID[] {106 const chain: CellID[] = [""];107 for (let hop = 0; hop < floor; hop++) {108 const last = chain[chain.length - 1];109 if (last === undefined) break;110 const next = on.descendTarget(last, probe);111 if (!next) break;112 chain.push(next);113 }114 return chain;115}116117/**118 * Whether `inner` lies within `outer`, allowing the one thing the continuity119 * rule permits: an extent measured a whole world of x away, because a ring120 * that crossed the seam was unwrapped from its own first vertex. The slack is121 * for float arithmetic, not geometry.122 */123function nestsWithin(inner: Extent, outer: Extent, width: number, slack: number): boolean {124 for (const shift of [-width, 0, width]) {125 if (126 inner[0] + shift >= outer[0] - slack &&127 inner[2] + shift <= outer[2] + slack &&128 inner[1] >= outer[1] - slack &&129 inner[3] <= outer[3] + slack130 ) {131 return true;132 }133 }134 return false;135}136137for (const { name, system, ground, probes } of subjects) {138 const on = system.on(ground);139 const floor = system.maxLevel(ground);140 const width = ground.lens?.surface?.width ?? 0;141142 describe(`containment: ${name}`, () => {143 it("a child cell's extent lies within its parent's", () => {144 for (const probe of probes) {145 for (const parent of chainUnder(on, probe, floor - 1)) {146 const outer = on.bbox(parent);147 for (const child of on.children(parent)) {148 // Two places an extent stops being a containment fact, both of149 // them the picture's doing and not the hierarchy's. A parent150 // whose extent already spans the whole world of x — the root — is151 // cut at the picture's own edges, while a seam-crossing child152 // lawfully runs off them (the continuity rule: rings run off the153 // surface rather than wrapping), so only y can be measured there.154 // And around a pole the drawn extent is the bbox of a boundary155 // walk: a parent that circles the pole has a ring that never156 // reaches it, while the child cornered exactly on it does, so the157 // child's box runs past the parent's in y too. The spherical158 // predicate below is the truth at the poles; the box is not.159 const outerIsWholeWorld = outer[2] - outer[0] >= width - 1e-6;160 const polar = on.poleContained(child) !== null || on.poleContained(parent) !== null;161 const inner = on.bbox(child);162 if (polar) {163 // Judged by contains() below, in the system's own arithmetic.164 } else if (outerIsWholeWorld) {165 assert.ok(166 inner[1] >= outer[1] - 1e-6 && inner[3] <= outer[3] + 1e-6,167 `${child || "the root"} leaves ${parent || "the root"} in y`,168 );169 } else {170 assert.ok(171 nestsWithin(inner, outer, width, 1e-6),172 `${child}'s extent ${JSON.stringify(inner)} leaves its parent's ${JSON.stringify(outer)}`,173 );174 }175 // And the containment the extent pictures: the parent holds the176 // child's own interior, asked in the system's exact arithmetic.177 assert.ok(178 on.contains(parent, on.center(child)),179 `${parent || "the root"} does not contain the centre of its child ${child}`,180 );181 }182 }183 }184 });185 });186187 describe(`hierarchy: ${name}`, () => {188 it("parent and children are inverse both ways", () => {189 for (const probe of probes) {190 for (const id of chainUnder(on, probe, floor - 1)) {191 const kids = on.children(id);192 assert.deepEqual(on.children(id), kids, "the child order shuffled between calls");193 for (const child of kids) {194 assert.equal(on.parent(child), id, `${child} does not lead back to ${id || "the root"}`);195 assert.equal(on.level(child), on.level(id) + 1);196 }197 if (id !== "") {198 assert.ok(on.children(on.parent(id)).includes(id),199 `${on.parent(id) || "the root"} does not own up to ${id}`);200 }201 }202 }203 });204205 it("the sibling ordinal is the position in the stable order", () => {206 for (const probe of probes) {207 for (const id of chainUnder(on, probe, floor - 1)) {208 on.children(id).forEach((child, at) => {209 assert.equal(on.childIndex(child), at,210 `${child} is child ${at} of ${id || "the root"} but calls itself ${on.childIndex(child)}`);211 });212 }213 }214 });215 });216217 describe(`plan order: ${name}`, () => {218 // The order is reconstructed here from the documented rule and nothing219 // else: the ancestors' other children from the root down as neighbours,220 // then the held cell as a leaf and nothing after it, or as a scope221 // followed by every one of its children in the stable order.222 it("plans emit in the documented positional order", () => {223 for (const probe of probes) {224 for (const held of chainUnder(on, probe, floor)) {225 const expected: { hash: CellID; role: string; contextDistance: number }[] = [];226 const chain: CellID[] = [held];227 for (let id = held; id !== ""; ) {228 id = on.parent(id);229 chain.unshift(id);230 }231 for (let depth = 0; depth < chain.length - 1; depth++) {232 const here = chain[depth];233 const selected = chain[depth + 1];234 if (here === undefined || selected === undefined) continue;235 for (const id of on.children(here)) {236 if (id === selected) continue;237 expected.push({ hash: id, role: "neighbor", contextDistance: chain.length - 1 - depth });238 }239 }240 if (held && on.level(held) >= floor) {241 expected.push({ hash: held, role: "leaf", contextDistance: 0 });242 } else {243 if (held) expected.push({ hash: held, role: "scope", contextDistance: 0 });244 for (const id of on.children(held)) {245 expected.push({ hash: id, role: "child", contextDistance: 0 });246 }247 }248 assert.deepEqual(249 cellPlan(ground, system, held).map(250 (cell) => ({ hash: cell.hash, role: cell.role, contextDistance: cell.contextDistance }),251 ),252 expected,253 `the plan for "${held}" is not in emission order`,254 );255 }256 }257 });258259 it("nothing follows a leaf, and context distance descends across the run", () => {260 for (const probe of probes) {261 const chain = chainUnder(on, probe, floor);262 const deepest = chain[chain.length - 1];263 if (deepest === undefined || on.level(deepest) < floor) continue;264 const plan = cellPlan(ground, system, deepest);265 assert.equal(plan[plan.length - 1]?.role, "leaf");266 assert.equal(plan.filter((cell) => cell.role !== "neighbor").length, 1,267 "a leaf plan is neighbours and the leaf, nothing else");268 const distances = plan269 .filter((cell) => cell.role === "neighbor")270 .map((cell) => cell.contextDistance);271 for (let at = 1; at < distances.length; at++) {272 const previous = distances[at - 1];273 const current = distances[at];274 assert.ok(previous !== undefined && current !== undefined && current <= previous,275 "the root's neighbours come first and the held cell's siblings last");276 }277 }278 });279 });280}281282// --- the carry ---------------------------------------------------------------283//284// ⌘G cycles the grid system, and the held cell crosses with it. The two285// hierarchies share no boundaries, so the invariant is not about the address —286// it is that the *place* survives (the new cell holds the old cell's centre)287// and the *precision* survives (the new cell's area is the closest on a log288// scale among the cells of its own descent chain, because levels grow289// geometrically and "closest in kind" is what a reader means by "where I290// was"). The root is the one address both hierarchies spell alike, and it291// carries to itself.292293const crossings: readonly {294 name: string;295 ground: Ground;296 from: CellSystem;297 to: CellSystem;298 probes: readonly Coordinate[];299}[] = [300 { name: "geohash to districts on the plane", ground: field, from: geohashSystem, to: districtSystem, probes: fieldProbes },301 { name: "districts to geohash on the plane", ground: field, from: districtSystem, to: geohashSystem, probes: fieldProbes },302 { name: "geohash to s2 on the sphere", ground: globe, from: geohashSystem, to: s2System, probes: globeProbes },303 { name: "s2 to geohash on the sphere", ground: globe, from: s2System, to: geohashSystem, probes: globeProbes },304 { name: "real geohash to districts on the anchored plane", ground: anchored, from: geohashSystem, to: districtSystem, probes: anchoredProbes },305 { name: "districts to real geohash on the anchored plane", ground: anchored, from: districtSystem, to: geohashSystem, probes: anchoredProbes },306];307308for (const { name, ground, from, to, probes } of crossings) {309 const source = from.on(ground);310 const target = to.on(ground);311312 describe(`carry: ${name}`, () => {313 it("the root carries to the root", () => {314 assert.equal(equivalentCell(ground, from, to, ""), "");315 });316317 it("the place survives: the carried cell holds the old cell's centre", () => {318 for (const probe of probes) {319 for (const held of chainUnder(source, probe, from.maxLevel(ground))) {320 if (held === "") continue;321 const carried = equivalentCell(ground, from, to, held);322 if (carried === "") {323 // A carry to nowhere is lawful in exactly one case: the old324 // cell's centre is off the ground the target system divides —325 // the two systems no longer share one rectangle (geohash divides326 // the world square or real earth; districts divide the lens's327 // window), and a cell overhanging the shared ground can centre328 // outside it. The caller's answer is to hold no cell rather329 // than a wrong one, and this asserts the excuse is real.330 assert.equal(target.descendTarget("", source.center(held)), "",331 `"${held}" carried to nowhere though its centre is on the target's ground`);332 continue;333 }334 assert.ok(target.contains(carried, source.center(held)),335 `"${carried}" does not hold the centre of "${held}", which is the place that was carried`);336 }337 }338 });339340 it("the precision survives: no neighbouring depth fits closer on a log scale", () => {341 for (const probe of probes) {342 for (const held of chainUnder(source, probe, from.maxLevel(ground))) {343 if (held === "") continue;344 const carried = equivalentCell(ground, from, to, held);345 if (!carried) continue;346 const area = extentArea(source.bbox(held));347 const fit = (id: CellID): number =>348 Math.abs(Math.log(extentArea(target.bbox(id)) / area));349 // One level out: the parent is a worse fit, or there is no parent.350 const parent = target.parent(carried);351 if (parent !== "") {352 assert.ok(fit(carried) <= fit(parent) + 1e-9,353 `"${held}" carried to "${carried}" but its parent "${parent}" fits closer`);354 }355 // One level in: the child under the same centre is a worse fit — or356 // out of reach, because the carry stops at the telescope's floor357 // even where the arithmetic could keep halving (geohash's358 // descendTarget does; the floor asymmetry, docs/analysis.md).359 const deeper = target.level(carried) < to.maxLevel(ground)360 ? target.descendTarget(carried, source.center(held))361 : "";362 if (deeper) {363 assert.ok(fit(carried) <= fit(deeper) + 1e-9,364 `"${held}" carried to "${carried}" but its child "${deeper}" fits closer`);365 }366 }367 }368 });369 });370}