#include <cassert>
#include <iostream>

#include "testmeap.h"

#include "../meaputils.h"

#define HEAP_PROP_ASSERT(assertion) \
    if( !(assertion) ) \
    { \
        std::cerr << "line " << line << ": assertion '" << #assertion \
            << "' failed." << std::endl; \
        MeapUtils::print_meap( meap, std::cerr ); \
        assert( assertion ); \
    }

void assert_heap_property( unsigned int line, const IntMeap& meap )
{
    for( IntMeap::const_iterator it = meap.begin(); it != meap.end(); ++it )
    {
        int value = *it;
        IntMeap::const_iterator l_it = meap.left_child( it );
        if( l_it != meap.end() )
        {
            HEAP_PROP_ASSERT( *l_it <= value )
            IntMeap::const_iterator r_it = meap.right_sibling( l_it );
            if( r_it != meap.end() )
            {
                HEAP_PROP_ASSERT( *r_it <= value );
            }
        }
    }
}

#define ASSERT_HEAP_PROPERTY( meap ) assert_heap_property( __LINE__, meap )

void test_Empty_after_creation()
{
    IntMeap meap;
    assert( meap.empty() );
    ASSERT_HEAP_PROPERTY( meap );
}

void test_Inserting_each_value_increases_size_by_one()
{
    IntMeap meap;

    meap.insert( 3 );
    assert( ! meap.empty() );
    assert( meap.size() == 1 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 2 );
    assert( meap.size() == 2 );
    ASSERT_HEAP_PROPERTY( meap );
}

void test_Inserting_equal_values_increases_size_each_time()
{
    IntMeap meap;

    meap.insert( 2 );
    assert( meap.size() == 1 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 2 );
    assert( meap.size() == 2 );
    ASSERT_HEAP_PROPERTY( meap );
}


void test_Top_is_largest_element()
{
    IntMeap meap;
    meap.insert( 1 );
    assert( meap.top() == 1 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 2 );
    assert( meap.top() == 2 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 5 );
    assert( meap.top() == 5 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 3 );
    assert( meap.top() == 5 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 7 );
    assert( meap.top() == 7 );
    ASSERT_HEAP_PROPERTY( meap );
}

void test_Top_empty_throws()
{
    IntMeap meap;

    bool exception_caught = false;
    try
    {
        meap.top();
    }
    catch( IntMeap::AccessingEmptyMeapException& )
    {
        exception_caught = true;
    }

    assert( exception_caught );
}

void test_Pop_empty_does_nothing()
{
    IntMeap meap;
    meap.pop();
    assert( meap.size() == 0 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.insert( 17 );
    meap.pop();
    assert( meap.size() == 0 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.pop();
    assert( meap.size() == 0 );
    ASSERT_HEAP_PROPERTY( meap );
}

void test_Pop_removes_top()
{
    IntMeap meap;
    meap.insert( 1 );
    meap.insert( 2 );
    meap.insert( 5 );
    meap.insert( 3 );
    meap.insert( 7 );

    assert( meap.top() == 7 );
    assert( meap.size() == 5 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.pop();
    assert( meap.top() == 5 );
    assert( meap.size() == 4 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.pop();
    assert( meap.top() == 3 );
    assert( meap.size() == 3 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.pop();
    assert( meap.top() == 2 );
    assert( meap.size() == 2 );
    ASSERT_HEAP_PROPERTY( meap );

    meap.pop();
    assert( meap.top() == 1 );
    assert( meap.size() == 1 );
    ASSERT_HEAP_PROPERTY( meap );
}


void test_meap()
{
    test_Empty_after_creation();
    test_Inserting_each_value_increases_size_by_one();
    test_Inserting_equal_values_increases_size_each_time();
    test_Top_is_largest_element();
    test_Top_empty_throws();
    test_Pop_empty_does_nothing();
    test_Pop_removes_top();
}