/*                                                                     */
/* $$$$$$$$$$$$$$$$$$$$$$$$ Dr. Peter Wang P.100 of DSA $$$$$$$$$$$$$$ */
/* $$    A modulein C language with top-down design                 $$ */
/* $$    CMP507 Data Structure and Algorithm in C     Spring, 98    $$ */
/* $$    Class note 5 : Data Abstruction                            $$ */
/* $$    This is an example of priority queue by using link list    $$ */
/* $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ */
/*                                                                     */
#include 
/* ------------- PQtypes.h: data type declaration ---------------------*/
#define MAXCOUNT 10
typedef int PQItem;
typedef struct PQNodeTag {
		PQItem NodeItem;
		struct PQNodeTag *Link;
	} PQListNode;
typedef struct PQQueueTag {
	       	int Count;
       		PQListNode *ItemList;
       } PriorityQueue;
typedef PQItem SortingArray[MAXCOUNT];
SortingArray A;
/* ------- PQInterface.h: function prototyping----------------------- */
void Initialize(PriorityQueue *);
int Empty(PriorityQueue *);
int Full(PriorityQueue *);
void Insert(PQItem, PriorityQueue *);
PQItem Remove(PriorityQueue *);
void PriorityQueueSort(SortingArray);
/* ------------ define functions used in this project ----------------*/

/* ----------- Initialize --------------- */
void Initialize(PriorityQueue *PQ)
{
	PQ -> Count =0;
	PQ -> ItemList = NULL;
}

/* ----------- Empty --------------------*/
int Empty(PriorityQueue *PQ)
{
	return( PQ -> Count == 0);
}

/*  ---------------- Full --------------- */
int Full(PriorityQueue *PQ)
{
	return(PQ->Count == MAXCOUNT);
}

/* ----------------- SortedInsert   --------------- */
PQListNode *SortedInsert(PQItem Item, PQListNode *P)
{
	PQListNode *N;
	if(P==NULL || Item >= P->NodeItem) {
		N = (PQListNode *) malloc(sizeof(PQListNode));
		N -> NodeItem = Item;
		N -> Link = P;
		return(N);
       }
       else {
		P->Link = SortedInsert(Item, P->Link);
		return(P);
      }
}

/* --------------- Insert --------------- */
void Insert(PQItem Item, PriorityQueue *PQ)
{
	if(!Full(PQ)) {
		PQ->Count = PQ->Count + 1;
		PQ->ItemList = SortedInsert(Item, PQ->ItemList);
	}
}

/* ---------- Remove -----------------*/
PQItem Remove(PriorityQueue *PQ)
{
	PQItem temp;
	if(!Empty(PQ)) {
		temp = PQ->ItemList->NodeItem;
		PQ->ItemList=PQ->ItemList->Link;
		PQ->Count = PQ->Count - 1;
		return(temp);
	}
}

/* --------------------- PriorityQueueSort ---------- */
void PriorityQueueSort(SortingArray A)
{
int i;
PriorityQueue PQ;
Initialize(&PQ);
	for(i=0; i=0; i=i-1) A[i] = Remove(&PQ);
}

/* ------------------- main ---------------------- */
void main(void)
{
	int i;
	SortingArray A;
	for(i=0; i<10; i++) {
		A[i] = (3*i-13) * (3*i-13);
		printf("%d, ",A[i]);
	}
	printf("\n");
	PriorityQueueSort(A);
	for(i=0; i<10; i++) {
	printf("%d, ", A[i]);
	}
	printf("\n");
}