/* 
  * Copyright 1997, Regents of the University of Minnesota 
  * 
  * pqueue.c 
  * 
  * This file contains functions for manipulating the bucket list 
  * representation of the gains associated with each vertex in a graph. 
  * These functions are used by the refinement algorithms 
  * 
  * Started 9/2/94 
  * George 
  * 
  * $Id: pqueue.c,v 1.1 1998/11/27 17:59:28 karypis Exp $ 
  * 
  */ 

 #include <metis.h> 


 /************************************************************************* 
 * This function initializes the data structures of the priority queue 
 **************************************************************************/ 
 void PQueueInit(CtrlType *ctrl, PQueueType *queue, long maxnodes, long maxgain) 
 { 
   long i, j, ncore; 

   queue->nnodes = 0; 
   queue->maxnodes = maxnodes; 

   queue->buckets = NULL; 
   queue->nodes = NULL; 
   queue->heap = NULL; 
   queue->locator = NULL; 

   if (maxgain > PLUS_GAINSPAN || maxnodes < 500) 
     queue->type = 2; 
   else 
     queue->type = 1; 

   if (queue->type == 1) { 
     queue->pgainspan = amin(PLUS_GAINSPAN, maxgain); 
     queue->ngainspan = amin(NEG_GAINSPAN, maxgain); 

     j = queue->ngainspan+queue->pgainspan+1; 

     ncore = 2 + (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes + (sizeof(ListNodeType *)/sizeof(idxtype))*j; 

     if (WspaceAvail(ctrl) > ncore) { 
       queue->nodes = (ListNodeType *)idxwspacemalloc(ctrl, (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes); 
       queue->buckets = (ListNodeType **)idxwspacemalloc(ctrl, (sizeof(ListNodeType *)/sizeof(idxtype))*j); 
       queue->mustfree = 0; 
     } 
     else { /* Not enough memory in the wspace, allocate it */ 
       queue->nodes = (ListNodeType *)idxmalloc((sizeof(ListNodeType)/sizeof(idxtype))*maxnodes, "PQueueInit: queue->nodes"); 
       queue->buckets = (ListNodeType **)idxmalloc((sizeof(ListNodeType *)/sizeof(idxtype))*j, "PQueueInit: queue->buckets"); 
       queue->mustfree = 1; 
     } 

     for (i=0; i<maxnodes; i++)  
       queue->nodes[i].id = i; 

     for (i=0; i<j; i++) 
       queue->buckets[i] = NULL; 

     queue->buckets += queue->ngainspan;  /* Advance buckets by the ngainspan proper indexing */ 
     queue->maxgain = -queue->ngainspan; 
   } 
   else { 
     queue->heap = (KeyValueType *)idxwspacemalloc(ctrl, (sizeof(KeyValueType)/sizeof(idxtype))*maxnodes); 
     queue->locator = idxwspacemalloc(ctrl, maxnodes); 
     idxset(maxnodes, -1, queue->locator); 
   } 

 } 


 /************************************************************************* 
 * This function resets the buckets 
 **************************************************************************/ 
 void PQueueReset(PQueueType *queue) 
 { 
   long i, j; 
   queue->nnodes = 0; 

   if (queue->type == 1) { 
     queue->maxgain = -queue->ngainspan; 

     j = queue->ngainspan+queue->pgainspan+1; 
     queue->buckets -= queue->ngainspan;   
     for (i=0; i<j; i++) 
       queue->buckets[i] = NULL; 
     queue->buckets += queue->ngainspan;   
   } 
   else { 
     idxset(queue->maxnodes, -1, queue->locator); 
   } 

 } 


 /************************************************************************* 
 * This function frees the buckets 
 **************************************************************************/ 
 void PQueueFree(CtrlType *ctrl, PQueueType *queue) 
 { 

   if (queue->type == 1) { 
     if (queue->mustfree) { 
       queue->buckets -= queue->ngainspan;   
       GKfree(&queue->nodes, &queue->buckets, LTERM); 
     }  
     else { 
       idxwspacefree(ctrl, sizeof(ListNodeType *)*(queue->ngainspan+queue->pgainspan+1)/sizeof(idxtype)); 
       idxwspacefree(ctrl, sizeof(ListNodeType)*queue->maxnodes/sizeof(idxtype)); 
     } 
   } 
   else { 
     idxwspacefree(ctrl, sizeof(KeyValueType)*queue->maxnodes/sizeof(idxtype)); 
     idxwspacefree(ctrl, queue->maxnodes); 
   } 

   queue->maxnodes = 0; 
 } 


 /************************************************************************* 
 * This function returns the number of nodes in the queue 
 **************************************************************************/ 
 long PQueueGetSize(PQueueType *queue) 
 { 
   return queue->nnodes; 
 } 


 /************************************************************************* 
 * This function adds a node of certain gain into a partition 
 **************************************************************************/ 
 long PQueueInsert(PQueueType *queue, long node, long gain) 
 { 
   long 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; 
 } 


 /************************************************************************* 
 * This function deletes a node from a partition and reinserts it with 
 * an updated gain 
 **************************************************************************/ 
 long PQueueDelete(PQueueType *queue, long node, long gain) 
 { 
   long i, j, newgain, oldgain; 
   idxtype *locator; 
   ListNodeType *newnode, **buckets; 
   KeyValueType *heap; 

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

     buckets = queue->buckets; 
     queue->nnodes--; 
     newnode = queue->nodes+node; 

     /* Remove newnode from the doubly-linked list */ 
     if (newnode->prev != NULL) 
       newnode->prev->next = newnode->next; 
     else 
       buckets[gain] = newnode->next; 
     if (newnode->next != NULL) 
       newnode->next->prev = newnode->prev; 

     if (buckets[gain] == NULL && gain == queue->maxgain) { 
       if (queue->nnodes == 0)  
         queue->maxgain = -queue->ngainspan; 
       else  
         for (; buckets[queue->maxgain]==NULL; queue->maxgain--); 
     } 
   } 
   else { /* Heap Priority Queue */ 
     heap = queue->heap; 
     locator = queue->locator; 

     ASSERT(locator[node] != -1); 
     ASSERT(heap[locator[node]].val == node); 

     ASSERT(CheckHeap(queue)); 

     i = locator[node]; 
     locator[node] = -1; 

     if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) { 
       node = heap[queue->nnodes].val; 
       newgain = heap[queue->nnodes].key; 
       oldgain = heap[i].key; 

       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; 
         } 
       } 

       heap[i].key = newgain; 
       heap[i].val = node; 
       locator[node] = i; 
     } 

     ASSERT(CheckHeap(queue)); 
   } 

   return 0; 
 } 



 /************************************************************************* 
 * This function deletes a node from a partition and reinserts it with 
 * an updated gain 
 **************************************************************************/ 
 long PQueueUpdate(PQueueType *queue, long node, long oldgain, long newgain) 
 { 
   long 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; 
       } 
     } 

     heap[i].key = newgain; 
     heap[i].val = node; 
     locator[node] = i; 

     ASSERT(CheckHeap(queue)); 
   } 

   return 0; 
 } 



 /************************************************************************* 
 * This function deletes a node from a partition and reinserts it with 
 * an updated gain 
 **************************************************************************/ 
 void PQueueUpdateUp(PQueueType *queue, long node, long oldgain, long newgain) 
 { 
   long i, j; 
   idxtype *locator; 
   ListNodeType *newnode, **buckets; 
   KeyValueType *heap; 

   if (oldgain == newgain)  
     return; 

   if (queue->type == 1) { 
     ASSERT(oldgain >= -queue->ngainspan && oldgain <= queue->pgainspan); 
     ASSERT(newgain >= -queue->ngainspan && newgain <= queue->pgainspan); 
     ASSERT(queue->nnodes > 0); 

     buckets = queue->buckets; 
     newnode = queue->nodes+node; 

     /* First delete the node */ 
     if (newnode->prev != NULL) 
       newnode->prev->next = newnode->next; 
     else 
       buckets[oldgain] = newnode->next; 
     if (newnode->next != NULL) 
       newnode->next->prev = newnode->prev; 

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

     if (queue->maxgain < newgain) 
       queue->maxgain = 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)); 


     /* Here we are just filtering up since the newgain is greater than the oldgain */ 
     i = locator[node]; 
     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; 
     } 

     heap[i].key = newgain; 
     heap[i].val = node; 
     locator[node] = i; 

     ASSERT(CheckHeap(queue)); 
   } 

 } 


 /************************************************************************* 
 * This function returns the vertex with the largest gain from a partition 
 * and removes the node from the bucket list 
 **************************************************************************/ 
 long PQueueGetMax(PQueueType *queue) 
 { 
   long vtx, i, j, gain, node; 
   idxtype *locator; 
   ListNodeType *tptr; 
   KeyValueType *heap; 

   if (queue->nnodes == 0) 
     return -1; 

   queue->nnodes--; 

   if (queue->type == 1) { 
     tptr = queue->buckets[queue->maxgain]; 
     queue->buckets[queue->maxgain] = tptr->next; 
     if (tptr->next != NULL) { 
       tptr->next->prev = NULL; 
     } 
     else { 
       if (queue->nnodes == 0) { 
         queue->maxgain = -queue->ngainspan; 
       } 
       else  
         for (; queue->buckets[queue->maxgain]==NULL; queue->maxgain--); 
     } 

     return tptr->id; 
   } 
   else { 
     heap = queue->heap; 
     locator = queue->locator; 

     vtx = heap[0].val; 
     locator[vtx] = -1; 

     if ((i = queue->nnodes) > 0) { 
       gain = heap[i].key; 
       node = heap[i].val; 
       i = 0; 
       while ((j=2*i+1) < queue->nnodes) { 
         if (heap[j].key > gain) { 
           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 > gain) { 
           j = j+1; 
           heap[i] = heap[j]; 
           locator[heap[i].val] = i; 
           i = j; 
         } 
         else 
           break; 
       } 

       heap[i].key = gain; 
       heap[i].val = node; 
       locator[node] = i; 
     } 

     ASSERT(CheckHeap(queue)); 
     return vtx; 
   } 
 } 
        

 /************************************************************************* 
 * This function returns the vertex with the largest gain from a partition 
 **************************************************************************/ 
 long PQueueSeeMax(PQueueType *queue) 
 { 
   long vtx; 

   if (queue->nnodes == 0) 
     return -1; 

   if (queue->type == 1)  
     vtx = queue->buckets[queue->maxgain]->id; 
   else 
     vtx = queue->heap[0].val; 

   return vtx; 
 } 
        

 /************************************************************************* 
 * This function returns the vertex with the largest gain from a partition 
 **************************************************************************/ 
 long PQueueGetKey(PQueueType *queue) 
 { 
   long key; 

   if (queue->nnodes == 0) 
     return -1; 

   if (queue->type == 1)  
     key = queue->maxgain; 
   else 
     key = queue->heap[0].key; 

   return key; 
 } 
        



 /************************************************************************* 
 * This functions checks the consistency of the heap 
 **************************************************************************/ 
 long CheckHeap(PQueueType *queue) 
 { 
   long i, j, nnodes; 
   idxtype *locator; 
   KeyValueType *heap; 

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

   if (nnodes == 0) 
     return 1; 

   ASSERT(locator[heap[0].val] == 0); 
   for (i=1; i<nnodes; i++) { 
     ASSERTP(locator[heap[i].val] == i, ("%ld %ld %ld %ld\n", nnodes, i, heap[i].val, locator[heap[i].val]));  
     ASSERTP(heap[i].key <= heap[(i-1)/2].key, ("%ld %ld %ld %ld %ld\n", i, (i-1)/2, nnodes, heap[i].key, heap[(i-1)/2].key)); 
   } 
   for (i=1; i<nnodes; i++) 
     ASSERT(heap[i].key <= heap[0].key); 

   for (j=i=0; i<queue->maxnodes; i++) { 
     if (locator[i] != -1) 
       j++; 
   } 
   ASSERTP(j == nnodes, ("%ld %ld\n", j, nnodes)); 

   return 1; 
 }