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 } 109