Function PQueueUpdate

OTHER/METIS/pqueue.c:294–360

* This function deletes a node from a partition and reinserts it with * an updated gain **************************************************************************/

* an updated gain
**************************************************************************/
int PQueueUpdate(PQueueType *queue, int node, int oldgain, int newgain)
{
  int i, j;
  idxtype *locator;
  ListNodeType *newnode;
  KeyValueType *heap;

  if (oldgain == newgain) 
    return 0;

  if (queue->type == 1) {
    /* First delete the node and then insert it */
    PQueueDelete(queue, node, oldgain);
    return PQueueInsert(queue, node, newgain);
  }
  else { /* Heap Priority Queue */
    heap = queue->heap;
    locator = queue->locator;

    ASSERT(locator[node] != -1);
    ASSERT(heap[locator[node]].val == node);
    ASSERT(heap[locator[node]].key == oldgain);
    ASSERT(CheckHeap(queue));

    i = locator[node];

    if (oldgain < newgain) { /* Filter-up */
      while (i > 0) {
        j = (i-1)>>1;
        if (heap[j].key < newgain) {
          heap[i] = heap[j];
          locator[heap[i].val] = i;
          i = j;
        }
        else 
          break;
      }
    }
    else { /* Filter down */
      while ((j=2*i+1) < queue->nnodes) {
        if (heap[j].key > newgain) {
          if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
            j = j+1;
          heap[i] = heap[j];
          locator[heap[i].val] = i;
          i = j;
        }
        else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
          j = j+1;
          heap[i] = heap[j];
          locator[heap[i].val] = i;
          i = j;
        }
        else
          break;
      }
    }