/*program priority_q_demo

   The program first arranges the input data into a heap with the lowest
   value as the root. Several insertions and deletions are made (deletion
   is always of the lowest value data item) with the heap property restored
   after each operation. Finally, the array (which contains the heap) is
   printed.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

      LIST ADT (an ARRAY implementataion)

NOTES:-    1. The array size is determined by maxln, and is set for 100
              elements.

           2. An empty list has the position variable L.last set to 0.*/

#include <stdio.h>
#include <stdlib.h>
#define maxln 100

typedef int position;
typedef int infotype;
typedef struct {
  infotype contents[maxln];
  position last;
} list;
typedef infotype processtype;
typedef list PRIORITYQUEUE;

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

main()
{
  void ERROR(void);
  position FIRST(list *);
  position ENDLIS(list *);
  position NEXT(position, list *);
  infotype RETRIEVE(position, list *);
  void MAKENULL(list *);
  void INSERTL(infotype, position, list *);
  void print_out(list *);
  void MAKEHEAP(PRIORITYQUEUE *);
  void buildheap(int, PRIORITYQUEUE *);
  void INSERT(processtype, PRIORITYQUEUE *);
  void DELETEMIN(processtype *, PRIORITYQUEUE *);

  list L;
  processtype dummy;
  position p;
  infotype v;
  FILE *fp;

  MAKENULL(&L);
  if((fp = fopen("INDATP", "r"))==NULL) ERROR();
  p= FIRST(&L);
  do {
    fscanf(fp,"%d",&v);
    INSERTL (v, p, &L);
    p= NEXT(p, &L);
  } while (!feof(fp));
  fclose(fp);
  print_out (&L);
  MAKEHEAP (&L);
  INSERT (2,&L);
  DELETEMIN (&dummy, &L);
  INSERT (12, &L);
  INSERT (9, &L);
  DELETEMIN (&dummy, &L);
  DELETEMIN (&dummy, &L);
  DELETEMIN (&dummy, &L);
  INSERT (17, &L);
  INSERT (4, &L);
  print_out (&L);
  return 0;
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

void ERROR (void)
{
  exit (1);
}
position FIRST (list *L)
{
  return 1;
}
position ENDLIS (list *L)
{
  return L->last + 1;
}
position NEXT (position p, list *L)
{
  if ((p > L->last) || (p < 1)) ERROR();
  else return ++p;
}
infotype RETRIEVE (position p, list *L)
{
  if ((p > L->last) || (p < 1)) ERROR();
  else return L->contents[p];
}
void MAKENULL (list *L)
{
  L->last= 0;
}
void INSERTL (infotype x, position p, list *L)
{
  position q;

  if (L->last >= maxln) ERROR();
  else if ((p > L->last+1) || (p < 1)) ERROR();
  else {
    for (q=L->last; q>=p; q--)  L->contents[q+1]= L->contents[q];
    L->last++;
    L->contents[p]= x;
  }
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

            PRIORITY QUEUE ADT    -   CODE*/

void DELETEMIN (processtype *element, PRIORITYQUEUE *A)
{
  int i, j, done;
  processtype temp;

  if (A->last== 0) ERROR();
  else {
    done= 0;
    *element= A->contents[1];
    A->contents[1]= A->contents[A->last];
    A->last--;
    i= 1;
    while ((i <= A->last/2) && (!done)) {
      if (2*i == A->last) j= 2*i;
      else {
        if (A->contents[2*i] < A->contents[2*i+1]) j= 2*i;
        else j= 2*i+1;
      }
      if (A->contents[i] > A->contents[j]) {
        temp= A->contents[i];
        A->contents[i]= A->contents[j];
        A->contents[j]= temp;
        i= j;
      }
      else done= 1;
    }
  }
}
void INSERT (processtype x, PRIORITYQUEUE *A)
{
  int i, done;
  processtype temp;

  if (A->last >= maxln) ERROR();
  else {
    A->last++;
    A->contents[A->last]= x;
    i= A->last;
    done= 0;
    while ((i>1) && (!done)) {
      if (A->contents[i] < A->contents[i/2]) {
        temp= A->contents[i];
        A->contents[i]= A->contents[i/2];
        A->contents[i/2]= temp;
        i= i/2;
      }
      else done= 1;
    }
  }
}

void MAKEHEAP (PRIORITYQUEUE *A)
{
  int c;

  for (c=A->last/2; c>0; c--) buildheap(c, A);
}
void buildheap (int i, PRIORITYQUEUE *A)
{
  int j, done;
  processtype temp;

  done= 0;
  while ((i <= A->last/2) && (!done)) {
    if (2*i == A->last) j= 2*i;
    else {
      if (A->contents[2*i] < A->contents[2*i+1]) j= 2*i;
      else j= 2*i+1;
    }
    if (A->contents[i] > A->contents[j]) {
      temp= A->contents[i];
      A->contents[i]= A->contents[j];
      A->contents[j]= temp;
      i= j;
    }
    else done= 1;
  }
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/


void print_out (list *L)
   /*print_out prints list L, after a linefeed. The elements are expected to be
     single digit integers (a field width of 2 is used with no formatting) if
     this is not the case the output will look confused.*/
{
  position p;

  printf("\n");
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    printf("%3d",RETRIEVE(p, L));
    p= NEXT(p, L);
  }
  printf("\n");
}