java-topology/defects/0ad-0002/test/0ad-0002-test.cpp

// Unit test for 0ad-0002: CCmpRangeManager m_ModifiedEntities dedup
// Verifies that unordered_set-based dedup matches vector-based behavior
// and demonstrates O(E*M) -> O(E) improvement.

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

using entity_id_t = uint32_t;

// --- BEFORE: vector + std::find ---
struct VisibilityTrackerBefore {
    std::vector<entity_id_t> m_ModifiedEntities;

    void RequestVisibilityUpdate(entity_id_t ent) {
        if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), ent) == m_ModifiedEntities.end())
            m_ModifiedEntities.push_back(ent);
    }

    bool IsModified(entity_id_t ent) const {
        return std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), ent) != m_ModifiedEntities.end();
    }

    void DrainModified() {
        while (!m_ModifiedEntities.empty()) {
            m_ModifiedEntities.pop_back();
        }
    }
};

// --- AFTER: unordered_set ---
struct VisibilityTrackerAfter {
    std::unordered_set<entity_id_t> m_ModifiedEntities;

    void RequestVisibilityUpdate(entity_id_t ent) {
        m_ModifiedEntities.insert(ent);
    }

    bool IsModified(entity_id_t ent) const {
        return m_ModifiedEntities.count(ent) > 0;
    }

    void DrainModified() {
        while (!m_ModifiedEntities.empty()) {
            auto it = m_ModifiedEntities.begin();
            m_ModifiedEntities.erase(it);
        }
    }
};

void test_correctness() {
    VisibilityTrackerBefore before;
    VisibilityTrackerAfter after;

    // Simulate entity visibility updates for 200 entities
    for (entity_id_t i = 1; i <= 200; ++i) {
        before.RequestVisibilityUpdate(i);
        after.RequestVisibilityUpdate(i);
    }

    // Duplicate requests (common when entities overlap LOS regions)
    for (entity_id_t i = 50; i <= 150; ++i) {
        before.RequestVisibilityUpdate(i);
        after.RequestVisibilityUpdate(i);
    }

    assert(before.m_ModifiedEntities.size() == after.m_ModifiedEntities.size());

    // Verify same membership
    for (entity_id_t i = 1; i <= 200; ++i) {
        assert(before.IsModified(i) == after.IsModified(i));
    }
    for (entity_id_t i = 201; i <= 300; ++i) {
        assert(!before.IsModified(i));
        assert(!after.IsModified(i));
    }

    printf("PASS correctness: %zu modified entities match\n", after.m_ModifiedEntities.size());
}

void test_performance() {
    const int E = 1000;  // entities in a large game
    const int QUERIES = 2000;  // visibility queries per frame (E * players)

    // BEFORE
    auto t0 = std::chrono::high_resolution_clock::now();
    VisibilityTrackerBefore before;
    for (int i = 0; i < E; ++i)
        before.RequestVisibilityUpdate(i);
    // Simulate GetLosVisibility querying m_ModifiedEntities for each entity
    int found_before = 0;
    for (int i = 0; i < QUERIES; ++i)
        if (before.IsModified(i % (E + 200)))
            found_before++;
    auto t1 = std::chrono::high_resolution_clock::now();

    // AFTER
    auto t2 = std::chrono::high_resolution_clock::now();
    VisibilityTrackerAfter after;
    for (int i = 0; i < E; ++i)
        after.RequestVisibilityUpdate(i);
    int found_after = 0;
    for (int i = 0; i < QUERIES; ++i)
        if (after.IsModified(i % (E + 200)))
            found_after++;
    auto t3 = std::chrono::high_resolution_clock::now();

    assert(found_before == found_after);

    double before_us = std::chrono::duration<double, std::micro>(t1 - t0).count();
    double after_us = std::chrono::duration<double, std::micro>(t3 - t2).count();
    double ratio = before_us / after_us;

    printf("PASS performance: before=%.0fus after=%.0fus ratio=%.1fx (E=%d, queries=%d)\n",
           before_us, after_us, ratio, E, QUERIES);
    assert(ratio > 2.0 && "Expected at least 2x speedup");
}

int main() {
    test_correctness();
    test_performance();
    printf("ALL TESTS PASSED\n");
    return 0;
}