java-topology/defects/cataclysm-0002/test/cataclysm-0002-test.cpp

// Unit test for cataclysm-0002: dependency_tree dedup
// Verifies that unordered_set dedup matches vector+std::find dedup
// for get_dependencies_as_nodes and get_dependents_as_nodes patterns.

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

// Simulate dependency_node pointer dedup
struct FakeNode {
    int id;
};

int main() {
    const int N = 500;  // Number of dependency nodes

    // Create fake nodes
    std::vector<FakeNode> nodes( N );
    for( int i = 0; i < N; i++ ) {
        nodes[i].id = i;
    }

    // Simulate dependencies list with duplicates (as in BFS traversal)
    std::vector<FakeNode *> dependencies;
    for( int i = 0; i < N; i++ ) {
        dependencies.push_back( &nodes[i] );
        // Add some duplicates
        if( i % 3 == 0 ) {
            dependencies.push_back( &nodes[i / 2] );
        }
    }

    // BEFORE: vector + std::find for dedup
    std::vector<FakeNode *> ret_before;
    auto t0 = std::chrono::high_resolution_clock::now();
    for( int run = 0; run < 1000; run++ ) {
        ret_before.clear();
        for( auto it = dependencies.rbegin(); it != dependencies.rend(); ++it ) {
            if( std::find( ret_before.begin(), ret_before.end(), *it ) == ret_before.end() ) {
                ret_before.push_back( *it );
            }
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    double ms_before = std::chrono::duration<double, std::milli>( t1 - t0 ).count();

    // AFTER: unordered_set + vector for dedup
    std::vector<FakeNode *> ret_after;
    auto t2 = std::chrono::high_resolution_clock::now();
    for( int run = 0; run < 1000; run++ ) {
        ret_after.clear();
        std::unordered_set<FakeNode *> seen;
        for( auto it = dependencies.rbegin(); it != dependencies.rend(); ++it ) {
            if( seen.find( *it ) == seen.end() ) {
                ret_after.push_back( *it );
                seen.insert( *it );
            }
        }
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    double ms_after = std::chrono::duration<double, std::milli>( t3 - t2 ).count();

    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( ret_before.size() == ret_after.size() );
    for( size_t i = 0; i < ret_before.size(); i++ ) {
        assert( ret_before[i] == ret_after[i] );
    }

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

    // Also test inherit_errors pattern (string dedup)
    {
        const int E = 200;
        std::vector<std::string> errors;
        for( int i = 0; i < E; i++ ) {
            errors.push_back( "error_" + std::to_string( i ) );
        }
        // Add duplicates
        std::vector<std::string> new_errors;
        for( int i = 0; i < E; i++ ) {
            new_errors.push_back( "error_" + std::to_string( i % ( E / 2 ) ) );
        }

        // BEFORE: vector copy + std::find
        std::vector<std::string> result_before = errors;
        auto t4 = std::chrono::high_resolution_clock::now();
        for( int run = 0; run < 1000; run++ ) {
            result_before = errors;
            for( const auto &e : new_errors ) {
                if( std::find( result_before.begin(), result_before.end(), e ) == result_before.end() ) {
                    result_before.push_back( e );
                }
            }
        }
        auto t5 = std::chrono::high_resolution_clock::now();

        // AFTER: unordered_set + vector
        std::vector<std::string> result_after;
        auto t6 = std::chrono::high_resolution_clock::now();
        for( int run = 0; run < 1000; run++ ) {
            result_after = errors;
            std::unordered_set<std::string> seen_set( errors.begin(), errors.end() );
            for( const auto &e : new_errors ) {
                if( seen_set.find( e ) == seen_set.end() ) {
                    result_after.push_back( e );
                    seen_set.insert( e );
                }
            }
        }
        auto t7 = std::chrono::high_resolution_clock::now();

        double ms_b = std::chrono::duration<double, std::milli>( t5 - t4 ).count();
        double ms_a = std::chrono::duration<double, std::milli>( t7 - t6 ).count();
        printf( "inherit_errors BEFORE: %.3f ms, AFTER: %.3f ms, ratio: %.1fx\n",
                ms_b, ms_a, ms_b / ms_a );
        assert( result_before.size() == result_after.size() );
    }

    printf( "PASS: cataclysm-0002 dependency_tree dedup\n" );
    return 0;
}