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    int i;
64
65    ret = malloc (sizeof(*ret));
66    if (ret == NULL)
67	return ret;
68
69    ret->cmp    = cmp;
70    ret->max_sz = sz;
71    ret->sz     = 0;
72    ret->data   = malloc (sz * sizeof(*ret->data));
73    if (ret->sz != 0 && ret->data == NULL) {
74	free (ret);
75	return NULL;
76    }
77    for (i = 0; i < sz; ++i) {
78	ret->data[i].data = NULL;
79	ret->data[i].ptr  = NULL;
80    }
81    return ret;
82}
83
84static inline unsigned
85parent (unsigned n)
86{
87    return (n + 1) / 2 - 1;
88}
89
90static inline unsigned
91left_child (unsigned n)
92{
93    return 2 * n + 1;
94}
95
96static inline unsigned
97right_child (unsigned n)
98{
99    return 2 * n + 2;
100}
101
102static heap_ptr dummy;
103
104/*
105 *
106 */
107
108static void
109assign (Heap *h, unsigned n, heap_element el)
110{
111    h->data[n] = el;
112    *(h->data[n].ptr) = n;
113}
114
115/*
116 *
117 */
118
119static void
120upheap (Heap *h, unsigned n)
121{
122    heap_element v = h->data[n];
123
124    while (n > 0 && (*h->cmp)(h->data[parent(n)].data, v.data) > 0) {
125	assign (h, n, h->data[parent(n)]);
126	n = parent(n);
127    }
128    assign (h, n, v);
129}
130
131/*
132 *
133 */
134
135static void
136downheap (Heap *h, unsigned n)
137{
138    heap_element v = h->data[n];
139
140    while (n < h->sz / 2) {
141	int cmp1, cmp2;
142	unsigned new_n;
143
144	assert (left_child(n) < h->sz);
145
146	new_n = left_child(n);
147
148	cmp1 = (*h->cmp)(v.data, h->data[new_n].data);
149
150	if (right_child(n) < h->sz) {
151	    cmp2 = (*h->cmp)(v.data, h->data[right_child(n)].data);
152	    if (cmp2 > cmp1) {
153		cmp1  = cmp2;
154		new_n = right_child(n);
155	    }
156	}
157
158	if (cmp1 > 0) {
159	    assign (h, n, h->data[new_n]);
160	    n = new_n;
161	} else {
162	    break;
163	}
164    }
165    assign (h, n, v);
166}
167
168/*
169 * Insert a new element `data' into `h'.
170 * Return 0 if succesful or else -1.
171 */
172
173int
174heap_insert (Heap *h, const void *data, heap_ptr *ptr)
175{
176    assert (data != NULL);
177
178    if (h->sz == h->max_sz) {
179	unsigned new_sz = h->max_sz * 2;
180	heap_element *tmp;
181
182	tmp = realloc (h->data, new_sz * sizeof(*h->data));
183	if (tmp == NULL)
184	    return -1;
185	h->max_sz = new_sz;
186	h->data   = tmp;
187    }
188    if (ptr == NULL)
189	ptr = &dummy;
190
191    h->data[h->sz].data = data;
192    h->data[h->sz].ptr  = ptr;
193    upheap (h, h->sz);
194    ++h->sz;
195    return 0;
196}
197
198/*
199 * Return the head of the heap `h' (or NULL if it's empty).
200 */
201
202const void *
203heap_head (Heap *h)
204{
205    if (h->sz == 0)
206	return NULL;
207    else
208	return h->data[0].data;
209}
210
211/*
212 * Remove element `n' from the heap `h'
213 */
214
215static void
216remove_this (Heap *h, unsigned n)
217{
218    assert (n < h->sz);
219
220    --h->sz;
221    h->data[n] = h->data[h->sz];
222    h->data[h->sz].data = NULL;
223    h->data[h->sz].ptr  = NULL;
224    if (n != h->sz) {
225	downheap (h, n);
226	upheap (h, n);
227    }
228}
229
230/*
231 * Remove the head from the heap `h'.
232 */
233
234void
235heap_remove_head (Heap *h)
236{
237    remove_this (h, 0);
238}
239
240/*
241 * Remove this very element from the heap `h'.
242 * Return 0 if succesful and -1 if it couldn't be found.
243 */
244
245int
246heap_remove (Heap *h, heap_ptr ptr)
247{
248    if (h->sz == 0)
249	return -1;
250
251    assert (h->data[ptr].ptr != &dummy);
252
253    remove_this (h, ptr);
254    return 0;
255}
256
257/*
258 * Delete the heap `h'
259 */
260
261void
262heap_delete (Heap *h)
263{
264    free (h->data);
265    free (h);
266}
267
268/*
269 *
270 */
271
272static int
273do_verify (Heap *h, unsigned n)
274{
275    if (left_child(n) < h->sz) {
276	if((*h->cmp)(h->data[n].data, h->data[left_child(n)].data) > 0)
277	    return 0;
278	if (!do_verify (h, left_child(n)))
279	    return 0;
280    }
281    if (right_child(n) < h->sz) {
282	if((*h->cmp)(h->data[n].data, h->data[right_child(n)].data) > 0)
283	    return 0;
284	if (!do_verify (h, right_child(n)))
285	    return 0;
286    }
287    return 1;
288}
289
290/*
291 * Verify that `h' is really a heap.
292 */
293
294int
295heap_verify (Heap *h)
296{
297    return do_verify (h, 0);
298}
299