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