#include <iostream>
#include "boost/heap/binomial_heap.hpp"
#include "boost/heap/fibonacci_heap.hpp"
#include "boost/heap/pairing_heap.hpp"
#include "boost/heap/skew_heap.hpp"

struct heap_data
{
  int payload;

  heap_data( const int& x ) : payload( x ){}

  bool operator<( const heap_data& hd ) const
  {
    return payload > hd.payload;
  }

};
    
typedef boost::heap::binomial_heap<heap_data> b_heap_t;
typedef boost::heap::pairing_heap<heap_data> p_heap_t;
typedef boost::heap::skew_heap<heap_data> s_heap_t;
typedef boost::heap::fibonacci_heap<heap_data> f_heap_t;

template<typename Heap>
void
assign_heaps( Heap& pq1, Heap& pq2, Heap& pq3 )
{
  
  pq1.push(heap_data(2));
  pq1.push(heap_data(3));
  pq1.push(heap_data(1));

  pq2.push(heap_data(3));
  pq2.push(heap_data(4));
  pq2.push(heap_data(2));

  pq3.push(heap_data(4));
  pq3.push(heap_data(5));
  pq3.push(heap_data(3));

}

template<typename Heap>
void test1( void )
{
  Heap pq1, pq2, pq3;

  assign_heaps<Heap>( pq1, pq2, pq3 );

  pq2.merge( pq1 );   // I would think this would fully clear pq1

  pq1.merge( pq3 );

  std::cout << "In test 1, pq1:" << std::endl;

  // I would expect the following to print 3 4 5 but it prints 1 3 4 5
  // with the fibonacci heap

  for(
    typename Heap::ordered_iterator it = pq1.ordered_begin();
    it != pq1.ordered_end();
    it++
  )
  {
    std::cout << (*it).payload << std::endl;
  }
}

template<typename Heap>
void test2( void )
{
  Heap pq1, pq2, pq3;

  assign_heaps<Heap>( pq1, pq2, pq3 );

  pq2.merge( pq1 );
  pq1.clear();

  pq1.merge( pq3 );

  std::cout << "In test 2, pq1:" << std::endl;

  // The following prints out 3 4 5 as expected in all cases because I
  // cleared pq1 before merging in pq3.

  for(
    typename Heap::ordered_iterator it = pq1.ordered_begin();
    it != pq1.ordered_end();
    it++
  )
  {
    std::cout << (*it).payload << std::endl;
  }
}

int main(void)
{

  std::cout << std::endl << "Binomial heap:" << std::endl;

  test1<b_heap_t>();

  test2<b_heap_t>();

  std::cout << std::endl << "Pairing heap:" << std::endl;

  test1<p_heap_t>();

  test2<p_heap_t>();

  std::cout << std::endl << "Skew heap:" << std::endl;

  test1<s_heap_t>();

  test2<s_heap_t>();

  std::cout << std::endl << "Fibonacci heap:" << std::endl;

  test1<f_heap_t>();

  test2<f_heap_t>();

  return 0;

}