40 if (queue->
type == 1) {
59 for (i=0; i<maxnodes; i++)
85 if (queue->
type == 1) {
107 if (queue->
type == 1) {
145 if (queue->
type == 1) {
150 newnode = queue->
nodes + node;
154 newnode->
prev = NULL;
155 if (newnode->
next != NULL)
157 queue->
buckets[gain] = newnode;
168 ASSERT(locator[node] == -1);
173 if (heap[j].key < gain) {
175 locator[heap[i].
val] = i;
199 int i, j, newgain, oldgain;
204 if (queue->
type == 1) {
210 newnode = queue->
nodes+node;
213 if (newnode->
prev != NULL)
216 buckets[gain] = newnode->
next;
217 if (newnode->
next != NULL)
220 if (buckets[gain] == NULL && gain == queue->
maxgain) {
231 ASSERT(locator[node] != -1);
232 ASSERT(heap[locator[node]].val == node);
242 oldgain = heap[i].
key;
244 if (oldgain < newgain) {
247 if (heap[j].key < newgain) {
249 locator[heap[i].
val] = i;
257 while ((j=2*i+1) < queue->
nnodes) {
258 if (heap[j].key > newgain) {
262 locator[heap[i].
val] = i;
265 else if (j+1 < queue->
nnodes && heap[j+1].
key > newgain) {
268 locator[heap[i].
val] = i;
276 heap[i].
key = newgain;
300 if (oldgain == newgain)
303 if (queue->
type == 1) {
312 ASSERT(locator[node] != -1);
313 ASSERT(heap[locator[node]].val == node);
314 ASSERT(heap[locator[node]].key == oldgain);
319 if (oldgain < newgain) {
322 if (heap[j].key < newgain) {
324 locator[heap[i].
val] = i;
332 while ((j=2*i+1) < queue->
nnodes) {
333 if (heap[j].key > newgain) {
337 locator[heap[i].
val] = i;
340 else if (j+1 < queue->
nnodes && heap[j+1].
key > newgain) {
343 locator[heap[i].
val] = i;
351 heap[i].
key = newgain;
374 if (oldgain == newgain)
377 if (queue->
type == 1) {
383 newnode = queue->
nodes+node;
386 if (newnode->
prev != NULL)
389 buckets[oldgain] = newnode->
next;
390 if (newnode->
next != NULL)
394 newnode->
next = buckets[newgain];
395 newnode->
prev = NULL;
396 if (newnode->
next != NULL)
398 buckets[newgain] = newnode;
407 ASSERT(locator[node] != -1);
408 ASSERT(heap[locator[node]].val == node);
409 ASSERT(heap[locator[node]].key == oldgain);
417 if (heap[j].key < newgain) {
419 locator[heap[i].
val] = i;
426 heap[i].
key = newgain;
442 int vtx, i, j, gain, node;
452 if (queue->
type == 1) {
455 if (tptr->
next != NULL) {
475 if ((i = queue->
nnodes) > 0) {
479 while ((j=2*i+1) < queue->
nnodes) {
480 if (heap[j].key > gain) {
484 locator[heap[i].
val] = i;
487 else if (j+1 < queue->
nnodes && heap[j+1].
key > gain) {
490 locator[heap[i].
val] = i;
518 if (queue->
type == 1)
537 if (queue->
type == 1)
564 ASSERT(locator[heap[0].val] == 0);
565 for (i=1; i<nnodes; i++) {
566 ASSERTP(locator[heap[i].val] == i, (
"%d %d %d %d\n", nnodes, i, heap[i].val, locator[heap[i].val]));
567 ASSERTP(heap[i].key <= heap[(i-1)/2].key, (
"%d %d %d %d %d\n", i, (i-1)/2, nnodes, heap[i].key, heap[(i-1)/2].key));
569 for (i=1; i<nnodes; i++)
570 ASSERT(heap[i].key <= heap[0].key);
572 for (j=i=0; i<queue->
maxnodes; i++) {
573 if (locator[i] != -1)
576 ASSERTP(j == nnodes, (
"%d %d\n", j, nnodes));
int PQueueGetSize(PQueueType *queue)
struct ListNodeType * prev
void GKfree(void **ptr1,...)
#define ASSERTP(expr, msg)
struct ListNodeType ListNodeType
int PQueueGetKey(PQueueType *queue)
struct ListNodeType * next