heap/test/stable_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 "common_heap_tests.hpp"

struct q_tester
{
    q_tester( int i = 0, int j = 0 ) :
        value( i ),
        id( j )
    {}

    bool operator<( q_tester const& rhs ) const
    {
        return value < rhs.value;
    }

    bool operator>( q_tester const& rhs ) const
    {
        return value > rhs.value;
    }

    bool operator==( q_tester const& rhs ) const
    {
        return ( value == rhs.value ) && ( id == rhs.id );
    }

    int value;
    int id;
};

std::ostream& operator<<( std::ostream& out, q_tester const& t )
{
    out << "[" << t.value << " " << t.id << "]";
    return out;
}

typedef std::vector< q_tester > stable_test_data;

stable_test_data make_stable_test_data( int size, int same_count = 3, int offset = 0, int strive = 1 )
{
    stable_test_data ret;

    for ( int i = 0; i != size; ++i )
        for ( int j = 0; j != same_count; ++j )
            ret.push_back( q_tester( i * strive + offset, j ) );
    return ret;
}

struct compare_by_id
{
    bool operator()( q_tester const& lhs, q_tester const& rhs )
    {
        return lhs.id > rhs.id;
    }
};

template < typename pri_queue >
void pri_queue_stable_test_sequential_push( void )
{
    stable_test_data data = make_stable_test_data( test_size );

    pri_queue q;
    fill_q( q, data );
    std::stable_sort( data.begin(), data.end(), compare_by_id() );
    std::stable_sort( data.begin(), data.end(), std::less< q_tester >() );
    check_q( q, data );
}

template < typename pri_queue >
void pri_queue_stable_test_sequential_reverse_push( void )
{
    stable_test_data data = make_stable_test_data( test_size );
    pri_queue        q;
    stable_test_data push_data( data );

    std::stable_sort( push_data.begin(), push_data.end(), std::greater< q_tester >() );

    fill_q( q, push_data );

    std::stable_sort( data.begin(), data.end(), compare_by_id() );
    std::stable_sort( data.begin(), data.end(), std::less< q_tester >() );

    check_q( q, data );
}


template < typename pri_queue >
void run_stable_heap_tests( void )
{
    pri_queue_stable_test_sequential_push< pri_queue >();
    pri_queue_stable_test_sequential_reverse_push< pri_queue >();
}