/*                                                                     */
/* $$$$$$$$$$$$$$$$$$$$$$$$ Dr. Peter Wang P.105 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 PQItem PQArray[MAXCOUNT];
typedef struct PQQueueTag {
	       	int Count;
       		PQArray ItemArray;
       } PriorityQueue;
typedef PQItem SortingArray[MAXCOUNT];

/* ------- 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;
}

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

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

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

/* ---------- Remove -----------------*/
PQItem Remove(PriorityQueue *PQ)
{
	int i;
	int MaxIndex;
	PQItem MaxItem;
	if(!Empty(PQ)) {
		MaxItem=PQ->ItemArray[0];
		MaxIndex=0;
		for(i=1;iCount;i++) {
			if(PQ->ItemArray[i]>MaxItem) {
				MaxItem=PQ->ItemArray[i];
				MaxIndex=i;
			}
		}
		PQ->Count = PQ->Count - 1;
		PQ->ItemArray[MaxIndex]=PQ->ItemArray[PQ->Count];
		return(MaxItem);
	}
}

/* --------------------- 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");
}