Function PQueueInsert

OTHER/METIS/pqueue.c:139–191

* This function adds a node of certain gain into a partition **************************************************************************/

* This function adds a node of certain gain into a partition
**************************************************************************/
int PQueueInsert(PQueueType *queue, int node, int gain)
{
  int i, j, k;
  idxtype *locator;
  ListNodeType *newnode;
  KeyValueType *heap;

  if (queue->type == 1) {
    ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);

    /* Allocate and add the node */
    queue->nnodes++;
    newnode = queue->nodes + node;

    /* Attach this node in the doubly-linked list */
    newnode->next = queue->buckets[gain];
    newnode->prev = NULL;
    if (newnode->next != NULL)
      newnode->next->prev = newnode;
    queue->buckets[gain] = newnode;

    if (queue->maxgain < gain)
      queue->maxgain = gain;
  }
  else {
    ASSERT(CheckHeap(queue));

    heap = queue->heap;
    locator = queue->locator;

    ASSERT(locator[node] == -1);

    i = queue->nnodes++;
    while (i > 0) {
      j = (i-1)/2;
      if (heap[j].key < gain) {
        heap[i] = heap[j];
        locator[heap[i].val] = i;
        i = j;
      }
      else 
        break;
    }
    ASSERT(i >= 0);
    heap[i].key = gain;
    heap[i].val = node;
    locator[node] = i;

    ASSERT(CheckHeap(queue));
  }

  return 0;
}


/*************************************************************************