java-topology/defects/simutrans-0003/test/test_rebuild_connections.cpp

// Unit test for simutrans-0003: rebuild_connections() consecutive_halts append_unique O(S^2)
// Simulates building consecutive halt lists from schedule entries across goods categories.
// Defect: append_unique (linear scan) per schedule entry per category = O(S^2) per category.
// Fix: hash set for O(1) dedup = O(S) per category.

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

// --- Defect version: linear append_unique ---
static int defect_rebuild(int num_categories, int num_schedules, int entries_per_sched,
                          const uint16_t* halt_data) {
    // consecutive_halts[catg] collects unique halts
    std::vector<std::vector<uint16_t>> consecutive_halts(num_categories);
    int ops = 0;

    for (int s = 0; s < num_schedules; s++) {
        for (int e = 0; e < entries_per_sched; e++) {
            uint16_t halt_id = halt_data[s * entries_per_sched + e];
            for (int catg = 0; catg < num_categories; catg++) {
                // append_unique: linear scan
                bool found = false;
                for (uint16_t h : consecutive_halts[catg]) {
                    ops++;
                    if (h == halt_id) { found = true; break; }
                }
                if (!found) {
                    consecutive_halts[catg].push_back(halt_id);
                }
            }
        }
    }
    return ops;
}

// --- Fixed version: hash set dedup ---
static int fixed_rebuild(int num_categories, int num_schedules, int entries_per_sched,
                         const uint16_t* halt_data) {
    std::vector<std::unordered_set<uint16_t>> seen(num_categories);
    std::vector<std::vector<uint16_t>> consecutive_halts(num_categories);
    int ops = 0;

    for (int s = 0; s < num_schedules; s++) {
        for (int e = 0; e < entries_per_sched; e++) {
            uint16_t halt_id = halt_data[s * entries_per_sched + e];
            for (int catg = 0; catg < num_categories; catg++) {
                ops++;
                if (seen[catg].find(halt_id) == seen[catg].end()) {
                    seen[catg].insert(halt_id);
                    consecutive_halts[catg].push_back(halt_id);
                }
            }
        }
    }
    return ops;
}

int main() {
    // Simulate a busy transfer halt: 8 goods categories, 10 lines each with
    // 20 schedule entries, halt IDs from a pool of 50 unique halts.
    const int NUM_CATEGORIES = 8;
    const int NUM_SCHEDULES = 10;
    const int ENTRIES_PER_SCHED = 20;
    const int HALT_POOL = 50;

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

    int defect_ops = defect_rebuild(NUM_CATEGORIES, NUM_SCHEDULES, ENTRIES_PER_SCHED, halt_data.data());
    int fixed_ops = fixed_rebuild(NUM_CATEGORIES, NUM_SCHEDULES, ENTRIES_PER_SCHED, halt_data.data());

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

    printf("=== simutrans-0003: rebuild_connections consecutive_halts append_unique ===\n");
    printf("Categories: %d, schedules: %d, entries/schedule: %d, halt pool: %d\n",
           NUM_CATEGORIES, NUM_SCHEDULES, ENTRIES_PER_SCHED, 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: count unique halts per category should match
    // (Using separate runs with smaller data for verification)
    std::vector<std::vector<uint16_t>> defect_result(NUM_CATEGORIES);
    std::vector<std::unordered_set<uint16_t>> fixed_result(NUM_CATEGORIES);
    for (int s = 0; s < NUM_SCHEDULES; s++) {
        for (int e = 0; e < ENTRIES_PER_SCHED; e++) {
            uint16_t halt_id = halt_data[s * ENTRIES_PER_SCHED + e];
            for (int catg = 0; catg < NUM_CATEGORIES; catg++) {
                bool found = false;
                for (uint16_t h : defect_result[catg]) {
                    if (h == halt_id) { found = true; break; }
                }
                if (!found) defect_result[catg].push_back(halt_id);
                fixed_result[catg].insert(halt_id);
            }
        }
    }
    for (int catg = 0; catg < NUM_CATEGORIES; catg++) {
        assert(defect_result[catg].size() == fixed_result[catg].size());
    }
    printf("Unique halts per category: %zu (both versions agree)\n", fixed_result[0].size());

    assert(ratio > 5.0);
    printf("PASS\n");
    return 0;
}