1e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include <vector> 2e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include <algorithm> 3e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include <functional> 4e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 5e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "cppunit/cppunit_proxy.h" 6e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 7e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES) 8e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottusing namespace std; 9e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 10e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 11e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 12e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// TestCase class 13e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 14e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottclass HeapTest : public CPPUNIT_NS::TestCase 15e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 16e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST_SUITE(HeapTest); 17e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST(mkheap0); 18e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST(mkheap1); 19e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST(pheap1); 20e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST(pheap2); 21e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_TEST_SUITE_END(); 22e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 23e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprotected: 24e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void mkheap0(); 25e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void mkheap1(); 26e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void pheap1(); 27e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void pheap2(); 28e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 29e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 30e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottCPPUNIT_TEST_SUITE_REGISTRATION(HeapTest); 31e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 32e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 33e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// tests implementation 34e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 35e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid HeapTest::mkheap0() 36e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 37e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int numbers[6] = { 5, 10, 4, 13, 11, 19 }; 38e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 39e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott make_heap(numbers, numbers + 6); 40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==19) 41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 6); 42e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==13) 43e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 5); 44e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==11) 45e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 4); 46e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==10) 47e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 3); 48e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==5) 49e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 2); 50e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==4) 51e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 1); 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 53e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid HeapTest::mkheap1() 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 55e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int numbers[6] = { 5, 10, 4, 13, 11, 19 }; 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 57e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott make_heap(numbers, numbers + 6, greater<int>()); 58e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 59e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==4) 60e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 6, greater<int>()); 61e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==5) 62e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 5, greater<int>()); 63e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==10) 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 4, greater<int>()); 65e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==11) 66e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 3, greater<int>()); 67e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==13) 68e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott pop_heap(numbers, numbers + 2, greater<int>()); 69e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(numbers[0]==19) 70e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 71e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid HeapTest::pheap1() 72e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 73e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott vector<int> v; 74e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 75e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(1); 76e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(20); 77e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(4); 78e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott make_heap(v.begin(), v.end()); 79e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 80e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(7); 81e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott push_heap(v.begin(), v.end()); 82e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 83e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott sort_heap(v.begin(), v.end()); 84e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 85e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[0]==1); 86e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[1]==4); 87e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[2]==7); 88e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[3]==20); 89e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 90e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid HeapTest::pheap2() 91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 92e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott vector<int> v; 93e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 94e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(1); 95e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(20); 96e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(4); 97e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott make_heap(v.begin(), v.end(), greater<int>()); 98e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 99e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott v.push_back(7); 100e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott push_heap(v.begin(), v.end(), greater<int>()); 101e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 102e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott sort_heap(v.begin(), v.end(), greater<int>()); 103e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 104e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[0]==20); 105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[1]==7); 106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[2]==4); 107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CPPUNIT_ASSERT(v[3]==1); 108e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 109