|
1 /* |
|
2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 #include <vector> |
|
18 #include <algorithm> |
|
19 #include <functional> |
|
20 |
|
21 #include "cppunit/cppunit_proxy.h" |
|
22 |
|
23 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES) |
|
24 using namespace std; |
|
25 #endif |
|
26 |
|
27 // |
|
28 // TestCase class |
|
29 // |
|
30 class HeapTest : public CPPUNIT_NS::TestCase |
|
31 { |
|
32 CPPUNIT_TEST_SUITE(HeapTest); |
|
33 CPPUNIT_TEST(mkheap0); |
|
34 CPPUNIT_TEST(mkheap1); |
|
35 CPPUNIT_TEST(pheap1); |
|
36 CPPUNIT_TEST(pheap2); |
|
37 CPPUNIT_TEST_SUITE_END(); |
|
38 |
|
39 protected: |
|
40 void mkheap0(); |
|
41 void mkheap1(); |
|
42 void pheap1(); |
|
43 void pheap2(); |
|
44 }; |
|
45 |
|
46 CPPUNIT_TEST_SUITE_REGISTRATION(HeapTest); |
|
47 |
|
48 // |
|
49 // tests implementation |
|
50 // |
|
51 void HeapTest::mkheap0() |
|
52 { |
|
53 int numbers[6] = { 5, 10, 4, 13, 11, 19 }; |
|
54 |
|
55 make_heap(numbers, numbers + 6); |
|
56 CPPUNIT_ASSERT(numbers[0]==19) |
|
57 pop_heap(numbers, numbers + 6); |
|
58 CPPUNIT_ASSERT(numbers[0]==13) |
|
59 pop_heap(numbers, numbers + 5); |
|
60 CPPUNIT_ASSERT(numbers[0]==11) |
|
61 pop_heap(numbers, numbers + 4); |
|
62 CPPUNIT_ASSERT(numbers[0]==10) |
|
63 pop_heap(numbers, numbers + 3); |
|
64 CPPUNIT_ASSERT(numbers[0]==5) |
|
65 pop_heap(numbers, numbers + 2); |
|
66 CPPUNIT_ASSERT(numbers[0]==4) |
|
67 pop_heap(numbers, numbers + 1); |
|
68 } |
|
69 void HeapTest::mkheap1() |
|
70 { |
|
71 int numbers[6] = { 5, 10, 4, 13, 11, 19 }; |
|
72 |
|
73 make_heap(numbers, numbers + 6, greater<int>()); |
|
74 |
|
75 CPPUNIT_ASSERT(numbers[0]==4) |
|
76 pop_heap(numbers, numbers + 6, greater<int>()); |
|
77 CPPUNIT_ASSERT(numbers[0]==5) |
|
78 pop_heap(numbers, numbers + 5, greater<int>()); |
|
79 CPPUNIT_ASSERT(numbers[0]==10) |
|
80 pop_heap(numbers, numbers + 4, greater<int>()); |
|
81 CPPUNIT_ASSERT(numbers[0]==11) |
|
82 pop_heap(numbers, numbers + 3, greater<int>()); |
|
83 CPPUNIT_ASSERT(numbers[0]==13) |
|
84 pop_heap(numbers, numbers + 2, greater<int>()); |
|
85 CPPUNIT_ASSERT(numbers[0]==19) |
|
86 } |
|
87 void HeapTest::pheap1() |
|
88 { |
|
89 vector<int> v; |
|
90 |
|
91 v.push_back(1); |
|
92 v.push_back(20); |
|
93 v.push_back(4); |
|
94 make_heap(v.begin(), v.end()); |
|
95 |
|
96 v.push_back(7); |
|
97 push_heap(v.begin(), v.end()); |
|
98 |
|
99 sort_heap(v.begin(), v.end()); |
|
100 |
|
101 CPPUNIT_ASSERT(v[0]==1); |
|
102 CPPUNIT_ASSERT(v[1]==4); |
|
103 CPPUNIT_ASSERT(v[2]==7); |
|
104 CPPUNIT_ASSERT(v[3]==20); |
|
105 } |
|
106 void HeapTest::pheap2() |
|
107 { |
|
108 vector<int> v; |
|
109 |
|
110 v.push_back(1); |
|
111 v.push_back(20); |
|
112 v.push_back(4); |
|
113 make_heap(v.begin(), v.end(), greater<int>()); |
|
114 |
|
115 v.push_back(7); |
|
116 push_heap(v.begin(), v.end(), greater<int>()); |
|
117 |
|
118 sort_heap(v.begin(), v.end(), greater<int>()); |
|
119 |
|
120 CPPUNIT_ASSERT(v[0]==20); |
|
121 CPPUNIT_ASSERT(v[1]==7); |
|
122 CPPUNIT_ASSERT(v[2]==4); |
|
123 CPPUNIT_ASSERT(v[3]==1); |
|
124 } |