java-topology/defects/pioneer-0002/test/test_faction_isclaimed.cpp

// Unit test for pioneer-0002: Faction::IsClaimed linear scan of m_ownedsystemlist
// Defect: O(C) linear scan of claimed systems vector per system per faction
// Fix: std::set<SystemPath> for O(log C) lookup
//
// Called from GetNearestClaimant which runs per-system during sector generation.
// With F factions and C claims each, and S systems to assign, total cost is O(S*F*C).

#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <cassert>

struct SystemPath {
    int sectorX, sectorY, sectorZ;
    int systemIndex;
    int bodyIndex;

    SystemPath() : sectorX(0), sectorY(0), sectorZ(0), systemIndex(-1), bodyIndex(-1) {}
    SystemPath(int x, int y, int z) : sectorX(x), sectorY(y), sectorZ(z), systemIndex(-1), bodyIndex(-1) {}
    SystemPath(int x, int y, int z, int si) : sectorX(x), sectorY(y), sectorZ(z), systemIndex(si), bodyIndex(-1) {}

    bool operator==(const SystemPath &b) const {
        return sectorX == b.sectorX && sectorY == b.sectorY && sectorZ == b.sectorZ
            && systemIndex == b.systemIndex && bodyIndex == b.bodyIndex;
    }
    bool operator<(const SystemPath &b) const {
        if (sectorX != b.sectorX) return sectorX < b.sectorX;
        if (sectorY != b.sectorY) return sectorY < b.sectorY;
        if (sectorZ != b.sectorZ) return sectorZ < b.sectorZ;
        if (systemIndex != b.systemIndex) return systemIndex < b.systemIndex;
        return bodyIndex < b.bodyIndex;
    }
};

// BEFORE: linear scan
static long long benchmark_linear(int numClaims, int numQueries) {
    std::vector<SystemPath> claims;
    for (int i = 0; i < numClaims; i++) {
        claims.push_back(SystemPath(i % 100, (i / 100) % 100, i / 10000, -99));
    }

    // Queries: mix of hits and misses
    std::vector<SystemPath> queries;
    for (int i = 0; i < numQueries; i++) {
        queries.push_back(SystemPath(i % 200, (i / 200) % 200, i / 40000));
    }

    long long ops = 0;
    auto start = std::chrono::high_resolution_clock::now();

    for (const auto &query : queries) {
        SystemPath sector = query;
        sector.systemIndex = -99;
        bool found = false;
        for (const auto &clam : claims) {
            ops++;
            if (clam == sector || clam == query) {
                found = true;
                break;
            }
        }
        (void)found;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto us = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    printf("  LINEAR: C=%d Q=%d ops=%lld time=%lldus\n", numClaims, numQueries, ops, us);
    return ops;
}

// AFTER: set lookup
static long long benchmark_set(int numClaims, int numQueries) {
    std::set<SystemPath> claimSet;
    for (int i = 0; i < numClaims; i++) {
        claimSet.insert(SystemPath(i % 100, (i / 100) % 100, i / 10000, -99));
    }

    std::vector<SystemPath> queries;
    for (int i = 0; i < numQueries; i++) {
        queries.push_back(SystemPath(i % 200, (i / 200) % 200, i / 40000));
    }

    long long ops = 0;
    auto start = std::chrono::high_resolution_clock::now();

    for (const auto &query : queries) {
        SystemPath sector = query;
        sector.systemIndex = -99;
        ops += 2; // two set lookups
        bool found = claimSet.count(sector) > 0 || claimSet.count(query) > 0;
        (void)found;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto us = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    printf("  SET:    C=%d Q=%d ops=%lld time=%lldus\n", numClaims, numQueries, ops, us);
    return ops;
}

int main() {
    printf("pioneer-0002: Faction::IsClaimed linear scan O(C) -> O(log C)\n");
    printf("=================================================================\n\n");

    int test_sizes[][2] = {
        {50, 200},
        {100, 500},
        {200, 1000},
        {500, 2000},
    };

    bool all_pass = true;
    for (auto &sz : test_sizes) {
        int C = sz[0], Q = sz[1];
        printf("Test C=%d claims, Q=%d queries:\n", C, Q);
        long long ops_before = benchmark_linear(C, Q);
        long long ops_after = benchmark_set(C, Q);
        double ratio = (double)ops_before / (double)ops_after;
        printf("  Ratio: %.1fx fewer operations\n\n", ratio);
        if (ratio < 2.0) {
            printf("  FAIL: expected at least 2x improvement\n");
            all_pass = false;
        }
    }

    printf("=================================================================\n");
    if (all_pass) {
        printf("PASS: all tests passed\n");
        return 0;
    } else {
        printf("FAIL: some tests failed\n");
        return 1;
    }
}