1// Geohash: the halving, and what the port keeps of it.2//3// The numbers below are hand-derived from the halving rules rather than4// computed by the code under test, so a regression shows up as a number and5// not as a tautology. They are the same numbers the pre-rewrite suite carried,6// which is not an accident: the vectors gate compares this system's floats7// byte for byte, and these are the ones a reader can check by hand.89import assert from "node:assert/strict";10import test from "node:test";1112import {13 geohashAlphabet,14 geohashBaseDepth,15 geohashCellAt,16 geohashDepth,17 geohashExtent,18 geohashMaxDepth,19 geohashSystem,20} from "../cellsystems/geohash.ts";21import { bendOr, sphere, square, squareFromBounds, squareNoLens } from "./grounds.ts";2223const on = geohashSystem.on(square);2425test("the alphabet drops the four characters a reader would mishear", () => {26 assert.equal(geohashAlphabet.length, 32);27 for (const character of "ailo") {28 assert.ok(!geohashAlphabet.includes(character), `${character} is not in the alphabet`);29 }30});3132test("bbox halves the way geohash always has", () => {33 // The root is the world square — a plane's own [0, -size, size, 0], whose34 // top edge is a plain 0 rather than the surface ladder's -0.35 assert.deepEqual([...on.bbox("")], [0, -1024, 1024, 0]);36 // m = alphabet index 19 = 10011: x right, y bottom, x left, y up, x right.37 assert.deepEqual([...on.bbox("m")], [640, -768, 768, -512]);38 // 6 = 00110, continuing on the alternate axis.39 assert.deepEqual([...on.bbox("m6")], [672, -704, 704, -672]);40 assert.deepEqual([...on.bbox("m6s")], [688, -688, 692, -680]);41});4243test("cellAt is bbox run backward", () => {44 const centre = [688, -688] as const;45 assert.equal(on.descendTarget("", centre), "m");46 assert.equal(on.descendTarget("m", centre), "m6");47 assert.equal(geohashCellAt(square, centre, 3), "m6s");48 assert.equal(geohashCellAt(square, [-1, -1], 3), "", "off the surface names nothing");49 assert.equal(geohashCellAt(square, centre), "m6s", "the default depth is the floor");50});5152test("containment is inclusive on every edge", () => {53 assert.equal(on.contains("m6", [704, -672]), true, "the top-right corner is inside");54 assert.equal(on.contains("m6", [672, -704]), true, "the bottom-left corner is inside");55 assert.equal(on.contains("m6", [704.0001, -672]), false);56 assert.equal(on.contains("m6", [688, -672]), true, "the top edge is inside");57 // Cells sharing an edge all hold a point on it; nothing here breaks the tie,58 // because the caller asking is drawing, not partitioning. Four siblings meet59 // at m6's bottom-left corner and all four claim it.60 assert.deepEqual(61 on.children("m").filter((id) => on.contains(id, [672, -704])),62 ["m1", "m3", "m4", "m6"],63 );64 assert.deepEqual(65 on.children("m").filter((id) => on.contains(id, [688, -704])),66 ["m3", "m6"],67 "a point on a shared edge belongs to both cells",68 );69});7071test("a hash that never leaves the alphabet keeps its own address", () => {72 assert.equal(on.normalizeInput("M6X!"), "m6x");73 assert.equal(on.normalizeInput("aM6iLo"), "m6", "a, i, l and o are dropped, not mapped");74 assert.equal(on.normalizeInput("m6w9"), "m6w", "the field stops at the floor");75 assert.equal(on.parseInput(""), "", "the root is a place");76 assert.equal(on.parseInput("m6"), "m6");77});7879test("the label cuts the address into its context and its principal", () => {80 assert.deepEqual(on.label("m6s"), { context: "m6", principal: "s" });81 assert.deepEqual(on.label("m"), { context: "", principal: "m" });82 assert.deepEqual(on.label(""), { context: "", principal: "" });83});8485test("the accent follows the last character, so neighbours differ", () => {86 assert.equal(on.colorKey("0"), 0);87 assert.equal(on.colorKey("m"), 9, "index 19, wrapped on a ten-colour wheel");88 assert.equal(on.colorKey("mz"), 1, "index 31");89 assert.equal(on.childIndex("m6"), 6);90});9192test("the plan primitives stay where they were", () => {93 const children = on.children("m");94 assert.equal(children.length, 32);95 assert.equal(children[0], "m0");96 assert.equal(children[31], "mz");97 assert.equal(on.parent("m6"), "m");98 assert.equal(on.parent("m"), "");99 assert.equal(on.parent(""), "");100 assert.equal(on.level(""), 0);101 const ring = on.ring("m6");102 assert.equal(ring.length, 5);103 assert.deepEqual(ring[0], ring[4], "the ring closes");104 assert.deepEqual(on.locate([688, -688]), { label: "Geohash", value: "m6s" });105 assert.equal(on.locate([-1, -1]), null);106});107108test("the ground is an argument: the same hash names different ground on a different world", () => {109 const elsewhere = geohashSystem.on(sphere);110 assert.notDeepEqual([...elsewhere.bbox("m6")], [...on.bbox("m6")]);111 // Which is the whole point of de-globalizing: two grounds can be divided at112 // once, by two callers who never meet.113 assert.deepEqual([...on.bbox("m6")], [672, -704, 704, -672]);114});115116test("a plane's grid divides the world square and stays put across lenses", () => {117 // The maintainer's ruling: a game map's grid covers the FULL map area,118 // whatever window the open lens declares, so switching lenses moves no119 // hash. The lens-window ground and the whole-square ground answer the same120 // boxes, and the bounds-only lens does too.121 assert.deepEqual([...geohashExtent(square)], [0, -1024, 1024, 0]);122 assert.deepEqual([...geohashExtent(squareFromBounds)], [0, -1024, 1024, 0]);123 assert.deepEqual([...geohashExtent(squareNoLens)], [0, -1024, 1024, 0]);124 const windowed = geohashSystem.on(squareFromBounds);125 assert.deepEqual([...windowed.bbox("m6")], [...on.bbox("m6")]);126 assert.equal(windowed.descendTarget("m", [688, -688]), "m6");127 // A sphere keeps the surface ladder: its picture IS the ground.128 assert.deepEqual([...geohashExtent(sphere)], [0, -4096, 8192, -0]);129});130131// ---- the real mode: an earth-anchored plane -------------------------------132//133// bend-or declares a plane, an earth body and a Mercator window of134// -121.48204667177453 … -121.1529533282255 east-west (0.32909° of longitude)135// and 44.17572950664809 … 43.93922950850393 north-south (0.23650° of136// latitude), over the whole 8192 square. Its geohashes are the real ones.137138const real = geohashSystem.on(bendOr);139140test("bend-or's window comes out base depth 4, floor 6 — exactly", () => {141 // Cell spans halve from 360°/180° per the 5-bit alternation: depth 3 is142 // 1.40625° both ways (too coarse for either axis), depth 4 is 0.3515625°143 // of longitude (misses 0.32909°) by 0.17578125° of latitude (fits144 // 0.23650°). The OR fires at 4, and the three layers end at 6.145 assert.equal(geohashBaseDepth(bendOr), 4);146 assert.equal(geohashDepth(bendOr), 6);147 assert.equal(geohashSystem.inputLength(bendOr), 6);148 // Three layers of precision on every ground: maxLevel does not move.149 assert.equal(geohashSystem.maxLevel(bendOr), 3);150 // And the synthetic grounds keep their 3.151 assert.equal(geohashBaseDepth(square), 1);152 assert.equal(geohashDepth(square), geohashMaxDepth);153});154155test("bend-or's cell ids are genuine WGS84 geohashes", () => {156 // Derived independently with the textbook algorithm (python) before the157 // implementation existed: the raster centre (4096, 4096 y-down) is158 // lat 44.05759758…, lng -121.3175 — geohash 9rcdxk; (1024, 2048) is159 // 9rcdux; and (9000, 4096), EAST of the declared window, still has a real160 // address: 9rcfeu. The ground is real earth, so no point is refused.161 assert.equal(geohashCellAt(bendOr, [4096, -4096]), "9rcdxk");162 assert.equal(geohashCellAt(bendOr, [1024, -2048]), "9rcdux");163 assert.equal(geohashCellAt(bendOr, [9000, -4096]), "9rcfeu");164 assert.equal(geohashCellAt(bendOr, [4096, -4096], 4), "9rcd");165 assert.deepEqual(real.locate([4096, -4096]), { label: "Geohash", value: "9rcdxk" });166});167168test("the root plan is the six depth-4 cells the window intersects, reading order", () => {169 // Depth-4 cells are 0.3515625° × 0.17578125° from (-180, -90). The window170 // spans columns 166–167 and rows 761–763 of that grid — two columns, three171 // rows, north to south then west to east — and every one of the six172 // intersects with real area (the bottom row by 0.0061°, the top by173 // 0.0546°).174 assert.deepEqual(real.children(""), ["9rce", "9rcg", "9rcd", "9rcf", "9rc9", "9rcc"]);175 // The sibling ordinal is the position among the window's own cells.176 assert.equal(real.childIndex("9rcd"), 2);177 assert.equal(real.childIndex("9rce"), 0);178});179180test("real cells are drawn at their full extents, overhang and all", () => {181 // Hand-derived through the window's own formulas (x linear in longitude,182 // y linear in asinh(tan lat)), cross-checked in python to 1e-10:183 // 9rcd is [-121.640625, 43.9453125] … [-121.2890625, 44.12109375], which184 // lands west of the raster (x -3947.43…) — honest overhang, not clipped.185 assert.deepEqual([...real.bbox("9rcd")],186 [-3947.432211218598, -7981.703605508047, 4803.884266171338, -1895.4089537724801]);187 // 9rcdx, one layer down: [-121.3330078125, 44.033203125] …188 // [-121.2890625, 44.0771484375], fully inside the raster.189 assert.deepEqual([...real.bbox("9rcdx")],190 [3709.969706497596, -4940.812877376354, 4803.884266171338, -3418.6763501123382]);191 const ring = real.ring("9rcd");192 assert.equal(ring.length, 5);193 assert.deepEqual(ring[0], ring[4], "the ring closes");194});195196test("level counts layers on real ground, so the telescope is still three deep", () => {197 assert.equal(real.level(""), 0);198 assert.equal(real.level("9rcd"), 1);199 assert.equal(real.level("9rcdx"), 2);200 assert.equal(real.level("9rcdxk"), 3);201 assert.equal(real.parent("9rcdx"), "9rcd");202 assert.equal(real.parent("9rcd"), "", "a base cell telescopes out to the root");203 assert.equal(real.descendTarget("", [4096, -4096]), "9rcd",204 "descending from the root lands on a base cell, not a hemisphere");205 assert.equal(real.descendTarget("9rcd", [4096, -4096]), "9rcdx");206});207208test("a real address is whole at base depth, and a shorter one is a draft", () => {209 assert.equal(real.normalizeInput("9RCDXK!"), "9rcdxk");210 assert.equal(real.normalizeInput("9rcdxkpb"), "9rcdxk", "the field stops at the floor");211 assert.equal(real.parseInput(""), "", "the root is a place");212 assert.equal(real.parseInput("9rc"), null, "a hemisphere-to-city prefix is a draft");213 assert.equal(real.parseInput("9rcd"), "9rcd");214});215216test("real containment is the cell's own degree rectangle, boundaries inclusive", () => {217 assert.equal(real.contains("9rcd", [4096, -4096]), true);218 assert.equal(real.contains("9rcf", [4096, -4096]), false);219 assert.equal(real.contains("9rcf", [9000, -4096]), true,220 "a point outside the window is still on real ground");221 assert.equal(real.contains("", [9000, -4096]), true, "the root is the whole earth");222 const children = real.children("9rcd");223 assert.ok(children.length > 0 && children.length <= 32);224 for (const child of children) {225 assert.equal(real.parent(child), "9rcd");226 }227});228229test("geohash keeps halving past its own floor, and S2 does not", () => {230 // A frozen asymmetry, recorded rather than defended: `descendTarget` at231 // maxLevel answers a deeper cell in geohash and "" in S2. Nothing reaches232 // it — every caller stops at maxLevel first (cellPlan, equivalentCell) — but233 // a conformance suite that asserted one behaviour would be asserting a rule234 // the systems do not share. docs/analysis.md, "the floor asymmetry".235 assert.equal(geohashSystem.maxLevel(square), geohashMaxDepth);236 assert.equal(on.descendTarget("m6s", [688, -688]).length, 4,237 "geohash answers a level-4 cell when asked below its floor");238});