1/*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
29 */
30/*
31** Author: Eric Veach, July 1994.
32**
33*/
34
35#include <stddef.h>
36#include <assert.h>
37#include "priorityq-heap.h"
38#include "memalloc.h"
39
40#define INIT_SIZE	32
41
42#ifndef TRUE
43#define TRUE 1
44#endif
45#ifndef FALSE
46#define FALSE 0
47#endif
48
49#ifdef FOR_TRITE_TEST_PROGRAM
50#define LEQ(x,y)	(*pq->leq)(x,y)
51#else
52/* Violates modularity, but a little faster */
53#include "geom.h"
54#define LEQ(x,y)	VertLeq((GLUvertex *)x, (GLUvertex *)y)
55#endif
56
57/* really __gl_pqHeapNewPriorityQ */
58PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
59{
60  PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
61  if (pq == NULL) return NULL;
62
63  pq->size = 0;
64  pq->max = INIT_SIZE;
65  pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
66  if (pq->nodes == NULL) {
67     memFree(pq);
68     return NULL;
69  }
70
71  pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
72  if (pq->handles == NULL) {
73     memFree(pq->nodes);
74     memFree(pq);
75     return NULL;
76  }
77
78  pq->initialized = FALSE;
79  pq->freeList = 0;
80  pq->leq = leq;
81
82  pq->nodes[1].handle = 1;	/* so that Minimum() returns NULL */
83  pq->handles[1].key = NULL;
84  return pq;
85}
86
87/* really __gl_pqHeapDeletePriorityQ */
88void pqDeletePriorityQ( PriorityQ *pq )
89{
90  memFree( pq->handles );
91  memFree( pq->nodes );
92  memFree( pq );
93}
94
95
96static void FloatDown( PriorityQ *pq, long curr )
97{
98  PQnode *n = pq->nodes;
99  PQhandleElem *h = pq->handles;
100  PQhandle hCurr, hChild;
101  long child;
102
103  hCurr = n[curr].handle;
104  for( ;; ) {
105    child = curr << 1;
106    if( child < pq->size && LEQ( h[n[child+1].handle].key,
107				 h[n[child].handle].key )) {
108      ++child;
109    }
110
111    assert(child <= pq->max);
112
113    hChild = n[child].handle;
114    if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
115      n[curr].handle = hCurr;
116      h[hCurr].node = curr;
117      break;
118    }
119    n[curr].handle = hChild;
120    h[hChild].node = curr;
121    curr = child;
122  }
123}
124
125
126static void FloatUp( PriorityQ *pq, long curr )
127{
128  PQnode *n = pq->nodes;
129  PQhandleElem *h = pq->handles;
130  PQhandle hCurr, hParent;
131  long parent;
132
133  hCurr = n[curr].handle;
134  for( ;; ) {
135    parent = curr >> 1;
136    hParent = n[parent].handle;
137    if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
138      n[curr].handle = hCurr;
139      h[hCurr].node = curr;
140      break;
141    }
142    n[curr].handle = hParent;
143    h[hParent].node = curr;
144    curr = parent;
145  }
146}
147
148/* really __gl_pqHeapInit */
149void pqInit( PriorityQ *pq )
150{
151  long i;
152
153  /* This method of building a heap is O(n), rather than O(n lg n). */
154
155  for( i = pq->size; i >= 1; --i ) {
156    FloatDown( pq, i );
157  }
158  pq->initialized = TRUE;
159}
160
161/* really __gl_pqHeapInsert */
162/* returns LONG_MAX iff out of memory */
163PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
164{
165  long curr;
166  PQhandle free_handle;
167
168  curr = ++ pq->size;
169  if( (curr*2) > pq->max ) {
170    PQnode *saveNodes= pq->nodes;
171    PQhandleElem *saveHandles= pq->handles;
172
173    /* If the heap overflows, double its size. */
174    pq->max <<= 1;
175    pq->nodes = (PQnode *)memRealloc( pq->nodes,
176				     (size_t)
177				     ((pq->max + 1) * sizeof( pq->nodes[0] )));
178    if (pq->nodes == NULL) {
179       pq->nodes = saveNodes;	/* restore ptr to free upon return */
180       return LONG_MAX;
181    }
182    pq->handles = (PQhandleElem *)memRealloc( pq->handles,
183			                     (size_t)
184			                      ((pq->max + 1) *
185					       sizeof( pq->handles[0] )));
186    if (pq->handles == NULL) {
187       pq->handles = saveHandles; /* restore ptr to free upon return */
188       return LONG_MAX;
189    }
190  }
191
192  if( pq->freeList == 0 ) {
193    free_handle = curr;
194  } else {
195    free_handle = pq->freeList;
196    pq->freeList = pq->handles[free_handle].node;
197  }
198
199  pq->nodes[curr].handle = free_handle;
200  pq->handles[free_handle].node = curr;
201  pq->handles[free_handle].key = keyNew;
202
203  if( pq->initialized ) {
204    FloatUp( pq, curr );
205  }
206  assert(free_handle != LONG_MAX);
207  return free_handle;
208}
209
210/* really __gl_pqHeapExtractMin */
211PQkey pqExtractMin( PriorityQ *pq )
212{
213  PQnode *n = pq->nodes;
214  PQhandleElem *h = pq->handles;
215  PQhandle hMin = n[1].handle;
216  PQkey min = h[hMin].key;
217
218  if( pq->size > 0 ) {
219    n[1].handle = n[pq->size].handle;
220    h[n[1].handle].node = 1;
221
222    h[hMin].key = NULL;
223    h[hMin].node = pq->freeList;
224    pq->freeList = hMin;
225
226    if( -- pq->size > 0 ) {
227      FloatDown( pq, 1 );
228    }
229  }
230  return min;
231}
232
233/* really __gl_pqHeapDelete */
234void pqDelete( PriorityQ *pq, PQhandle hCurr )
235{
236  PQnode *n = pq->nodes;
237  PQhandleElem *h = pq->handles;
238  long curr;
239
240  assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
241
242  curr = h[hCurr].node;
243  n[curr].handle = n[pq->size].handle;
244  h[n[curr].handle].node = curr;
245
246  if( curr <= -- pq->size ) {
247    if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
248      FloatDown( pq, curr );
249    } else {
250      FloatUp( pq, curr );
251    }
252  }
253  h[hCurr].key = NULL;
254  h[hCurr].node = pq->freeList;
255  pq->freeList = hCurr;
256}
257