]>
Commit | Line | Data |
---|---|---|
77ddb3e5 | 1 | /* Fibonacci heap for GNU compiler. |
fbd26352 | 2 | Copyright (C) 2016-2019 Free Software Foundation, Inc. |
77ddb3e5 | 3 | Contributed by Martin Liska <mliska@suse.cz> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 3, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "fibonacci_heap.h" | |
25 | #include "selftest.h" | |
26 | ||
27 | #if CHECKING_P | |
28 | ||
29 | namespace selftest { | |
30 | ||
31 | /* Selftests. */ | |
32 | ||
33 | /* Verify that operations with empty heap work. */ | |
34 | ||
35 | typedef fibonacci_node <int, int> int_heap_node_t; | |
36 | typedef fibonacci_heap <int, int> int_heap_t; | |
37 | ||
38 | static void | |
39 | test_empty_heap () | |
40 | { | |
41 | int_heap_t *h1 = new int_heap_t (INT_MIN); | |
42 | ||
43 | ASSERT_TRUE (h1->empty ()); | |
44 | ASSERT_EQ (0, h1->nodes ()); | |
45 | ASSERT_EQ (NULL, h1->min ()); | |
46 | ||
47 | int_heap_t *h2 = new int_heap_t (INT_MIN); | |
48 | ||
49 | int_heap_t *r = h1->union_with (h2); | |
50 | ASSERT_TRUE (r->empty ()); | |
51 | ASSERT_EQ (0, r->nodes ()); | |
52 | ASSERT_EQ (NULL, r->min ()); | |
53 | ||
54 | delete r; | |
55 | } | |
56 | ||
57 | #define TEST_HEAP_N 100 | |
58 | #define TEST_CALCULATE_VALUE(i) ((3 * i) + 10000) | |
59 | ||
60 | /* Verify heap basic operations. */ | |
61 | ||
62 | static void | |
63 | test_basic_heap_operations () | |
64 | { | |
65 | int values[TEST_HEAP_N]; | |
66 | int_heap_t *h1 = new int_heap_t (INT_MIN); | |
67 | ||
68 | for (unsigned i = 0; i < TEST_HEAP_N; i++) | |
69 | { | |
70 | values[i] = TEST_CALCULATE_VALUE (i); | |
71 | ASSERT_EQ (i, h1->nodes ()); | |
72 | h1->insert (i, &values[i]); | |
73 | ASSERT_EQ (0, h1->min_key ()); | |
74 | ASSERT_EQ (values[0], *h1->min ()); | |
75 | } | |
76 | ||
77 | for (unsigned i = 0; i < TEST_HEAP_N; i++) | |
78 | { | |
79 | ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ()); | |
80 | ASSERT_EQ ((int)i, h1->min_key ()); | |
81 | ASSERT_EQ (values[i], *h1->min ()); | |
82 | ||
83 | h1->extract_min (); | |
84 | } | |
85 | ||
86 | ASSERT_TRUE (h1->empty ()); | |
87 | ||
88 | delete h1; | |
89 | } | |
90 | ||
91 | /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values | |
92 | of each key is equal to 3 * key + 10000. BUFFER is used as a storage | |
93 | of values and NODES points to inserted nodes. */ | |
94 | ||
95 | static int_heap_t * | |
96 | build_simple_heap (int *buffer, int_heap_node_t **nodes) | |
97 | { | |
98 | int_heap_t *h = new int_heap_t (INT_MIN); | |
99 | ||
100 | for (unsigned i = 0; i < TEST_HEAP_N; i++) | |
101 | { | |
102 | buffer[i] = TEST_CALCULATE_VALUE (i); | |
103 | nodes[i] = h->insert (i, &buffer[i]); | |
104 | } | |
105 | ||
106 | return h; | |
107 | } | |
108 | ||
109 | /* Verify that fibonacci_heap::replace_key works. */ | |
110 | ||
111 | static void | |
112 | test_replace_key () | |
113 | { | |
114 | int values[TEST_HEAP_N]; | |
115 | int_heap_node_t *nodes[TEST_HEAP_N]; | |
116 | ||
117 | int_heap_t *heap = build_simple_heap (values, nodes); | |
118 | ||
119 | int N = 10; | |
120 | for (unsigned i = 0; i < (unsigned)N; i++) | |
121 | heap->replace_key (nodes[i], 100 * 1000 + i); | |
122 | ||
123 | ASSERT_EQ (TEST_HEAP_N, heap->nodes ()); | |
124 | ASSERT_EQ (N, heap->min_key ()); | |
125 | ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ()); | |
126 | ||
127 | for (int i = 0; i < TEST_HEAP_N - 1; i++) | |
128 | heap->extract_min (); | |
129 | ||
130 | ASSERT_EQ (1, heap->nodes ()); | |
131 | ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ()); | |
132 | ||
133 | delete heap; | |
134 | } | |
135 | ||
136 | /* Verify that heap can handle duplicate keys. */ | |
137 | ||
138 | static void | |
139 | test_duplicate_keys () | |
140 | { | |
141 | int values[3 * TEST_HEAP_N]; | |
142 | int_heap_t *heap = new int_heap_t (INT_MIN); | |
143 | ||
144 | for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++) | |
145 | { | |
146 | values[i] = TEST_CALCULATE_VALUE (i); | |
147 | heap->insert (i / 3, &values[i]); | |
148 | } | |
149 | ||
150 | ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ()); | |
151 | ASSERT_EQ (0, heap->min_key ()); | |
152 | ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ()); | |
153 | ||
154 | for (unsigned i = 0; i < 9; i++) | |
155 | heap->extract_min (); | |
156 | ||
157 | for (unsigned i = 0; i < 3; i++) | |
158 | { | |
159 | ASSERT_EQ (3, heap->min_key ()); | |
160 | heap->extract_min (); | |
161 | } | |
162 | ||
163 | delete heap; | |
164 | } | |
165 | ||
166 | /* Verify that heap can handle union. */ | |
167 | ||
168 | static void | |
169 | test_union () | |
170 | { | |
171 | int value = 777; | |
172 | ||
173 | int_heap_t *heap1 = new int_heap_t (INT_MIN); | |
174 | for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++) | |
175 | heap1->insert (i, &value); | |
176 | ||
177 | int_heap_t *heap2 = new int_heap_t (INT_MIN); | |
178 | for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++) | |
179 | heap2->insert (i, &value); | |
180 | ||
181 | int_heap_t *union_heap = heap1->union_with (heap2); | |
182 | ||
183 | for (int i = 0; i < 3 * TEST_HEAP_N; i++) | |
184 | { | |
185 | ASSERT_EQ (i, union_heap->min_key ()); | |
186 | union_heap->extract_min (); | |
187 | } | |
188 | ||
189 | delete union_heap; | |
190 | } | |
191 | ||
192 | /* Verify that heap can handle union with a heap having exactly the same | |
193 | keys. */ | |
194 | ||
195 | static void | |
196 | test_union_of_equal_heaps () | |
197 | { | |
198 | int value = 777; | |
199 | ||
200 | int_heap_t *heap1 = new int_heap_t (INT_MIN); | |
201 | for (unsigned i = 0; i < TEST_HEAP_N; i++) | |
202 | heap1->insert (i, &value); | |
203 | ||
204 | int_heap_t *heap2 = new int_heap_t (INT_MIN); | |
205 | for (unsigned i = 0; i < TEST_HEAP_N; i++) | |
206 | heap2->insert (i, &value); | |
207 | ||
208 | int_heap_t *union_heap = heap1->union_with (heap2); | |
209 | ||
210 | for (int i = 0; i < TEST_HEAP_N; i++) | |
211 | for (int j = 0; j < 2; j++) | |
212 | { | |
213 | ASSERT_EQ (i, union_heap->min_key ()); | |
214 | union_heap->extract_min (); | |
215 | } | |
216 | ||
217 | delete union_heap; | |
218 | } | |
219 | ||
220 | /* Dummy struct for testing. */ | |
221 | ||
251317e4 | 222 | class heap_key |
77ddb3e5 | 223 | { |
251317e4 | 224 | public: |
77ddb3e5 | 225 | heap_key (int k): key (k) |
226 | { | |
227 | } | |
228 | ||
229 | int key; | |
230 | ||
231 | bool operator< (const heap_key &other) const | |
232 | { | |
233 | return key > other.key; | |
234 | } | |
235 | ||
236 | bool operator== (const heap_key &other) const | |
237 | { | |
238 | return key == other.key; | |
239 | } | |
240 | ||
241 | bool operator> (const heap_key &other) const | |
242 | { | |
243 | return !(*this == other || *this < other); | |
244 | } | |
245 | }; | |
246 | ||
247 | typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t; | |
248 | ||
249 | /* Verify that heap can handle a struct as key type. */ | |
250 | ||
251 | static void | |
252 | test_struct_key () | |
253 | { | |
254 | int value = 123456; | |
255 | class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN); | |
256 | ||
257 | heap->insert (heap_key (1), &value); | |
258 | heap->insert (heap_key (10), &value); | |
259 | heap->insert (heap_key (100), &value); | |
260 | heap->insert (heap_key (1000), &value); | |
261 | ||
262 | ASSERT_EQ (1000, heap->min_key ().key); | |
263 | ASSERT_EQ (4, heap->nodes ()); | |
264 | heap->extract_min (); | |
265 | heap->extract_min (); | |
266 | ASSERT_EQ (10, heap->min_key ().key); | |
267 | heap->extract_min (); | |
268 | ASSERT_EQ (&value, heap->min ()); | |
269 | heap->extract_min (); | |
270 | ASSERT_TRUE (heap->empty ()); | |
271 | ||
272 | delete heap; | |
273 | } | |
274 | ||
275 | /* Run all of the selftests within this file. */ | |
276 | ||
277 | void | |
278 | fibonacci_heap_c_tests () | |
279 | { | |
280 | test_empty_heap (); | |
281 | test_basic_heap_operations (); | |
282 | test_replace_key (); | |
283 | test_duplicate_keys (); | |
284 | test_union (); | |
285 | test_union_of_equal_heaps (); | |
286 | test_struct_key (); | |
287 | } | |
288 | ||
289 | } // namespace selftest | |
290 | ||
291 | #endif /* #if CHECKING_P */ |