heap/test/mutable_heap_tests.hpp

/*=============================================================================
    Copyright (c) 2010 Tim Blechmann

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/

#include <random>

#include "common_heap_tests.hpp"


#define PUSH_WITH_HANDLES( HANDLES, Q, DATA )               \
    std::vector< typename pri_queue::handle_type > HANDLES; \
                                                            \
    for ( unsigned int k = 0; k != data.size(); ++k )       \
        HANDLES.push_back( Q.push( DATA[ k ] ) );


template < typename pri_queue >
void pri_queue_test_update_decrease( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        *handles[ i ] = -1;
        data[ i ]     = -1;
        q.update( handles[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_update_decrease_function( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ] = -1;
        q.update( handles[ i ], -1 );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_update_function_identity( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        q.update( handles[ i ], data[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_update_shuffled( void )
{
    pri_queue q;
    test_data data = make_test_data( test_size );
    PUSH_WITH_HANDLES( handles, q, data );

    test_data shuffled( data );
    std::shuffle( shuffled.begin(), shuffled.end(), get_rng() );

    for ( int i = 0; i != test_size; ++i )
        q.update( handles[ i ], shuffled[ i ] );

    check_q( q, data );
}


template < typename pri_queue >
void pri_queue_test_update_increase( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ]     = data.back() + 1;
        *handles[ i ] = data[ i ];
        q.update( handles[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_update_increase_function( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ] = data.back() + 1;
        q.update( handles[ i ], data[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_decrease( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        *handles[ i ] = -1;
        data[ i ]     = -1;
        q.decrease( handles[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_decrease_function( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ] = -1;
        q.decrease( handles[ i ], -1 );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_decrease_function_identity( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        q.decrease( handles[ i ], data[ i ] );

        check_q( q, data );
    }
}


template < typename pri_queue >
void pri_queue_test_increase( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ]     = data.back() + 1;
        *handles[ i ] = data[ i ];
        q.increase( handles[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_increase_function( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        data[ i ] = data.back() + 1;
        q.increase( handles[ i ], data[ i ] );

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_increase_function_identity( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        q.increase( handles[ i ], data[ i ] );

        check_q( q, data );
    }
}

template < typename pri_queue >
void pri_queue_test_erase( void )
{
    for ( int i = 0; i != test_size; ++i ) {
        pri_queue q;
        test_data data = make_test_data( test_size );
        PUSH_WITH_HANDLES( handles, q, data );

        for ( int j = 0; j != i; ++j ) {
            std::uniform_int_distribution<> range( 0, data.size() - 1 );

            int index = range( get_rng() );
            q.erase( handles[ index ] );
            handles.erase( handles.begin() + index );
            data.erase( data.begin() + index );
        }

        std::sort( data.begin(), data.end() );
        check_q( q, data );
    }
}


template < typename pri_queue >
void run_mutable_heap_update_tests( void )
{
    pri_queue_test_update_increase< pri_queue >();
    pri_queue_test_update_decrease< pri_queue >();

    pri_queue_test_update_shuffled< pri_queue >();
}

template < typename pri_queue >
void run_mutable_heap_update_function_tests( void )
{
    pri_queue_test_update_increase_function< pri_queue >();
    pri_queue_test_update_decrease_function< pri_queue >();
    pri_queue_test_update_function_identity< pri_queue >();
}


template < typename pri_queue >
void run_mutable_heap_decrease_tests( void )
{
    pri_queue_test_decrease< pri_queue >();
    pri_queue_test_decrease_function< pri_queue >();
    pri_queue_test_decrease_function_identity< pri_queue >();
}

template < typename pri_queue >
void run_mutable_heap_increase_tests( void )
{
    pri_queue_test_increase< pri_queue >();
    pri_queue_test_increase_function< pri_queue >();
    pri_queue_test_increase_function_identity< pri_queue >();
}

template < typename pri_queue >
void run_mutable_heap_erase_tests( void )
{
    pri_queue_test_erase< pri_queue >();
}

template < typename pri_queue >
void run_mutable_heap_test_handle_from_iterator( void )
{
    pri_queue que;

    que.push( 3 );
    que.push( 1 );
    que.push( 4 );

    que.update( pri_queue::s_handle_from_iterator( que.begin() ), 6 );
}


template < typename pri_queue >
void run_mutable_heap_tests( void )
{
    run_mutable_heap_update_function_tests< pri_queue >();
    run_mutable_heap_update_tests< pri_queue >();
    run_mutable_heap_decrease_tests< pri_queue >();
    run_mutable_heap_increase_tests< pri_queue >();
    run_mutable_heap_erase_tests< pri_queue >();
    run_mutable_heap_test_handle_from_iterator< pri_queue >();
}

template < typename pri_queue >
void run_ordered_iterator_tests()
{
    pri_queue_test_ordered_iterators< pri_queue >();
}