java-topology/defects/megaglest-0002/test/test_find_units_dedup.cpp

// Unit test for megaglest-0002: findUnitsForCell O(R²*U) linear dedup
// Defect: linear scan of units vector to check for duplicates in
//         findUnitsForCell, called once per cell in radius grid = O(R² * U)
// Fix: std::unordered_set<int> for O(1) duplicate check
//
// Simulates our findUnitsInRange hot path where cells in a radius grid
// may reference our same unit (multi-cell units), requiring dedup.

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

// Simulated cell unit reference
struct CellUnit {
    int id;
    bool alive;
};

// --- DEFECTIVE: O(cells * U) linear scan for dedup ---
std::vector<int> findUnitsInRangeDefective(const std::vector<CellUnit> &cells) {
    std::vector<int> units;
    for (size_t c = 0; c < cells.size(); ++c) {
        const CellUnit &cu = cells[c];
        if (!cu.alive) continue;

        // Linear scan for duplicate check
        bool found = false;
        for (size_t i = 0; i < units.size(); ++i) {
            if (units[i] == cu.id) {
                found = true;
                break;
            }
        }
        if (!found) {
            units.push_back(cu.id);
        }
    }
    return units;
}

// --- FIXED: O(cells) with hash set dedup ---
std::vector<int> findUnitsInRangeFixed(const std::vector<CellUnit> &cells) {
    std::vector<int> units;
    std::unordered_set<int> seenIds;
    for (size_t c = 0; c < cells.size(); ++c) {
        const CellUnit &cu = cells[c];
        if (!cu.alive) continue;

        // O(1) hash set dedup
        if (seenIds.insert(cu.id).second) {
            units.push_back(cu.id);
        }
    }
    return units;
}

void test_correctness() {
    printf("test_correctness... ");

    // Simulate cells where same unit appears multiple times (multi-cell units)
    std::vector<CellUnit> cells = {
        {1, true}, {2, true}, {1, true}, {3, true},
        {2, true}, {4, true}, {5, false}, {3, true},
        {6, true}, {1, true}
    };

    auto defResult = findUnitsInRangeDefective(cells);
    auto fixResult = findUnitsInRangeFixed(cells);

    std::sort(defResult.begin(), defResult.end());
    std::sort(fixResult.begin(), fixResult.end());

    assert(defResult == fixResult);
    std::vector<int> expected = {1, 2, 3, 4, 6};
    assert(defResult == expected);

    printf("PASS\n");
}

void test_all_same_unit() {
    printf("test_all_same_unit... ");

    // Worst case: all cells reference same unit (large multi-cell building)
    std::vector<CellUnit> cells;
    for (int i = 0; i < 100; ++i) {
        cells.push_back({42, true});
    }

    auto defResult = findUnitsInRangeDefective(cells);
    auto fixResult = findUnitsInRangeFixed(cells);

    assert(defResult.size() == 1);
    assert(fixResult.size() == 1);
    assert(defResult[0] == 42);
    assert(fixResult[0] == 42);

    printf("PASS\n");
}

void test_performance() {
    printf("test_performance... ");

    // Simulate radius=15, size=1: (2*15+1)^2 = 961 cells
    // With ~100 unique units, each occupying ~10 cells on average
    const int NUM_CELLS = 5000;
    const int NUM_UNIQUE_UNITS = 500;
    const int ITERS = 200;

    std::vector<CellUnit> cells;
    cells.reserve(NUM_CELLS);
    for (int c = 0; c < NUM_CELLS; ++c) {
        // Distribute units across cells with heavy overlap
        int unitId = (c * 7) % NUM_UNIQUE_UNITS + 1;
        cells.push_back({unitId, true});
    }

    // Defective
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERS; ++iter) {
        auto result = findUnitsInRangeDefective(cells);
        assert(!result.empty());
    }
    auto t1 = std::chrono::high_resolution_clock::now();

    // Fixed
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERS; ++iter) {
        auto result = findUnitsInRangeFixed(cells);
        assert(!result.empty());
    }
    auto t3 = std::chrono::high_resolution_clock::now();

    double defective_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double fixed_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();
    double ratio = defective_ms / fixed_ms;

    printf("defective=%.1fms fixed=%.1fms ratio=%.1fx ", defective_ms, fixed_ms, ratio);
    assert(ratio > 2.0);
    printf("PASS\n");
}

int main() {
    printf("=== megaglest-0002: findUnitsForCell dedup O(R²*U) -> O(R²) ===\n");
    test_correctness();
    test_all_same_unit();
    test_performance();
    printf("All tests passed.\n");
    return 0;
}