java-topology/defects/openxcom-0002/test/test_research_lookup.cpp

// Unit test for openxcom-0002: SavedGame isResearched / getAvailableResearchProjects
// vector linear scan O(R*D) -> unordered_set O(1) lookup
//
// Defect: SavedGame::isResearched(string) iterates _discovered vector O(D) per call.
// Called from getAvailableResearchProjects in a loop over all research topics (R),
// multiple times per topic (dependencies, requirements, name check, getOneFree).
// With 100+ research topics and 50+ discovered, this is O(R*D) = O(5000+) string
// comparisons per base per geoscape tick.
//
// Additionally, getAvailableResearchProjects builds an "unlocked" vector and uses
// std::find for membership, adding O(R*U) where U = unlocked topics.
//
// Fix: Maintain parallel unordered_set<string> _discoveredNames for O(1) lookup.
// Use unordered_set for unlocked collection.

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <cassert>
#include <string>

// Simulate research name strings
std::string makeResearchName(int i) {
    return "STR_RESEARCH_TOPIC_" + std::to_string(i);
}

// Defective: linear scan of discovered vector
bool isResearchedDefective(const std::vector<std::string>& discovered, const std::string& name) {
    for (size_t i = 0; i < discovered.size(); ++i) {
        if (discovered[i] == name)
            return true;
    }
    return false;
}

// Fixed: hash set lookup
bool isResearchedFixed(const std::unordered_set<std::string>& discovered, const std::string& name) {
    return discovered.count(name) != 0;
}

int main() {
    // Typical late-game: 150 research topics, 80 discovered
    const int TOTAL_RESEARCH = 150;
    const int DISCOVERED = 80;
    const int CALLS_PER_TOPIC = 4; // deps + reqs + name + getOneFree
    const int BASES = 8; // max bases

    // Build discovered sets
    std::vector<std::string> discoveredVec;
    std::unordered_set<std::string> discoveredSet;
    for (int i = 0; i < DISCOVERED; ++i) {
        std::string name = makeResearchName(i);
        discoveredVec.push_back(name);
        discoveredSet.insert(name);
    }

    // Build query names (all research topics)
    std::vector<std::string> allTopics;
    for (int i = 0; i < TOTAL_RESEARCH; ++i) {
        allTopics.push_back(makeResearchName(i));
    }

    // Correctness check
    for (int i = 0; i < TOTAL_RESEARCH; ++i) {
        bool a = isResearchedDefective(discoveredVec, allTopics[i]);
        bool b = isResearchedFixed(discoveredSet, allTopics[i]);
        assert(a == b);
    }
    std::cout << "Correctness: PASS" << std::endl;

    // Benchmark: vector (defective) -- simulates getAvailableResearchProjects across all bases
    auto t0 = std::chrono::high_resolution_clock::now();
    int dummy1 = 0;
    for (int base = 0; base < BASES; ++base) {
        for (int topic = 0; topic < TOTAL_RESEARCH; ++topic) {
            for (int call = 0; call < CALLS_PER_TOPIC; ++call) {
                dummy1 += isResearchedDefective(discoveredVec, allTopics[topic]) ? 1 : 0;
            }
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();

    // Benchmark: unordered_set (fixed)
    auto t2 = std::chrono::high_resolution_clock::now();
    int dummy2 = 0;
    for (int base = 0; base < BASES; ++base) {
        for (int topic = 0; topic < TOTAL_RESEARCH; ++topic) {
            for (int call = 0; call < CALLS_PER_TOPIC; ++call) {
                dummy2 += isResearchedFixed(discoveredSet, allTopics[topic]) ? 1 : 0;
            }
        }
    }
    auto t3 = std::chrono::high_resolution_clock::now();

    double vecUs = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    double setUs = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    double ratio = vecUs / (setUs > 0 ? setUs : 1);

    std::cout << "Vector (defective): " << vecUs << " us" << std::endl;
    std::cout << "Set    (fixed):     " << setUs << " us" << std::endl;
    std::cout << "Ratio: " << ratio << "x" << std::endl;
    std::cout << "Parameters: R=" << TOTAL_RESEARCH << " topics, D=" << DISCOVERED
              << " discovered, " << CALLS_PER_TOPIC << " calls/topic, "
              << BASES << " bases" << std::endl;

    // Verify significant speedup
    assert(ratio > 2.0);
    std::cout << "Performance: PASS (ratio > 2x)" << std::endl;

    assert(dummy1 == dummy2);

    std::cout << "ALL TESTS PASSED" << std::endl;
    return 0;
}