#include <iostream>
#include "intmeap.h"
#include "meaputils.h"

bool IntMeap::empty() const
{
    return values_.empty();
}

size_t IntMeap::size() const
{
    return values_.size();
}

namespace
{

void bubble_up( IntMeap::container_type& values, int value,
    IntMeap::index_type index )
{
    if( index == 0 )
    {
        return;
    }
    IntMeap::index_type parent_index = MeapUtils::get_parent_index( index );
    int parent_value = values[parent_index];
    while( parent_value < value )
    {
        MeapUtils::swap_values( values, index, parent_index );
        if( parent_index == 0 )
        {
            return;
        }
        index = parent_index;
        parent_index = MeapUtils::get_parent_index( index );
        parent_value = values[parent_index];
    }
}

}

void IntMeap::insert( int value )
{
    values_.push_back( value );
    bubble_up( values_, value, values_.size() - 1 );
}

int IntMeap::top() const
{
    if( values_.empty() )
    {
        throw AccessingEmptyMeapException();
    }

    return values_.front();
}


namespace
{

void child_indices_and_values(
      const IntMeap::index_type index
    , const IntMeap::container_type values
    , const int value
    , const size_t sz
    , IntMeap::index_type& ret_i1
    , IntMeap::index_type& ret_i2
    , int& ret_v1
    , int& ret_v2
    )
{
    ret_i1 = MeapUtils::get_left_child_index( index );
    if( ret_i1 >= sz )
    {
        return;
    }
    ret_v1 = values[ret_i1];

    ret_i2 = MeapUtils::get_right_sibling_index( ret_i1 );
    if( ret_i2 >= sz )
    {
        ret_v2 = value; // This means we will never choose to swap with i2
    }
    else
    {
        ret_v2 = values[ret_i2];
    }
}

void bubble_down( IntMeap::container_type& values, IntMeap::index_type index )
{
    size_t sz = values.size();
    int value = values[index];

    IntMeap::index_type i1;
    IntMeap::index_type i2;
    int v1;
    int v2;
    child_indices_and_values( index, values, value, sz, i1, i2, v1, v2 );

    if( i1 >= sz )
    {
        return;
    }

    while( v1 > value || v2 > value )
    {
        if( v1 < v2 )
        {
            MeapUtils::swap_values( values, index, i2 );
            index = i2;
        }
        else
        {
            MeapUtils::swap_values( values, index, i1 );
            index = i1;
        }

        child_indices_and_values( index, values, value, sz, i1, i2, v1, v2 );
        if( i1 >= sz )
        {
            return;
        }
    }
}

}

void IntMeap::pop()
{
    if( values_.empty() )
    {
        return;
    }

    values_.front() = values_.back();
    values_.pop_back();

    bubble_down( values_, 0 );
}


IntMeap::const_iterator IntMeap::begin() const
{
    return values_.begin();
}

IntMeap::iterator IntMeap::begin()
{
    return values_.begin();
}


IntMeap::const_iterator IntMeap::end() const
{
    return values_.end();
}

IntMeap::iterator IntMeap::end()
{
    return values_.end();
}


IntMeap::const_iterator IntMeap::left_child( const_iterator it ) const
{
    return MeapUtils::index_to_it( *this, MeapUtils::get_left_child_index(
        MeapUtils::it_to_index( *this, it ) ) );
}

IntMeap::const_iterator IntMeap::right_sibling( const_iterator it ) const
{
    std::advance( it, 1 );
    return it;
}