distr/nanotrav/ntrHeap.c

   1 /**CFile***********************************************************************
   2
   3   FileName    [ntrHeap.c]
   4
   5   PackageName [ntr]
   6
   7   Synopsis    [Functions for heap-based priority queue.]
   8
   9   Description [The functions in this file manage a priority queue implemented
  10   as a heap. The first element of the heap is the one with the smallest key.
  11   Refer to Chapter 7 of Cormen, Leiserson, and Rivest for the theory.]
  12
  13   SeeAlso     []
  14
  15   Author      [Fabio Somenzi]
  16
  17   Copyright   [Copyright (c) 1995-2004, Regents of the University of Colorado
  18
  19   All rights reserved.
  20
  21   Redistribution and use in source and binary forms, with or without
  22   modification, are permitted provided that the following conditions
  23   are met:
  24
  25   Redistributions of source code must retain the above copyright
  26   notice, this list of conditions and the following disclaimer.
  27
  28   Redistributions in binary form must reproduce the above copyright
  29   notice, this list of conditions and the following disclaimer in the
  30   documentation and/or other materials provided with the distribution.
  31
  32   Neither the name of the University of Colorado nor the names of its
  33   contributors may be used to endorse or promote products derived from
  34   this software without specific prior written permission.
  35
  36   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  37   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  38   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  39   FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  40   COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  41   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  42   BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  43   LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  44   CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  45   LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  46   ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  47   POSSIBILITY OF SUCH DAMAGE.]
  48
  49 ******************************************************************************/
  50
  51 #include "ntr.h"
  52
  53 /*---------------------------------------------------------------------------*/
  54 /* Constant declarations                                                     */
  55 /*---------------------------------------------------------------------------*/
  56
  57
  58 /*---------------------------------------------------------------------------*/
  59 /* Stucture declarations                                                     */
  60 /*---------------------------------------------------------------------------*/
  61
  62 /*---------------------------------------------------------------------------*/
  63 /* Type declarations                                                         */
  64 /*---------------------------------------------------------------------------*/
  65
  66 /*---------------------------------------------------------------------------*/
  67 /* Variable declarations                                                     */
  68 /*---------------------------------------------------------------------------*/
  69
  70 #ifndef lint
  71 static char rcsid[] UTIL_UNUSED = "$Id: ntrHeap.c,v 1.5 2004/08/13 18:28:28 fabio Exp fabio $";
  72 #endif
  73
  74 /*---------------------------------------------------------------------------*/
  75 /* Macro declarations                                                        */
  76 /*---------------------------------------------------------------------------*/
  77
  78 #define PARENT(i)       (((i)-1)>>1)
  79 #define RIGHT(i)        (((i)+1)<<1)
  80 #define LEFT(i)         (((i)<<1)|1)
  81 #define ITEM(p,i)       ((p)[i].item)
  82 #define KEY(p,i)        ((p)[i].key)
  83
  84 /**AutomaticStart*************************************************************/
  85
  86 /*---------------------------------------------------------------------------*/
  87 /* Static function prototypes                                                */
  88 /*---------------------------------------------------------------------------*/
  89
  90 static void ntrHeapify (NtrHeap *heap, int i);
  91 static int ntrHeapResize (NtrHeap *heap);
  92
  93 /**AutomaticEnd***************************************************************/
  94
  95 /*---------------------------------------------------------------------------*/
  96 /* Definition of exported functions                                          */
  97 /*---------------------------------------------------------------------------*/
  98
  99
 100 /**Function********************************************************************
 101
 102   Synopsis    [Initializes a priority queue.]
 103
 104   Description [Initializes a priority queue. Returns a pointer to the heap
 105   if successful; NULL otherwise.]
 106
 107   SideEffects [None]
 108
 109   SeeAlso     [Ntr_FreeHeap]
 110
 111 ******************************************************************************/
 112 NtrHeap *
 113 Ntr_InitHeap(
 114   int size)
 115 {
 116     NtrHeap *heap;
 117
 118     heap = ALLOC(NtrHeap,1);
 119     if (heap == NULL) return(NULL);
 120     heap->size = size;
 121     heap->nslots = 0;
 122     heap->slots = ALLOC(NtrHeapSlot,size);
 123     if (heap->slots == NULL) {
 124         FREE(heap);
 125         return(NULL);
 126     }
 127     return(heap);
 128
 129 } /* end of Ntr_InitHeap */
 130
 131
 132 /**Function********************************************************************
 133
 134   Synopsis    [Frees a priority queue.]
 135
 136   Description []
 137
 138   SideEffects [None]
 139
 140   SeeAlso     [Ntr_InitHeap]
 141
 142 ******************************************************************************/
 143 void
 144 Ntr_FreeHeap(
 145   NtrHeap *heap)
 146 {
 147     FREE(heap->slots);
 148     FREE(heap);
 149     return;
 150
 151 } /* end of Ntr_FreeHeap */
 152
 153
 154 /**Function********************************************************************
 155
 156   Synopsis    [Inserts an item in a priority queue.]
 157
 158   Description [Inserts an item in a priority queue. Returns 1 if successful;
 159   0 otherwise.]
 160
 161   SideEffects [None]
 162
 163   SeeAlso     [Ntr_HeapExtractMin]
 164
 165 ******************************************************************************/
 166 int
 167 Ntr_HeapInsert(
 168   NtrHeap *heap,
 169   void *item,
 170   int key)
 171 {
 172     NtrHeapSlot *slots;
 173     int i = heap->nslots;
 174
 175     if (i == heap->size && !ntrHeapResize(heap)) return(0);
 176     slots = heap->slots;
 177     heap->nslots++;
 178     while (i > 0 && KEY(slots,PARENT(i)) > key) {
 179         ITEM(slots,i) = ITEM(slots,PARENT(i));
 180         KEY(slots,i) = KEY(slots,PARENT(i));
 181         i = PARENT(i);
 182     }
 183     ITEM(slots,i) = item;
 184     KEY(slots,i) = key;
 185     return(1);
 186
 187 } /* end of Ntr_HeapInsert */
 188
 189
 190 /**Function********************************************************************
 191
 192   Synopsis    [Extracts the element with the minimum key from a priority
 193   queue.]
 194
 195   Description [Extracts the element with the minimum key from a priority
 196   queue. Returns 1 if successful; 0 otherwise.]
 197
 198   SideEffects [The minimum key and the associated item are returned as
 199   side effects.]
 200
 201   SeeAlso     [Ntr_HeapInsert]
 202
 203 ******************************************************************************/
 204 int
 205 Ntr_HeapExtractMin(
 206   NtrHeap *heap,
 207   void *item,
 208   int *key)
 209 {
 210     NtrHeapSlot *slots = heap->slots;
 211
 212     if (heap->nslots == 0) return(0);
 213     *(void **)item = ITEM(slots,0);
 214     *key = KEY(slots,0);
 215     heap->nslots--;
 216     ITEM(slots,0) = ITEM(slots,heap->nslots);
 217     KEY(slots,0) = KEY(slots,heap->nslots);
 218     ntrHeapify(heap,0);
 219
 220     return(1);
 221
 222 } /* end of Ntr_HeapExtractMin */
 223
 224
 225 /**Function********************************************************************
 226
 227   Synopsis    [Returns the number of items in a priority queue.]
 228
 229   Description []
 230
 231   SideEffects [None]
 232
 233   SeeAlso     []
 234
 235 ******************************************************************************/
 236 int
 237 Ntr_HeapCount(
 238   NtrHeap *heap)
 239 {
 240     return(heap->nslots);
 241
 242 } /* end of Ntr_HeapCount */
 243
 244
 245 /**Function********************************************************************
 246
 247   Synopsis    [Clones a priority queue.]
 248
 249   Description []
 250
 251   SideEffects [None]
 252
 253   SeeAlso     [Ntr_InitHeap]
 254
 255 ******************************************************************************/
 256 NtrHeap *
 257 Ntr_HeapClone(
 258   NtrHeap *source)
 259 {
 260     NtrHeap *dest;
 261     int i;
 262     int nslots = source->nslots;
 263     NtrHeapSlot *sslots = source->slots;
 264     NtrHeapSlot *dslots;
 265
 266     dest = Ntr_InitHeap(source->size);
 267     if (dest == NULL) return(NULL);
 268     dest->nslots = nslots;
 269     dslots = dest->slots;
 270     for (i = 0; i < nslots; i++) {
 271         KEY(dslots,i) = KEY(sslots,i);
 272         ITEM(dslots,i) = ITEM(sslots,i);
 273     }
 274     return(dest);
 275
 276 } /* end of Ntr_HeapClone */
 277
 278
 279 /**Function********************************************************************
 280
 281   Synopsis    [Tests the heap property of a priority queue.]
 282
 283   Description [Tests the heap property of a priority queue. Returns 1 if
 284   Successful; 0 otherwise.]
 285
 286   SideEffects [None]
 287
 288   SeeAlso     []
 289
 290 ******************************************************************************/
 291 int
 292 Ntr_TestHeap(
 293   NtrHeap *heap,
 294   int i)
 295 {
 296     NtrHeapSlot *slots = heap->slots;
 297     int nslots = heap->nslots;
 298
 299     if (i > 0 && KEY(slots,i) < KEY(slots,PARENT(i)))
 300         return(0);
 301     if (LEFT(i) < nslots) {
 302         if (!Ntr_TestHeap(heap,LEFT(i)))
 303             return(0);
 304     }
 305     if (RIGHT(i) < nslots) {
 306         if (!Ntr_TestHeap(heap,RIGHT(i)))
 307             return(0);
 308     }
 309     return(1);
 310
 311 } /* end of Ntr_TestHeap */
 312
 313
 314 /*---------------------------------------------------------------------------*/
 315 /* Definition of static functions                                            */
 316 /*---------------------------------------------------------------------------*/
 317
 318
 319 /**Function********************************************************************
 320
 321   Synopsis    [Maintains the heap property of a priority queue.]
 322
 323   Description []
 324
 325   SideEffects [None]
 326
 327   SeeAlso     [Ntr_HeapExtractMin]
 328
 329 ******************************************************************************/
 330 static void
 331 ntrHeapify(
 332   NtrHeap *heap,
 333   int i)
 334 {
 335     int smallest;
 336     int left = LEFT(i);
 337     int right = RIGHT(i);
 338     int nslots = heap->nslots;
 339     NtrHeapSlot *slots = heap->slots;
 340     int key = KEY(slots,i);
 341
 342     if (left < nslots && KEY(slots,left) < key) {
 343         smallest = left;
 344     } else {
 345         smallest = i;
 346     }
 347     if (right < nslots && KEY(slots,right) < KEY(slots,smallest)) {
 348         smallest = right;
 349     }
 350     if (smallest != i) {
 351         void *item = ITEM(slots,i);
 352         KEY(slots,i) = KEY(slots,smallest);
 353         ITEM(slots,i) = ITEM(slots,smallest);
 354         KEY(slots,smallest) = key;
 355         ITEM(slots,smallest) = item;
 356         ntrHeapify(heap,smallest);
 357     }
 358
 359     return;
 360
 361 } /* end of ntrHeapify */
 362
 363
 364 /**Function********************************************************************
 365
 366   Synopsis    [Resizes a priority queue.]
 367
 368   Description [Resizes a priority queue by doubling the number of
 369   available slots.  Returns 1 if successful; 0 otherwise.]
 370
 371   SideEffects [None]
 372
 373   SeeAlso     [Ntr_HeapInsert]
 374
 375 ******************************************************************************/
 376 static int
 377 ntrHeapResize(
 378   NtrHeap *heap)
 379 {
 380   int oldlength = heap->size;
 381   int newlength = 2 * oldlength;
 382   NtrHeapSlot *oldslots = heap->slots;
 383   NtrHeapSlot *newslots = REALLOC(NtrHeapSlot, oldslots, newlength);
 384   if (newslots == NULL) return 0;
 385   heap->size = newlength;
 386   heap->slots = newslots;
 387   assert(Ntr_TestHeap(heap, 0));
 388   return 1;
 389
 390 } /* end of ntrHeapResize */