/* $Id: heap.c,v 10.1 92/10/06 23:10:28 ca Exp $ */

/** Implementation of a heap.
    Used for events.

    This heap has the type of the sort key compiled into it.  The heap
    could be made more general by taking a pointer to function to call
    in order to compare keys, but I am looking for speed.  However,
    the type of the key can be changed by change the Key_type typedef
    and KEY_LESS_THAN() macro in heap.h

    ath   09-mar-89
*/

#include "sim.h"
#include "heap.h"

/** Heap functions (or macros):
  heap_create()				Return a new heap.
  heap_destroy(h)			Free a heap.
  heap_insert(h, key, elt)		Insert an element in a heap.
  heap_min(h)				Return the minimum elt of heap.
  heap_extract_min(h)			Return and delete the min elt.
  heap_delete(h, elt)			Delete an element of the heap.
  heap_member(h, elt)			Tests for membership of elt in h.
*/


Heap *
heap_create()
{
  Heap *h = (Heap *)sim_calloc(1, sizeof(Heap));
  h->elts = (Heap_elt *)sim_calloc(HEAP_DEFAULT_SIZE, sizeof(Heap_elt));

  h->max_size = HEAP_DEFAULT_SIZE;
  h->size = 0;

  return(h);
}

void
heap_destroy(h)
     Heap *h;
{
  free(h->elts);
  free(h);
}

/* The following functions will be declared static inline in
   heap.h if we are using the GNU C compiler.  */
#ifndef INLINE
void
heap_insert(h, key, elt)
     Heap *h;
     Key_type key;
     caddr_t elt;
{
  int i = h->size, parent;

  /* If we hit the size limit, make it larger.  Note that the
     extra memory is not given back if size drops. */
  if (i == h->max_size)  {
    h->max_size *= 2;
    h->elts = (Heap_elt *)sim_realloc(h->elts, h->max_size * sizeof(Heap_elt));
  }

  /* Place the new element at the next available position
     at the bottom of the tree. */
  h->elts[i].key = key;
  h->elts[i].elt = elt;

  /* Swap the new elt up the tree while it is less than its parent. */
  while (i && KEY_LESS_THAN(key, h->elts[(parent = HEAP_PARENT(i))].key))  {
    HEAP_SWAP(h, i, parent);
    i = parent;
  }

  h->size++;
}

caddr_t
heap_min(h)
     Heap *h;
{
  if (h->size)
    return(h->elts[0].elt);
  else
    return((caddr_t)NULL);
}

caddr_t
heap_extract_min(h)
     Heap *h;
{
  caddr_t elt;
  int i;
  Key_type key;

  if (h->size == 0)
    return((caddr_t)NULL);

  /* Save the current minimum so that I can return it later. */
  elt = h->elts[0].elt;
  
  /* Move the elt from the last position (size - 1) in the heap to the root. */
  i = --h->size;
  h->elts[0] = h->elts[i];
  key = h->elts[0].key;

  /* Swap the new root down the tree 'till its children are both larger
     than it. */
  
  for (i = 0; i < h->size; )  {
    int left = HEAP_LEFT(i);
    int right = HEAP_RIGHT(i);
    int swap_child;

    /* Get the smaller of the two children (taking into account
       that either or both children may not exist). */
    /* Find smaller child of i that is still in the tree.
       (Note that right child exists ==> left child exists.) */
    if (right < h->size) {
      swap_child = KEY_LESS_THAN(h->elts[left].key, h->elts[right].key)
		? left : right;
    }
    else if (left < h->size)  {
      swap_child = left;
    }
    else
      break;			/* Neither child in tree. */

    if (KEY_LESS_THAN(h->elts[swap_child].key, key))  {
      HEAP_SWAP(h, i, swap_child);
      i = swap_child;
    }
    else
      break;
  }

  return(elt);
}
#endif  /* not INLINE */

/* Returns the index of elt in the elts[] array + 1.  External callers
   should just test the return for 0 or non-zero.  Heap_delete()
   uses this routine to find an element in the heap.
   Requires O(n) time. */
heap_member(h, elt)
     Heap *h;
     caddr_t elt;
{
  Heap_elt *he;
  int i;

  for (i = 0, he = h->elts; i < h->size; i++, he++)  {
    if (he->elt == elt)
      return(i + 1);
  }

  return (0);
}


/* Heap_delete().  Returns one for success, zero otherwise.
   Requires O(n) time. */
heap_delete(h, elt)
     Heap *h;
     caddr_t elt;
{
  int i = heap_member(h, elt);

  if (i == 0)
    return (FALSE);

  /* heap_member() return the index of the elt + 1. */
  i--;

  /* To actually remove the element from the tree, first swap it
     to the root (similar to the procedure applied when inserting a
     new element, but no key comparisons--just get it to the root).
     Then call heap_extract_min() to remove it & fix the tree.
     This process is not the most efficient, but I don't particularily
     care about how fast heap_delete() is.  Besides, I've already
     used O(n) time in heap_member(), what's another O(lg n). */

  /* Swap the element to be removed up the tree until it is the root. */
  for ( ; i; i = HEAP_PARENT(i))  {
    HEAP_SWAP(h, i, HEAP_PARENT(i));
  }

  /* Actually remove the element by calling heap_extract_min().
     The key that is now at the root is not necessarily the minimum,
     but heap_extract_min() does not care--it just removes the root. */
  (void) heap_extract_min(h);

  return(TRUE);
}


/* Couple of functions to support iterating through all things on the
   heap without having to know what a heap looks like.
   To be used as follows:
     for (elt = heap_iter_init(h); elt; elt = heap_iter(h))
       Do whatever to the elt.

   You cannot use heap_iter to do anything but inspect the heap.  If
   heap_insert(), heap_extract_min(), or heap_delete() are called
   while iterating through the heap, all bets are off.
*/

caddr_t
heap_iter_init(h)
     Heap *h;
{
  h->iter = 1;
  return(heap_min(h));
}

caddr_t
heap_iter(h)
     Heap *h;
{
  if (h->iter < h->size)
    return(h->elts[h->iter++].elt);
  else
    return((caddr_t)NULL);
}