//-------------------------------------------------------
// Source file provided by Mark Allen Weiss
// website: http://users.cis.fiu.edu/~weiss/dsaa_c2e/files.html
//
// Modified by Quinn Hsu
// Demonstrates how PbO can be used to expose optimization
//		parameters.  In this case, ##ary.
//
// Version 1.0
// Original PriorityQueue indexed from 1
// Modified PriorityQueue to index from 0
// Modified original Binary Heap to D-ary Heap
// Exposed PbO parameters for optimization
//-------------------------------------------------------

#include "fatal.h"
#include <stdlib.h>

// NOTE: It does not make sense to expose
// 		some of the below parameters for PbO.
//		However, they have been kept because the
//		original program makes use of these parameters

##PARAM(int minPQSize=10)
##PARAM(int minData=-32752)
##PARAM(int ary=4)
##PARAM(int maxSize=10000)

struct HeapStruct
{
	int Capacity;
	int Size;
	ElementType *Elements;
};

PriorityQueue
Initialize( int MaxElements )
{
	PriorityQueue H;

	if( MaxElements < ##minPQSize )
		Error( "Priority queue size is too small" );

	H = malloc( sizeof( struct HeapStruct ) );
	if( H ==NULL )
		FatalError( "Out of space!!!" );

	H->Elements = malloc( ( MaxElements + 1 )
							* sizeof( ElementType ) );
	if( H->Elements == NULL )
		FatalError( "Out of space!!!" );
		
	H->Capacity = MaxElements;
	H->Size = 0;
	H->Elements[ 0 ] = ##minData;
	
	return H;
}

void
MakeEmpty( PriorityQueue H )
{
	H->Size = 0;
}


void
Insert( ElementType X, PriorityQueue H )
{
	int i;
	
	if( IsFull( H ) )
	{
		Error( "Priority queue is full" );
		return;
	}
	
	if ( IsEmpty(H) ) {
		H->Elements[0] = X;
		H->Size++;
		return;
	}

	for( i = H->Size; H->Elements[ (i-1)/##ary ] > X; i = (i-1)/##ary ) {
		if (i==0) break;
		H->Elements[ i ] = H->Elements[ (i-1)/##ary ];
	}
	H->Elements[ i ] = X;
	H->Size++;
}


ElementType
DeleteMin( PriorityQueue H )
{
	int i, Child;
	ElementType MinElement, LastElement;
	
	if( IsEmpty( H ) )
	{
		Error( "Priority queue is empty" );
		return ##minData;
	}
	
	MinElement = H->Elements[ 0 ];
	LastElement = H->Elements[ H->Size-1  ];
	
	for( i = 0; (i*##ary)+1 < H->Size; i = Child )
	{
		/* Find smaller child */
		Child = (i*##ary)+1;
		
		if (Child > H->Size) { break; }
		int j;
		int currentSmallestChild;
		currentSmallestChild = Child;
		for (j=1; j<##ary; j++) {
			if (Child+j == H->Size) break;
			if(H->Elements[currentSmallestChild] > H->Elements[Child+j])
				currentSmallestChild = Child+j;
		}
		
		Child = currentSmallestChild;
		
		/* Percolate one level */
		if( LastElement > H->Elements[ Child ] )
			H->Elements[ i ] = H->Elements[ Child ];
		else
			break;
	} // end for
	
	H->Elements[ i ] = LastElement;
	H->Size--;
	return MinElement;
}

ElementType
FindMin( PriorityQueue H )
{
	if( !IsEmpty( H ) )
		return H->Elements[ 0 ];
	Error( "Priority Queue is Empty" );
	return ##minData;
}

int
IsEmpty( PriorityQueue H )
{
	return H->Size == 0;
}

int
IsFull( PriorityQueue H )
{
	return H->Size == H->Capacity;
}

void
Destroy( PriorityQueue H )
{
	free( H->Elements );
	free( H );
}



main( )
{
    PriorityQueue H;
    int i, j;

    H = Initialize( ##maxSize );
    for( i=0, j=##maxSize/2; i<##maxSize; i++, j=( j+71)%##maxSize )
        Insert( j, H );
	
    j = 0;
    for(j=0; j<##maxSize; j++) {
    	if (DeleteMin(H) != j) {
    		printf("Error in DeleteMin, %d\n",j);
    	}
    }
    
    printf( "Done...\n" );
    return 0;
}