#include <vector>
#include <algorithm>
#include <functional>

#include "cppunit/cppunit_proxy.h"

#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
using namespace std;
#endif

//
// TestCase class
//
class HeapTest : public CPPUNIT_NS::TestCase
{
  CPPUNIT_TEST_SUITE(HeapTest);
  CPPUNIT_TEST(mkheap0);
  CPPUNIT_TEST(mkheap1);
  CPPUNIT_TEST(pheap1);
  CPPUNIT_TEST(pheap2);
  CPPUNIT_TEST_SUITE_END();

protected:
  void mkheap0();
  void mkheap1();
  void pheap1();
  void pheap2();
};

CPPUNIT_TEST_SUITE_REGISTRATION(HeapTest);

//
// tests implementation
//
void HeapTest::mkheap0()
{
  int numbers[6] = { 5, 10, 4, 13, 11, 19 };

  make_heap(numbers, numbers + 6);
  CPPUNIT_ASSERT(numbers[0]==19)
  pop_heap(numbers, numbers + 6);
  CPPUNIT_ASSERT(numbers[0]==13)
  pop_heap(numbers, numbers + 5);
  CPPUNIT_ASSERT(numbers[0]==11)
  pop_heap(numbers, numbers + 4);
  CPPUNIT_ASSERT(numbers[0]==10)
  pop_heap(numbers, numbers + 3);
  CPPUNIT_ASSERT(numbers[0]==5)
  pop_heap(numbers, numbers + 2);
  CPPUNIT_ASSERT(numbers[0]==4)
  pop_heap(numbers, numbers + 1);
}
void HeapTest::mkheap1()
{
  int numbers[6] = { 5, 10, 4, 13, 11, 19 };

  make_heap(numbers, numbers + 6, greater<int>());

  CPPUNIT_ASSERT(numbers[0]==4)
  pop_heap(numbers, numbers + 6, greater<int>());
  CPPUNIT_ASSERT(numbers[0]==5)
  pop_heap(numbers, numbers + 5, greater<int>());
  CPPUNIT_ASSERT(numbers[0]==10)
  pop_heap(numbers, numbers + 4, greater<int>());
  CPPUNIT_ASSERT(numbers[0]==11)
  pop_heap(numbers, numbers + 3, greater<int>());
  CPPUNIT_ASSERT(numbers[0]==13)
  pop_heap(numbers, numbers + 2, greater<int>());
  CPPUNIT_ASSERT(numbers[0]==19)
}
void HeapTest::pheap1()
{
  vector<int> v;

  v.push_back(1);
  v.push_back(20);
  v.push_back(4);
  make_heap(v.begin(), v.end());

  v.push_back(7);
  push_heap(v.begin(), v.end());

  sort_heap(v.begin(), v.end());

  CPPUNIT_ASSERT(v[0]==1);
  CPPUNIT_ASSERT(v[1]==4);
  CPPUNIT_ASSERT(v[2]==7);
  CPPUNIT_ASSERT(v[3]==20);
}
void HeapTest::pheap2()
{
  vector<int> v;

  v.push_back(1);
  v.push_back(20);
  v.push_back(4);
  make_heap(v.begin(), v.end(), greater<int>());

  v.push_back(7);
  push_heap(v.begin(), v.end(), greater<int>());

  sort_heap(v.begin(), v.end(), greater<int>());

  CPPUNIT_ASSERT(v[0]==20);
  CPPUNIT_ASSERT(v[1]==7);
  CPPUNIT_ASSERT(v[2]==4);
  CPPUNIT_ASSERT(v[3]==1);
}