|
111
|
1 /* Fibonacci heap for GNU compiler.
|
|
131
|
2 Copyright (C) 2016-2018 Free Software Foundation, Inc.
|
|
111
|
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
|
|
|
222 struct heap_key
|
|
|
223 {
|
|
|
224 heap_key (int k): key (k)
|
|
|
225 {
|
|
|
226 }
|
|
|
227
|
|
|
228 int key;
|
|
|
229
|
|
|
230 bool operator< (const heap_key &other) const
|
|
|
231 {
|
|
|
232 return key > other.key;
|
|
|
233 }
|
|
|
234
|
|
|
235 bool operator== (const heap_key &other) const
|
|
|
236 {
|
|
|
237 return key == other.key;
|
|
|
238 }
|
|
|
239
|
|
|
240 bool operator> (const heap_key &other) const
|
|
|
241 {
|
|
|
242 return !(*this == other || *this < other);
|
|
|
243 }
|
|
|
244 };
|
|
|
245
|
|
|
246 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
|
|
|
247
|
|
|
248 /* Verify that heap can handle a struct as key type. */
|
|
|
249
|
|
|
250 static void
|
|
|
251 test_struct_key ()
|
|
|
252 {
|
|
|
253 int value = 123456;
|
|
|
254 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
|
|
|
255
|
|
|
256 heap->insert (heap_key (1), &value);
|
|
|
257 heap->insert (heap_key (10), &value);
|
|
|
258 heap->insert (heap_key (100), &value);
|
|
|
259 heap->insert (heap_key (1000), &value);
|
|
|
260
|
|
|
261 ASSERT_EQ (1000, heap->min_key ().key);
|
|
|
262 ASSERT_EQ (4, heap->nodes ());
|
|
|
263 heap->extract_min ();
|
|
|
264 heap->extract_min ();
|
|
|
265 ASSERT_EQ (10, heap->min_key ().key);
|
|
|
266 heap->extract_min ();
|
|
|
267 ASSERT_EQ (&value, heap->min ());
|
|
|
268 heap->extract_min ();
|
|
|
269 ASSERT_TRUE (heap->empty ());
|
|
|
270
|
|
|
271 delete heap;
|
|
|
272 }
|
|
|
273
|
|
|
274 /* Run all of the selftests within this file. */
|
|
|
275
|
|
|
276 void
|
|
|
277 fibonacci_heap_c_tests ()
|
|
|
278 {
|
|
|
279 test_empty_heap ();
|
|
|
280 test_basic_heap_operations ();
|
|
|
281 test_replace_key ();
|
|
|
282 test_duplicate_keys ();
|
|
|
283 test_union ();
|
|
|
284 test_union_of_equal_heaps ();
|
|
|
285 test_struct_key ();
|
|
|
286 }
|
|
|
287
|
|
|
288 } // namespace selftest
|
|
|
289
|
|
|
290 #endif /* #if CHECKING_P */
|
