/** Header file for a heap. */

/* $Id: heap.h,v 10.1 92/10/06 23:08:38 ca Exp $ */

#include <sys/types.h>

/* Change these two lines to redefine the key used in the heap. */
typedef unsigned Key_type;
#define KEY_LESS_THAN(k1, k2) ((k1) < (k2))

typedef struct _heap_elt {
	Key_type key;
	caddr_t elt;
} Heap_elt;

#define HEAP_DEFAULT_SIZE 32
typedef struct _heap {
	int size;		/* Number of elements in the heap */
	int max_size;		/* Max number that can be stored
				   before the array must be resized. */
	Heap_elt *elts;
	int iter;		/* Index to iterate over heap elements. */
} Heap;

#define HEAP_PARENT(elt_index) (((elt_index) - 1) / 2)
#define HEAP_LEFT(elt_index)   ((elt_index) * 2 + 1)
#define HEAP_RIGHT(elt_index)  (((elt_index) + 1) * 2)

/* Swap elts[i] with elts[j] */
#define HEAP_SWAP(h, i, j) \
	{ \
	  Heap_elt he; \
	  he = h->elts[(i)]; \
	  h->elts[(i)] = h->elts[(j)]; \
	  h->elts[(j)] = he; \
	}


/* Put functions inline for speed with GCC. */
#ifdef INLINE
static 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++;
}

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

static inline 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);
}

#else   /* not INLINE */
void heap_insert();
caddr_t heap_min(), heap_extract_min();
#endif  /* INLINE */

Heap *heap_create();
void heap_destroy();