1/*
2 * Copyright (c) 1998 - 2002 Kungliga Tekniska H�gskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the Institute nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34/*
35 * Heap
36 */
37
38#ifdef HAVE_CONFIG_H
39#include <config.h>
40RCSID("$Id$");
41#endif
42
43#include <assert.h>
44#include <stdio.h>
45#include <stdlib.h>
46#include "heap.h"
47
48struct heap {
49    heap_cmp_fn cmp;
50    unsigned max_sz;
51    unsigned sz;
52    heap_element *data;
53};
54
55/*
56 * Allocate a new heap of size `sz' with compare function `cmp'.
57 */
58
59Heap *
60heap_new (unsigned sz, heap_cmp_fn cmp)
61{
62    Heap *ret;
63    unsigned i;
64
65    assert(sz != 0);
66
67    ret = malloc (sizeof(*ret));
68    if (ret == NULL)
69	return ret;
70
71    ret->cmp    = cmp;
72    ret->max_sz = sz;
73    ret->sz     = 0;
74    ret->data   = malloc (sz * sizeof(*ret->data));
75    if (ret->data == NULL) {
76	free (ret);
77	return NULL;
78    }
79    for (i = 0; i < sz; ++i) {
80	ret->data[i].data = NULL;
81	ret->data[i].ptr  = NULL;
82    }
83    return ret;
84}
85
86static inline unsigned
87parent (unsigned n)
88{
89    return (n + 1) / 2 - 1;
90}
91
92static inline unsigned
93left_child (unsigned n)
94{
95    return 2 * n + 1;
96}
97
98static inline unsigned
99right_child (unsigned n)
100{
101    return 2 * n + 2;
102}
103
104static heap_ptr dummy;
105
106/*
107 *
108 */
109
110static void
111assign (Heap *h, unsigned n, heap_element el)
112{
113    h->data[n] = el;
114    *(h->data[n].ptr) = n;
115}
116
117/*
118 *
119 */
120
121static void
122upheap (Heap *h, unsigned n)
123{
124    heap_element v = h->data[n];
125
126    while (n > 0 && (*h->cmp)(h->data[parent(n)].data, v.data) > 0) {
127	assign (h, n, h->data[parent(n)]);
128	n = parent(n);
129    }
130    assign (h, n, v);
131}
132
133/*
134 *
135 */
136
137static void
138downheap (Heap *h, unsigned n)
139{
140    heap_element v = h->data[n];
141
142    while (n < h->sz / 2) {
143	int cmp1, cmp2;
144	unsigned new_n;
145
146	assert (left_child(n) < h->sz);
147
148	new_n = left_child(n);
149
150	cmp1 = (*h->cmp)(v.data, h->data[new_n].data);
151
152	if (right_child(n) < h->sz) {
153	    cmp2 = (*h->cmp)(v.data, h->data[right_child(n)].data);
154	    if (cmp2 > cmp1) {
155		cmp1  = cmp2;
156		new_n = right_child(n);
157	    }
158	}
159
160	if (cmp1 > 0) {
161	    assign (h, n, h->data[new_n]);
162	    n = new_n;
163	} else {
164	    break;
165	}
166    }
167    assign (h, n, v);
168}
169
170/*
171 * Insert a new element `data' into `h'.
172 * Return 0 if succesful or else -1.
173 */
174
175int
176heap_insert (Heap *h, const void *data, heap_ptr *ptr)
177{
178    assert (data != NULL);
179
180    if (h->sz == h->max_sz) {
181	unsigned new_sz = h->max_sz * 2;
182	heap_element *tmp;
183
184	tmp = realloc (h->data, new_sz * sizeof(*h->data));
185	if (tmp == NULL)
186	    return -1;
187	h->max_sz = new_sz;
188	h->data   = tmp;
189    }
190    if (ptr == NULL)
191	ptr = &dummy;
192
193    h->data[h->sz].data = data;
194    h->data[h->sz].ptr  = ptr;
195    upheap (h, h->sz);
196    ++h->sz;
197    return 0;
198}
199
200/*
201 * Return the head of the heap `h' (or NULL if it's empty).
202 */
203
204const void *
205heap_head (Heap *h)
206{
207    if (h->sz == 0)
208	return NULL;
209    else
210	return h->data[0].data;
211}
212
213/*
214 * Remove element `n' from the heap `h'
215 */
216
217static void
218remove_this (Heap *h, unsigned n)
219{
220    assert (n < h->sz);
221
222    --h->sz;
223    h->data[n] = h->data[h->sz];
224    h->data[h->sz].data = NULL;
225    h->data[h->sz].ptr  = NULL;
226    if (n != h->sz) {
227	downheap (h, n);
228	upheap (h, n);
229    }
230}
231
232/*
233 * Remove the head from the heap `h'.
234 */
235
236void
237heap_remove_head (Heap *h)
238{
239    remove_this (h, 0);
240}
241
242/*
243 * Remove this very element from the heap `h'.
244 * Return 0 if succesful and -1 if it couldn't be found.
245 */
246
247int
248heap_remove (Heap *h, heap_ptr ptr)
249{
250    if (h->sz == 0)
251	return -1;
252
253    assert (h->data[ptr].ptr != &dummy);
254
255    remove_this (h, ptr);
256    return 0;
257}
258
259/*
260 * Delete the heap `h'
261 */
262
263void
264heap_delete (Heap *h)
265{
266    free (h->data);
267    free (h);
268}
269
270/*
271 *
272 */
273
274static int
275do_verify (Heap *h, unsigned n)
276{
277    if (left_child(n) < h->sz) {
278	if((*h->cmp)(h->data[n].data, h->data[left_child(n)].data) > 0)
279	    return 0;
280	if (!do_verify (h, left_child(n)))
281	    return 0;
282    }
283    if (right_child(n) < h->sz) {
284	if((*h->cmp)(h->data[n].data, h->data[right_child(n)].data) > 0)
285	    return 0;
286	if (!do_verify (h, right_child(n)))
287	    return 0;
288    }
289    return 1;
290}
291
292/*
293 * Verify that `h' is really a heap.
294 */
295
296int
297heap_verify (Heap *h)
298{
299    return do_verify (h, 0);
300}
301