Rebuilding a lost program from its test kit.

What happened to the code

1. Sept–Oct 2020

   Assignment written in C and tested against the course's kit: the CLUE data in five orders and 3k–15k subsets. A Stage 1 output for five queries was saved in my testing folder as result/test1.txt (20 Sept).

2. Nov 2020

   Code pushed to a private GitHub repository and synced to Google Drive. My experiment counts went into result1.csv and result2.csv for a plot.

3. Later

   The repository was deleted. The Drive copy kept the git index but lost the two objects holding the assignment and lecture zips. No backup surfaced.

4. Oct 2026

   Rebuilt in C99 from the evidence, ported to TypeScript, and checked against each other on every file of the test kit.

The evidence: one saved output

result/test1.txt, saved in my 2020 testing folder, holds 150 records (154 lines with the blank separators) for 5 queries, 57,807 bytes. Its first two lines:

144.9740079 -37.81499345 --> Census year: 2018 || Block ID: 18 || Property ID: 108975 || Base property ID: 108975 || CLUE small area: Melbourne (CBD) || Trading name: Besen Pty Ltd || Industry (ANZSIC4) code: 6419 || Industry (ANZSIC4) description: Other Auxiliary Finance and Investment Services || x coordinate: 144.97401 || y coordinate: -37.81499 || Location: (-37.81499345, 144.9740079) || 
144.9740079 -37.81499345 --> Census year: 2018 || Block ID: 18 || Property ID: 108975 || Base property ID: 108975 || CLUE small area: Melbourne (CBD) || Trading name: Department of Economic Development, Jobs, Transport and Resources || Industry (ANZSIC4) code: 7520 || Industry (ANZSIC4) description: State Government Administration || x coordinate: 144.97401 || y coordinate: -37.81499 || Location: (-37.81499345, 144.9740079) || 

The query is echoed as typed, every field is printed as Name: value || , and all seven businesses at that address follow in the order they appear in CLUEdata2018_original.csv. The rebuild's make test regenerates this file and compares it byte for byte.

Each design choice, and what it rests on

Key

x coordinate, y coordinate columns; x at even depths, y at odd

EvidenceThe median-first file builds a perfectly balanced tree (13 levels) only with x first.

Ties on the split axis

Strictly smaller goes left, equal or greater right

EvidenceStandard course convention; keeps the median file balanced.

Same location

One node, records in file order

Evidenceresult/test1.txt lists 7, 43, 1, 88, 11 businesses per answer in exactly the CSV's order.

Output

<query as typed> --> Field: value || … || , blank line between queries

EvidenceByte layout of result/test1.txt: LF endings, trailing space, quotes removed.

Distance

Euclidean in raw degrees, compared squared

EvidenceCoordinate units throughout; no projection in the spec-era code.

Comparisons

One per node whose key is compared with the query

EvidenceTextbook definition; the 2020 rule could not be recovered (below).

Stage 2

Inclusive radius search, NOTFOUND when empty

EvidenceInferred from result2.csv, which records a second, much wider search.

The heart of it, in C99

void kd_insert(kd_tree_t *tree, record_t *rec) {
    double key[2] = {rec->x, rec->y};
    tree->records++;

    if (tree->root == NULL) {
        tree->root = node_new(rec);
        tree->nodes++;
        return;
    }

    kd_node_t *node = tree->root;
    int depth = 0;
    for (;;) {
        if (key[0] == node->key[0] && key[1] == node->key[1]) {
            /* Same location: append, keeping file order. */
            rec->next = NULL;
            node->tail->next = rec;
            node->tail = rec;
            node->count++;
            return;
        }
        int axis = depth % 2;
        int side = key[axis] < node->key[axis] ? 0 : 1;
        if (node->child[side] == NULL) {
            node->child[side] = node_new(rec);
            tree->nodes++;
            return;
        }
        node = node->child[side];
        depth++;
    }
}

static void nearest_rec(const kd_node_t *node, int depth, nn_state_t *st) {
    if (node == NULL) {
        return;
    }
    st->comparisons++;
    double d2 = dist2(st->q, node->key);
    if (d2 < st->best_d2) {
        st->best_d2 = d2;
        st->best = node;
    }

    int axis = depth % 2;
    double diff = st->q[axis] - node->key[axis];
    int near = diff < 0 ? 0 : 1;

    nearest_rec(node->child[near], depth + 1, st);
    /* The far side can only hold a closer point if the splitting line is
     * closer than the best distance so far. */
    if (diff * diff < st->best_d2) {
        nearest_rec(node->child[1 - near], depth + 1, st);
    }
}

Full source, Makefile and tests in coursework/rebuild-2026 in the repository. The TypeScript port in web/src/lib/kdtree.ts follows it line by line.

Parity: C and TypeScript agree exactly

The C programs ran over all ten files of the test kit with four query sets (40 runs). The TypeScript port must print the same comparison count for every query and an output file with the same SHA-256. The tree shapes below are the C kdstats output; the browser rebuilds the same trees.

Swipe the table sideways for every column →

Compiler for this fixture: Apple clang version 21.0.0 (clang-2100.3.34.2).