java-topology/defects/simutrans-0001/test/test_rebuild_linked_connections.cpp

// Unit test for simutrans-0001: rebuild_linked_connections() append_unique O(C*H^2)
// Simulates collecting unique halt IDs from connections across multiple goods categories.
// Defect: vector append_unique (linear scan) inside double loop = O(C * H^2).
// Fix: hash set for O(1) membership test = O(C * H).

#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <unordered_set>
#include <chrono>
#include <cassert>

// --- Defect version: linear scan append_unique ---
struct DefectCollector {
    std::vector<uint16_t> all;

    void append_unique(uint16_t halt_id) {
        for (uint16_t h : all) {
            if (h == halt_id) return;
        }
        all.push_back(halt_id);
    }
};

static int defect_rebuild_linked(int num_categories, int conns_per_catg, const uint16_t* conn_data) {
    DefectCollector collector;
    int ops = 0;
    for (int c = 0; c < num_categories; c++) {
        for (int j = 0; j < conns_per_catg; j++) {
            uint16_t halt_id = conn_data[c * conns_per_catg + j];
            // append_unique does linear scan
            for (uint16_t h : collector.all) {
                ops++;
                if (h == halt_id) goto next;
            }
            collector.all.push_back(halt_id);
            next:;
        }
    }
    return ops;
}

// --- Fixed version: hash set for O(1) lookup ---
static int fixed_rebuild_linked(int num_categories, int conns_per_catg, const uint16_t* conn_data) {
    std::unordered_set<uint16_t> seen;
    std::vector<uint16_t> all;
    int ops = 0;
    for (int c = 0; c < num_categories; c++) {
        for (int j = 0; j < conns_per_catg; j++) {
            uint16_t halt_id = conn_data[c * conns_per_catg + j];
            ops++;
            if (seen.find(halt_id) == seen.end()) {
                seen.insert(halt_id);
                all.push_back(halt_id);
            }
        }
    }
    return ops;
}

int main() {
    // Simulate a busy transfer halt: 10 goods categories, 200 connections per category,
    // drawn from a pool of 200 unique halts (so many duplicates across categories).
    const int NUM_CATEGORIES = 10;
    const int CONNS_PER_CATG = 200;
    const int HALT_POOL = 200;

    std::vector<uint16_t> conn_data(NUM_CATEGORIES * CONNS_PER_CATG);
    srand(42);
    for (int i = 0; i < NUM_CATEGORIES * CONNS_PER_CATG; i++) {
        conn_data[i] = (uint16_t)(rand() % HALT_POOL);
    }

    int defect_ops = defect_rebuild_linked(NUM_CATEGORIES, CONNS_PER_CATG, conn_data.data());
    int fixed_ops = fixed_rebuild_linked(NUM_CATEGORIES, CONNS_PER_CATG, conn_data.data());

    double ratio = (double)defect_ops / (double)fixed_ops;

    printf("=== simutrans-0001: rebuild_linked_connections append_unique ===\n");
    printf("Categories: %d, connections/category: %d, halt pool: %d\n",
           NUM_CATEGORIES, CONNS_PER_CATG, HALT_POOL);
    printf("Defect ops (linear scan):   %d\n", defect_ops);
    printf("Fixed ops (hash set):       %d\n", fixed_ops);
    printf("Ratio: %.1fx\n", ratio);

    // Verify correctness: both should produce same unique set
    DefectCollector dc;
    for (int c = 0; c < NUM_CATEGORIES; c++) {
        for (int j = 0; j < CONNS_PER_CATG; j++) {
            dc.append_unique(conn_data[c * CONNS_PER_CATG + j]);
        }
    }
    std::unordered_set<uint16_t> fs;
    for (int c = 0; c < NUM_CATEGORIES; c++) {
        for (int j = 0; j < CONNS_PER_CATG; j++) {
            fs.insert(conn_data[c * CONNS_PER_CATG + j]);
        }
    }
    assert(dc.all.size() == fs.size());
    printf("Unique halts collected: %zu (both versions agree)\n", dc.all.size());

    // Speedup must be significant
    assert(ratio > 5.0);
    printf("PASS\n");
    return 0;
}