// Unit test for cataclysm-0003: surroundings_menu item/terfurn dedup
// Verifies that unordered_set dedup matches vector+std::find dedup
// for add_item_recursive and add_terfurn patterns.

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

int main() {
    // Simulate nearby items: radius 12 means ~(25)^2 = 625 tiles
    // Each tile may have 0-5 items. With item stacking, many names repeat.
    const int num_items = 2000;
    const int unique_names = 300;

    std::vector<std::string> item_names;
    for( int i = 0; i < num_items; i++ ) {
        item_names.push_back( "item_type_" + std::to_string( i % unique_names ) );
    }

    // BEFORE: vector + std::find for dedup
    auto t0 = std::chrono::high_resolution_clock::now();
    for( int run = 0; run < 500; run++ ) {
        std::vector<std::string> item_order;
        for( const auto &name : item_names ) {
            if( std::find( item_order.begin(), item_order.end(), name ) == item_order.end() ) {
                item_order.push_back( name );
            }
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    double ms_before = std::chrono::duration<double, std::milli>( t1 - t0 ).count();

    // Capture result for correctness check
    std::vector<std::string> result_before;
    for( const auto &name : item_names ) {
        if( std::find( result_before.begin(), result_before.end(), name ) == result_before.end() ) {
            result_before.push_back( name );
        }
    }

    // AFTER: unordered_set + vector for dedup
    auto t2 = std::chrono::high_resolution_clock::now();
    for( int run = 0; run < 500; run++ ) {
        std::vector<std::string> item_order;
        std::unordered_set<std::string> item_order_set;
        for( const auto &name : item_names ) {
            if( item_order_set.find( name ) == item_order_set.end() ) {
                item_order.push_back( name );
                item_order_set.insert( name );
            }
        }
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    double ms_after = std::chrono::duration<double, std::milli>( t3 - t2 ).count();

    // Capture result for correctness check
    std::vector<std::string> result_after;
    std::unordered_set<std::string> result_set;
    for( const auto &name : item_names ) {
        if( result_set.find( name ) == result_set.end() ) {
            result_after.push_back( name );
            result_set.insert( name );
        }
    }

    printf( "BEFORE (vector+find): %.3f ms\n", ms_before );
    printf( "AFTER  (unordered_set): %.3f ms\n", ms_after );

    // Verify correctness: same elements in same order
    assert( result_before.size() == result_after.size() );
    for( size_t i = 0; i < result_before.size(); i++ ) {
        assert( result_before[i] == result_after[i] );
    }
    assert( result_before.size() == static_cast<size_t>( unique_names ) );

    double ratio = ms_before / ms_after;
    printf( "Speedup ratio: %.1fx\n", ratio );
    assert( ratio > 2.0 );  // Must show clear improvement

    printf( "PASS: cataclysm-0003 surroundings_menu dedup\n" );
    return 0;
}