Mercurial > hg > CbC > CbC_gcc
comparison gcc/fibonacci_heap.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Fibonacci heap for GNU compiler. | |
2 Copyright (C) 2016-2017 Free Software Foundation, Inc. | |
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 */ |