// Unit test for speed-dreams-0003: GfRaceManager constructor dedup
// std::find on vector for dedup O(N^2) -> std::set O(N log N)

#include <cassert>
#include <cstdio>
#include <chrono>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

// Original: O(N^2) dedup with linear scan
static std::vector<std::string> dedup_original(const std::vector<std::string> &input) {
    std::vector<std::string> result;
    for (const auto &s : input) {
        if (std::find(result.begin(), result.end(), s) == result.end())
            result.push_back(s);
    }
    return result;
}

// Patched: O(N log N) dedup with set
static std::vector<std::string> dedup_patched(const std::vector<std::string> &input) {
    std::vector<std::string> result;
    std::set<std::string> seen;
    for (const auto &s : input) {
        if (seen.find(s) == seen.end()) {
            seen.insert(s);
            result.push_back(s);
        }
    }
    return result;
}

int main()
{
    // Test 1: Basic correctness
    {
        std::vector<std::string> input = {"a", "b", "a", "c", "b", "d", "a"};
        auto orig = dedup_original(input);
        auto patched = dedup_patched(input);

        assert(orig.size() == patched.size());
        for (size_t i = 0; i < orig.size(); i++)
            assert(orig[i] == patched[i]);

        assert(orig.size() == 4);
        assert(orig[0] == "a");
        assert(orig[1] == "b");
        assert(orig[2] == "c");
        assert(orig[3] == "d");
        printf("PASS: basic correctness\n");
    }

    // Test 2: No duplicates
    {
        std::vector<std::string> input = {"x", "y", "z"};
        auto orig = dedup_original(input);
        auto patched = dedup_patched(input);
        assert(orig.size() == 3);
        assert(orig.size() == patched.size());
        printf("PASS: no duplicates\n");
    }

    // Test 3: All duplicates
    {
        std::vector<std::string> input = {"a", "a", "a", "a"};
        auto orig = dedup_original(input);
        auto patched = dedup_patched(input);
        assert(orig.size() == 1);
        assert(orig.size() == patched.size());
        printf("PASS: all duplicates\n");
    }

    // Test 4: Performance at scale N=1000 with 50% duplicates
    {
        const int N = 1000;
        std::vector<std::string> input;
        for (int i = 0; i < N; i++)
            input.push_back("type_" + std::to_string(i % (N / 2)));

        auto orig = dedup_original(input);
        auto patched = dedup_patched(input);
        assert(orig.size() == patched.size());

        const int ITERS = 500;

        auto t0 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < ITERS; i++)
            dedup_original(input);
        auto t1 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < ITERS; i++)
            dedup_patched(input);
        auto t2 = std::chrono::high_resolution_clock::now();

        double orig_us = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
        double patched_us = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
        double ratio = orig_us / patched_us;

        printf("PASS: performance N=%d: original=%.0fus patched=%.0fus ratio=%.1fx\n",
               N, orig_us, patched_us, ratio);

        assert(ratio > 2.0);
    }

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