1 #include <vector>

     2 #include <algorithm>

     3 #include <functional>

     4 

     5 #include "cppunit/cppunit_proxy.h"

     6 

     7 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)

     8 using namespace std;

     9 #endif

    10 

    11 //

    12 // TestCase class

    13 //

    14 class HeapTest : public CPPUNIT_NS::TestCase

    15 {

    16   CPPUNIT_TEST_SUITE(HeapTest);

    17   CPPUNIT_TEST(mkheap0);

    18   CPPUNIT_TEST(mkheap1);

    19   CPPUNIT_TEST(pheap1);

    20   CPPUNIT_TEST(pheap2);

    21   CPPUNIT_TEST_SUITE_END();

    22 

    23 protected:

    24   void mkheap0();

    25   void mkheap1();

    26   void pheap1();

    27   void pheap2();

    28 };

    29 

    30 CPPUNIT_TEST_SUITE_REGISTRATION(HeapTest);

    31 

    32 //

    33 // tests implementation

    34 //

    35 void HeapTest::mkheap0()

    36 {

    37   int numbers[6] = { 5, 10, 4, 13, 11, 19 };

    38 

    39   make_heap(numbers, numbers + 6);

    40   CPPUNIT_ASSERT(numbers[0]==19)

    41   pop_heap(numbers, numbers + 6);

    42   CPPUNIT_ASSERT(numbers[0]==13)

    43   pop_heap(numbers, numbers + 5);

    44   CPPUNIT_ASSERT(numbers[0]==11)

    45   pop_heap(numbers, numbers + 4);

    46   CPPUNIT_ASSERT(numbers[0]==10)

    47   pop_heap(numbers, numbers + 3);

    48   CPPUNIT_ASSERT(numbers[0]==5)

    49   pop_heap(numbers, numbers + 2);

    50   CPPUNIT_ASSERT(numbers[0]==4)

    51   pop_heap(numbers, numbers + 1);

    52 }

    53 void HeapTest::mkheap1()

    54 {

    55   int numbers[6] = { 5, 10, 4, 13, 11, 19 };

    56 

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

    58 

    59   CPPUNIT_ASSERT(numbers[0]==4)

    60   pop_heap(numbers, numbers + 6, greater<int>());

    61   CPPUNIT_ASSERT(numbers[0]==5)

    62   pop_heap(numbers, numbers + 5, greater<int>());

    63   CPPUNIT_ASSERT(numbers[0]==10)

    64   pop_heap(numbers, numbers + 4, greater<int>());

    65   CPPUNIT_ASSERT(numbers[0]==11)

    66   pop_heap(numbers, numbers + 3, greater<int>());

    67   CPPUNIT_ASSERT(numbers[0]==13)

    68   pop_heap(numbers, numbers + 2, greater<int>());

    69   CPPUNIT_ASSERT(numbers[0]==19)

    70 }

    71 void HeapTest::pheap1()

    72 {

    73   vector<int> v;

    74 

    75   v.push_back(1);

    76   v.push_back(20);

    77   v.push_back(4);

    78   make_heap(v.begin(), v.end());

    79 

    80   v.push_back(7);

    81   push_heap(v.begin(), v.end());

    82 

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

    84 

    85   CPPUNIT_ASSERT(v[0]==1);

    86   CPPUNIT_ASSERT(v[1]==4);

    87   CPPUNIT_ASSERT(v[2]==7);

    88   CPPUNIT_ASSERT(v[3]==20);

    89 }

    90 void HeapTest::pheap2()

    91 {

    92   vector<int> v;

    93 

    94   v.push_back(1);

    95   v.push_back(20);

    96   v.push_back(4);

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

    98 

    99   v.push_back(7);

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

   101 

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

   103 

   104   CPPUNIT_ASSERT(v[0]==20);

   105   CPPUNIT_ASSERT(v[1]==7);

   106   CPPUNIT_ASSERT(v[2]==4);

   107   CPPUNIT_ASSERT(v[3]==1);

   108 }