source: vis_dev/glu-2.3/src/heap/heap.c @ 88

Last change on this file since 88 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 13.7 KB
RevLine 
[13]1/**CFile***********************************************************************
2
3  FileName    [heap.c]
4
5  PackageName [heap]
6
7  Synopsis    [Heap-based priority queue.]
8
9  Description [This file contains the functions to maintain a priority
10  queue implemented as a heap.]
11
12  SeeAlso     []
13
14  Author      [Fabio Somenzi]
15
16  Copyright   [This file was created at the University of Colorado at
17  Boulder.  The University of Colorado at Boulder makes no warranty
18  about the suitability of this software for any purpose.  It is
19  presented on an AS IS basis.]
20
21******************************************************************************/
22
23#include "heapInt.h"
24
25
26/*---------------------------------------------------------------------------*/
27/* Constant declarations                                                     */
28/*---------------------------------------------------------------------------*/
29
30
31/*---------------------------------------------------------------------------*/
32/* Stucture declarations                                                     */
33/*---------------------------------------------------------------------------*/
34
35
36/*---------------------------------------------------------------------------*/
37/* Type declarations                                                         */
38/*---------------------------------------------------------------------------*/
39
40
41/*---------------------------------------------------------------------------*/
42/* Variable declarations                                                     */
43/*---------------------------------------------------------------------------*/
44
45#ifndef lint
46static char rcsid[] UNUSED = "$Id: heap.c,v 1.18 2005/05/18 19:25:43 jinh Exp $";
47#endif
48
49
50/*---------------------------------------------------------------------------*/
51/* Macro declarations                                                        */
52/*---------------------------------------------------------------------------*/
53
54
55
56/**AutomaticStart*************************************************************/
57
58/*---------------------------------------------------------------------------*/
59/* Static function prototypes                                                */
60/*---------------------------------------------------------------------------*/
61
62static void HeapHeapify ARGS((Heap_t *heap));
63static void HeapHeapifyCompare ARGS((Heap_t *heap));
64static int HeapResize ARGS((Heap_t *heap));
65
66/**AutomaticEnd***************************************************************/
67
68
69/*---------------------------------------------------------------------------*/
70/* Definition of exported functions                                          */
71/*---------------------------------------------------------------------------*/
72
73
74/**Function********************************************************************
75
76  Synopsis    [Initializes a priority queue.]
77
78  Description [Initializes a priority queue. Returns a pointer to the
79  heap if successful; NULL otherwise.  The queue is implemented as a
80  heap.  The first element of the heap is the one with the smallest
81  key.]
82
83  SideEffects [None]
84
85  SeeAlso     [Heap_HeapFree]
86
87******************************************************************************/
88Heap_t *
89Heap_HeapInit(
90  int length)
91{
92  Heap_t *heap;
93
94  heap = ALLOC(Heap_t, 1);
95  if (heap == NIL(Heap_t)) return NIL(Heap_t);
96  heap->length = length;
97  heap->nitems = 0;
98  heap->compare = 0;
99  heap->slots = ALLOC(HeapSlot_t, length);
100  if (heap->slots == NIL(HeapSlot_t)) {
101    FREE(heap);
102    return NIL(Heap_t);
103  }
104  return heap;
105
106} /* Heap_HeapInit */
107
108
109/**Function********************************************************************
110
111  Synopsis    [Initializes a priority queue.]
112
113  Description [Initializes a priority queue. Returns a pointer to the
114  heap if successful; NULL otherwise.  The queue is implemented as a
115  heap.  The first element of the heap is the one with the smallest
116  key.]
117
118  SideEffects [None]
119
120  SeeAlso     [Heap_HeapFree]
121
122******************************************************************************/
123Heap_t *
124Heap_HeapInitCompare(
125  int length, int (*compare)(const void *, const void *))
126{
127  Heap_t *heap;
128
129  heap = ALLOC(Heap_t, 1);
130  if (heap == NIL(Heap_t)) return NIL(Heap_t);
131  heap->length = length;
132  heap->nitems = 0;
133  heap->compare = compare;
134  heap->slots = ALLOC(HeapSlot_t, length);
135  if (heap->slots == NIL(HeapSlot_t)) {
136    FREE(heap);
137    return NIL(Heap_t);
138  }
139  return heap;
140
141} /* Heap_HeapInitCompare */
142
143
144/**Function********************************************************************
145
146  Synopsis    [Frees a priority queue.]
147
148  Description []
149
150  SideEffects [None]
151
152  SeeAlso     [Heap_HeapInit]
153
154******************************************************************************/
155void
156Heap_HeapFree(
157  Heap_t *heap)
158{
159  FREE(heap->slots);
160  FREE(heap);
161  return;
162
163} /* Heap_HeapFree */
164
165
166/**Function********************************************************************
167
168  Synopsis    [Inserts an item in a priority queue.]
169
170  Description [Inserts an item in a priority queue.  Returns 1 if
171  successful; 0 otherwise.]
172
173  SideEffects [None]
174
175  SeeAlso     [Heap_HeapExtractMin]
176
177******************************************************************************/
178int
179Heap_HeapInsert(
180  Heap_t *heap,
181  void *item,
182  long key)
183{
184  HeapSlot_t *slots;
185  int i = heap->nitems;
186
187  if (i == heap->length && !HeapResize(heap)) return 0;
188  slots = heap->slots;
189  heap->nitems++;
190  while (i > 0 && KEY(slots, PARENT(i)) > key) {
191    ITEM(slots, i) = ITEM(slots, PARENT(i));
192    KEY(slots, i) = KEY(slots, PARENT(i));
193    i = PARENT(i);
194  }
195  ITEM(slots, i) = item;
196  KEY(slots, i) = key;
197  return 1;
198
199} /* Heap_HeapInsert */
200
201/**Function********************************************************************
202
203  Synopsis    [Inserts an item in a priority queue.]
204
205  Description [Inserts an item in a priority queue.  Returns 1 if
206  successful; 0 otherwise.]
207
208  SideEffects [None]
209
210  SeeAlso     [Heap_HeapExtractMin]
211
212******************************************************************************/
213int
214Heap_HeapInsertCompare(
215  Heap_t *heap,
216  void *item,
217  long key)
218{
219  HeapSlot_t *slots;
220  int i = heap->nitems;
221
222  if (i == heap->length && !HeapResize(heap)) return 0;
223  slots = heap->slots;
224  heap->nitems++;
225  while (i > 0 && (*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)key)) {
226    ITEM(slots, i) = ITEM(slots, PARENT(i));
227    KEY(slots, i) = KEY(slots, PARENT(i));
228    i = PARENT(i);
229  }
230  ITEM(slots, i) = item;
231  KEY(slots, i) = key;
232  return 1;
233
234} /* Heap_HeapInsertCompare */
235
236
237
238/**Function********************************************************************
239
240  Synopsis    [Extracts the element with the minimum key from a priority
241  queue.]
242
243  Description [Extracts the element with the minimum key from a
244  priority queue.  Returns 1 if successful; 0 otherwise.]
245
246  SideEffects [The minimum key and the associated item are returned as
247  side effects.]
248
249  SeeAlso     [Heap_HeapInsert]
250
251******************************************************************************/
252int
253Heap_HeapExtractMin(
254  Heap_t *heap,
255  void *item,
256  long *key)
257{
258  HeapSlot_t *slots = heap->slots;
259
260  if (heap->nitems == 0) return 0;
261  *(void **)item = ITEM(slots, 0);
262  *key = KEY(slots, 0);
263  heap->nitems--;
264  /* The next three lines are redundant if the queue is empty. */
265  ITEM(slots, 0) = ITEM(slots, heap->nitems);
266  KEY(slots, 0) = KEY(slots, heap->nitems);
267  if(heap->compare) HeapHeapifyCompare(heap);
268  else              HeapHeapify(heap);
269
270  return 1;
271
272} /* Heap_HeapExtractMin */
273
274
275/**Function********************************************************************
276
277  Synopsis    [Returns the number of items in a priority queue.]
278
279  Description []
280
281  SideEffects [None]
282
283  SeeAlso     []
284
285******************************************************************************/
286int
287Heap_HeapCount(
288  Heap_t *heap)
289{
290  return(heap->nitems);
291
292} /* Heap_HeapCount */
293
294
295/**Function********************************************************************
296
297  Synopsis    [Clones a priority queue.]
298
299  Description []
300
301  SideEffects [None]
302
303  SeeAlso     [Heap_HeapInit]
304
305******************************************************************************/
306Heap_t *
307Heap_HeapClone(
308  Heap_t *source)
309{
310  Heap_t *dest;
311  int i;
312  int nitems = source->nitems;
313  HeapSlot_t *sslots = source->slots;
314  HeapSlot_t *dslots;
315
316  dest = Heap_HeapInit(source->length);
317  if (dest == NULL) return(NULL);
318  dest->nitems = nitems;
319  dslots = dest->slots;
320  for (i = 0; i < nitems; i++) {
321    KEY(dslots, i) = KEY(sslots, i);
322    ITEM(dslots, i) = ITEM(sslots, i);
323  }
324  return(dest);
325
326} /* Heap_HeapClone */
327
328
329/**Function********************************************************************
330
331  Synopsis    [Tests the heap property of a priority queue.]
332
333  Description [Tests the heap property of a priority queue.  Returns 1 if
334  successful; 0 otherwise.]
335
336  SideEffects [None]
337
338  SeeAlso     []
339
340******************************************************************************/
341int
342Heap_HeapTest(
343  Heap_t *heap)
344{
345  HeapSlot_t *slots = heap->slots;
346  int nitems = heap->nitems;
347  int i;
348
349  for (i = 1; i < nitems; i++) {
350    if (KEY(slots,i) < KEY(slots, PARENT(i)))
351      return 0;
352  }
353  return 1;
354
355} /* Heap_HeapTest */
356
357/**Function********************************************************************
358
359  Synopsis    [Tests the heap property of a priority queue.]
360
361  Description [Tests the heap property of a priority queue.  Returns 1 if
362  successful; 0 otherwise.]
363
364  SideEffects [None]
365
366  SeeAlso     []
367
368******************************************************************************/
369int
370Heap_HeapTestCompare(
371  Heap_t *heap)
372{
373  HeapSlot_t *slots = heap->slots;
374  int nitems = heap->nitems;
375  int i;
376
377  for (i = 1; i < nitems; i++) {
378    if ((*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)KEY(slots,i)))
379      return 0;
380  }
381  return 1;
382
383} /* Heap_HeapTest */
384
385
386
387
388/*---------------------------------------------------------------------------*/
389/* Definition of internal functions                                          */
390/*---------------------------------------------------------------------------*/
391
392
393/*---------------------------------------------------------------------------*/
394/* Definition of static functions                                            */
395/*---------------------------------------------------------------------------*/
396
397
398/**Function********************************************************************
399
400  Synopsis    [Maintains the heap property of a priority queue.]
401
402  Description []
403
404  SideEffects [None]
405
406  SeeAlso     [Heap_HeapExtractMin]
407
408******************************************************************************/
409static void
410HeapHeapify(
411  Heap_t *heap)
412{
413  int nitems = heap->nitems;
414  HeapSlot_t *slots = heap->slots;
415  int i = 0;
416  int smallest = 0;
417  void *item = ITEM(slots, 0);
418  long key = KEY(slots, 0);
419
420  while (1) {
421    int left = LEFT(i);
422    int right = RIGHT(i);
423    int minkey;
424    if (left < nitems && (minkey = KEY(slots, left)) < key) {
425      smallest = left;
426    } else {
427      minkey = key;
428    }
429    if (right < nitems && KEY(slots, right) < minkey) {
430      smallest = right;
431    }
432    if (smallest == i) break;
433    KEY(slots, i) = KEY(slots, smallest);
434    ITEM(slots, i) = ITEM(slots, smallest);
435    i = smallest;
436  }
437  KEY(slots, i) = key;
438  ITEM(slots, i) = item;
439  return;
440
441} /* HeapHeapify */
442
443/**Function********************************************************************
444
445  Synopsis    [Tests the heap property of a priority queue.]
446
447  Description [Tests the heap property of a priority queue.  Returns 1 if
448  successful; 0 otherwise.]
449
450  SideEffects [None]
451
452  SeeAlso     []
453
454******************************************************************************/
455static void
456HeapHeapifyCompare(
457  Heap_t *heap)
458{
459  int nitems = heap->nitems;
460  HeapSlot_t *slots = heap->slots;
461  int i = 0;
462  int smallest = 0;
463  void *item = ITEM(slots, 0);
464  int key = KEY(slots, 0);
465  int minkey;
466
467
468  while (1) {
469    int left = LEFT(i);
470    int right = RIGHT(i);
471    if (left < nitems && (*(heap->compare))((char *)(long)key, (char *)(long)(minkey = KEY(slots, left)))) {
472      smallest = left;
473    } else {
474      minkey = key;
475    }
476    if (right < nitems && (*(heap->compare))((char *)(long)minkey, (char *)(long)KEY(slots, right))) {
477      smallest = right;
478    }
479    if (smallest == i) break;
480    KEY(slots, i) = KEY(slots, smallest);
481    ITEM(slots, i) = ITEM(slots, smallest);
482    i = smallest;
483  }
484  KEY(slots, i) = key;
485  ITEM(slots, i) = item;
486  return;
487
488} /* HeapHeapifyCompare */
489
490
491/**Function********************************************************************
492
493  Synopsis    [Resizes a priority queue.]
494
495  Description [Resizes a priority queue by doubling the number of
496  available slots.  Returns 1 if successful; 0 otherwise.]
497
498  SideEffects [None]
499
500  SeeAlso     [Heap_HeapInsert]
501
502******************************************************************************/
503static int
504HeapResize(
505  Heap_t *heap)
506{
507  int oldlength = heap->length;
508  int newlength = 2 * oldlength;
509  HeapSlot_t *oldslots = heap->slots;
510  HeapSlot_t *newslots = REALLOC(HeapSlot_t, oldslots, newlength);
511  if (newslots == NIL(HeapSlot_t)) return 0;
512  heap->length = newlength;
513  heap->slots = newslots;
514  if (heap->compare) {
515    assert(Heap_HeapTestCompare(heap));
516  }
517  else {
518    assert(Heap_HeapTest(heap));
519  }
520  return 1;
521
522} /* HeapResize */
523
524/**Function********************************************************************
525
526  Synopsis    [Apply function for each element of heap.]
527
528  Description [Apply function for each element of heap.
529               Returns 1 if successful; 0 otherwise.]
530
531  SideEffects [ ]
532
533  SeeAlso     [ ]
534
535******************************************************************************/
536void
537Heap_HeapApplyForEachElement(Heap_t *heap, int (*compare)(const void *))
538{
539int i;
540
541  for(i=0; i<heap->nitems; i++) {
542    (*compare)(heap->slots[i].item);
543  }
544  return;
545}
Note: See TracBrowser for help on using the repository browser.