java-topology/defects/spring-rts-0001/test/test_intercept_handler.cpp

// Unit test for spring-rts-0001: CWeapon::HasIncomingProjectile O(I) vector scan
// in InterceptHandler::Update() nested loop = O(W * P * I)
// Fix: std::unordered_set<int> for O(1) lookup = O(W * P)

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <chrono>
#include <cassert>
#include <cstdio>

// Simulate our BEFORE (vector-based) weapon incoming projectile tracking
struct WeaponBefore {
    std::vector<int> incomingProjectileIDs;

    bool HasIncomingProjectile(int projID) const {
        return (std::find(incomingProjectileIDs.begin(), incomingProjectileIDs.end(), projID) != incomingProjectileIDs.end());
    }
    void AddIncomingProjectile(int projID) {
        incomingProjectileIDs.push_back(projID);
    }
    void RemoveIncomingProjectile(int projID) {
        auto it = std::find(incomingProjectileIDs.begin(), incomingProjectileIDs.end(), projID);
        if (it != incomingProjectileIDs.end()) {
            *it = incomingProjectileIDs.back();
            incomingProjectileIDs.pop_back();
        }
    }
};

// Simulate our AFTER (unordered_set-based) weapon incoming projectile tracking
struct WeaponAfter {
    std::unordered_set<int> incomingProjectileIDs;

    bool HasIncomingProjectile(int projID) const {
        return (incomingProjectileIDs.find(projID) != incomingProjectileIDs.end());
    }
    void AddIncomingProjectile(int projID) {
        incomingProjectileIDs.insert(projID);
    }
    void RemoveIncomingProjectile(int projID) {
        incomingProjectileIDs.erase(projID);
    }
};

// Simulate InterceptHandler::Update() inner logic:
// for each interceptor weapon, for each interceptable projectile,
// call HasIncomingProjectile(projID) to check if already tracked
template<typename Weapon>
long long simulateInterceptUpdate(
    std::vector<Weapon>& interceptors,
    const std::vector<int>& interceptableIDs,
    int iterations
) {
    auto t0 = std::chrono::high_resolution_clock::now();
    int dummy = 0;

    for (int iter = 0; iter < iterations; iter++) {
        for (auto& w : interceptors) {
            for (int projID : interceptableIDs) {
                if (!w.HasIncomingProjectile(projID)) {
                    // Would normally add, but we skip to measure lookup cost
                    dummy++;
                }
            }
        }
    }

    auto t1 = std::chrono::high_resolution_clock::now();
    // Prevent optimization
    if (dummy < 0) printf("never\n");
    return std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
}

int main() {
    // Scenario: 10 interceptor weapons, 200 interceptable projectiles,
    // each weapon tracks 100 incoming projectiles (realistic for large battles)
    const int W = 10;   // interceptor weapons
    const int P = 200;  // interceptable projectiles in flight
    const int I = 100;  // incoming projectiles tracked per weapon
    const int ITERS = 20;

    // --- correctness test ---
    {
        WeaponBefore wb;
        WeaponAfter wa;

        for (int i = 0; i < 50; i++) {
            wb.AddIncomingProjectile(i * 3);
            wa.AddIncomingProjectile(i * 3);
        }

        // Check membership
        for (int i = 0; i < 50; i++) {
            assert(wb.HasIncomingProjectile(i * 3) == true);
            assert(wa.HasIncomingProjectile(i * 3) == true);
            assert(wb.HasIncomingProjectile(i * 3 + 1) == false);
            assert(wa.HasIncomingProjectile(i * 3 + 1) == false);
        }

        // Check removal
        wb.RemoveIncomingProjectile(15);
        wa.RemoveIncomingProjectile(15);
        assert(wb.HasIncomingProjectile(15) == false);
        assert(wa.HasIncomingProjectile(15) == false);

        // Verify same membership after removal
        for (int i = 0; i < 50; i++) {
            if (i * 3 == 15) continue;
            assert(wb.HasIncomingProjectile(i * 3) == true);
            assert(wa.HasIncomingProjectile(i * 3) == true);
        }

        printf("PASS correctness\n");
    }

    // --- performance test ---
    {
        std::vector<WeaponBefore> interceptorsBefore(W);
        std::vector<WeaponAfter> interceptorsAfter(W);

        // Pre-populate each weapon with I tracked projectiles (IDs 0..I-1)
        for (int w = 0; w < W; w++) {
            for (int i = 0; i < I; i++) {
                interceptorsBefore[w].AddIncomingProjectile(i);
                interceptorsAfter[w].AddIncomingProjectile(i);
            }
        }

        // Interceptable projectiles: IDs from I to I+P-1 (none already tracked)
        std::vector<int> interceptableIDs(P);
        for (int p = 0; p < P; p++) {
            interceptableIDs[p] = I + p;
        }

        // Warmup
        simulateInterceptUpdate(interceptorsBefore, interceptableIDs, 2);
        simulateInterceptUpdate(interceptorsAfter, interceptableIDs, 2);

        long long usBefore = simulateInterceptUpdate(interceptorsBefore, interceptableIDs, ITERS);
        long long usAfter  = simulateInterceptUpdate(interceptorsAfter,  interceptableIDs, ITERS);

        double ratio = (double)usBefore / (double)usAfter;

        printf("BEFORE (vector std::find):    %lld us\n", usBefore);
        printf("AFTER  (unordered_set::find): %lld us\n", usAfter);
        printf("Ratio: %.1fx\n", ratio);

        // Expect significant speedup (typically 10x+ at these sizes)
        assert(ratio > 2.0 && "Expected at least 2x speedup from vector->unordered_set");
        printf("PASS performance (%.1fx speedup)\n", ratio);
    }

    printf("ALL TESTS PASSED\n");
    return 0;
}