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)
8using namespace std;
9#endif
10
11//
12// TestCase class
13//
14class 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
23protected:
24  void mkheap0();
25  void mkheap1();
26  void pheap1();
27  void pheap2();
28};
29
30CPPUNIT_TEST_SUITE_REGISTRATION(HeapTest);
31
32//
33// tests implementation
34//
35void 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}
53void 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}
71void 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}
90void 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}
109