/*
 * $RCSfile$ $Revision$ $State$
 */
/****************************************************************************
*   File: rtmp_heap.c                                                       *
*                                                                           *
*       Copyright 1993 by Loral Advanced Distributed Simulation, Inc.       *
*                                                                           *
*               Loral Advanced Distributed Simulation, Inc.                 *
*               10 Moulton Street                                           *
*               Cambridge, MA 02238                                         *
*               617-873-1850                                                *
*                                                                           *
*       This software was developed by Loral under U. S. Government contracts*
*       and may be reproduced by or for the U. S. Government pursuant to    *
*       the copyright license under the clause at DFARS 252.227-7013        *
*       (OCT 1988).                                                         *
*                                                                           *
*       Contents: heap utility routines.
*
*            These routines are reference in Cormen, Lieserson, Rivest
*            _Introduction to Algorithms_.  Accordingly, the heap is
*            accessed * from 1 to n, not from 0 to n-1.  However,
*            there is a screwup which is corrected by using a
*            "location" array.  The heap is used to hold vertices
*            which are numbered 0 through n-1.  The "location" array
*            holds the location of the i_th vertex, so if
*            location[i]==j, then heap[j].ver_num==i;
*
*       Created: Tue Nov  9 1993                                            *
*       Author: oded                                                        *
*       Remarks:                                                            *
*                                                                           *
****************************************************************************/


#include "librtmp_local.h"

/*
  utility routine to print out content of heap
*/
void routemap_dump_heap(heap,n)
     heap_element* heap;
     int n;
{
  int i;
  
  for (i=1;i<=n;i++)
    printf("%3.1f,%d ",heap[i].key,heap[i].ver_num);
  printf("\n");
}


/* 
  heapifies the heap starting at heap[i] and also updates location
*/
void routemap_heapify(heap,n,i,location)
     heap_element* heap;
     int n;
     int i;
     int *location;
{
  int l,r,smallest;
  heap_element temp;
  int temp_loc;

  l=2*i;
  r=(2*i)+1;
  if ((l<=n) && (heap[l].key<heap[i].key))
    smallest=l;
  else
    smallest=i;
  if ((r<=n) && (heap[r].key<heap[smallest].key))
    smallest=r;
  if (smallest!=i)
    {
      location[heap[smallest].ver_num]=i;
      location[heap[i].ver_num]=smallest;
      temp = heap[i];
      heap[i]=heap[smallest];
      heap[smallest]=temp;
      routemap_heapify(heap,n,smallest,location);
    }
}
  

/* 
  given n unheapified elements in heap and their locations, this routine
  constructs a heap and its appropriate "location" array.
*/
void routemap_build_heap(heap,n,location)
     heap_element* heap;
     int n;
     int *location;
{
  int i;
  
  for (i=floor_div(n);i>=1;i--)
    routemap_heapify(heap,n,i,location);
}


/*
  removes the top element from the heap.  Updates "location".  Does NOT
  update n (the size of the heap) - that is the responsibility of whomever
  calls this routine.
*/
heap_element routemap_heap_extract_min(heap,n,location)
     heap_element* heap;
     int n;
     int* location;
{
  heap_element minimum;

  minimum=heap[1];
  location[heap[n].ver_num]=1;
  location[heap[1].ver_num]=n;
  heap[1]=heap[n];
  heap[n]=minimum;
  routemap_heapify(heap,n-1,1,location);
  return (minimum);
}


/*
  forces heap[i].key to be k and updates the heap and location appropriately
*/
void routemap_heap_decrease_key(heap,n,i,k,location)
     heap_element* heap;
     int n;
     int i;
     float32 k;
     int *location;
{
  heap_element temp;

  if (heap[i].key>k)
    {
      temp=heap[i];
      while ((i>1) && (heap[floor_div(i)].key>k))
	{
	  location[heap[floor_div(i)].ver_num]=i;
	  heap[i]=heap[floor_div(i)];
	  i=floor_div(i);
	}
      location[temp.ver_num]=i;
      heap[i]=temp;
      heap[i].key=k;
    }
}