// Unit test for cataclysm-0001: overmap_ui search dedup
// Verifies that unordered_set dedup matches vector+std::find dedup
// and measures O(1) vs O(N) lookup performance.

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

// Simulate point_abs_om as a simple pair
struct point_abs_om {
    int x, y;
    bool operator==( const point_abs_om &o ) const { return x == o.x && y == o.y; }
};

struct point_abs_om_hash {
    size_t operator()( const point_abs_om &p ) const {
        return std::hash<int>()( p.x ) ^ ( std::hash<int>()( p.y ) << 16 );
    }
};

int main() {
    // Generate overmap coordinates as if scanning radius 900
    // In practice, distinct overmaps = (2*900/180+1)^2 ~ 100
    const int num_overmaps = 100;
    const int num_lookups = 50000; // simulating many points mapping to same overmaps

    std::vector<point_abs_om> points;
    for( int i = 0; i < num_lookups; i++ ) {
        points.push_back( { i % num_overmaps, i / num_overmaps } );
    }

    // BEFORE: vector + std::find
    {
        std::vector<point_abs_om> checked;
        int found_count = 0;
        auto t0 = std::chrono::high_resolution_clock::now();
        for( const auto &p : points ) {
            if( std::find( checked.begin(), checked.end(), p ) == checked.end() ) {
                checked.push_back( p );
            } else {
                found_count++;
            }
        }
        auto t1 = std::chrono::high_resolution_clock::now();
        double ms_before = std::chrono::duration<double, std::milli>( t1 - t0 ).count();
        printf( "BEFORE (vector+find): %.3f ms, %d unique, %d dupes\n",
                ms_before, (int)checked.size(), found_count );

        // AFTER: unordered_set
        std::unordered_set<point_abs_om, point_abs_om_hash> checked_set;
        int found_count2 = 0;
        auto t2 = std::chrono::high_resolution_clock::now();
        for( const auto &p : points ) {
            if( checked_set.find( p ) == checked_set.end() ) {
                checked_set.insert( p );
            } else {
                found_count2++;
            }
        }
        auto t3 = std::chrono::high_resolution_clock::now();
        double ms_after = std::chrono::duration<double, std::milli>( t3 - t2 ).count();
        printf( "AFTER  (unordered_set): %.3f ms, %zu unique, %d dupes\n",
                ms_after, checked_set.size(), found_count2 );

        // Verify correctness
        assert( checked.size() == checked_set.size() );
        assert( found_count == found_count2 );

        double ratio = ms_before / ms_after;
        printf( "Speedup ratio: %.1fx\n", ratio );
        assert( ratio > 1.5 );  // Must be measurably faster

        printf( "PASS: cataclysm-0001 overmap search dedup\n" );
    }

    return 0;
}