#ifndef MAXPQ_H
#define MAXPQ_H

#include <list>
using namespace std;
#include <assert.h>

const int DefaultSize = 64;

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
struct element
{
	T data;
	int key;
	element(){};
	element(T d, int k);
	const element& operator=(const element& right);
	void evaluate(T d, int k);
};

template <class T>
element<T>::element(T d, int k)
{
	data = d;
	key = k;
}

template <class T>
const element<T>& element<T>::operator=(const element<T>& right)
{
	data = right.data;
	key = right.key;
	return *this;
}

template <class T>
void element<T>::evaluate(T d, int k)
{
	data = d;
	key = k;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
class maxPQ
{
public:
	virtual void Insert(const element<T>&) = 0;
	virtual element<T>* Delete(element<T>&) = 0;
};

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
template <class T>
class maxHeap : public maxPQ<T>
{
public:
	maxHeap(int sz = DefaultSize);
	void Insert(const element<T>& item);
	element<T>* Delete(element<T>& x);

private:
	element<T>* heap;
	int currentSize;
	int maxSize;
};

template <class T>
maxHeap<T>::maxHeap(int sz = DefaultSize)
{
	maxSize = sz;
	currentSize = 0;
	heap = new element<T>[maxSize+1];
}

template <class T>
void maxHeap<T>::Insert(const element<T>& x)
{
	assert(currentSize<maxSize);
	currentSize++;
	for ( int i=currentSize; (i>1)&&(x.key>heap[i/2].key); i/=2 )
		heap[i] = heap[i/2];
	heap[i] = x;
}

template <class T>
element<T>* maxHeap<T>::Delete(element<T>& x)
{
	assert(currentSize>0);
	x = heap[1];
	element<T> k = heap[currentSize];
	currentSize--;

	int i=1;
	for (int j=2; j<=currentSize; j*=2)
	{
		if( (j<currentSize)&&(heap[j].key<heap[j+1].key) )
			j++;
		if (k.key >= heap[j].key)
			break;
		heap[i] = heap[j];
		i = j;
	}
	heap[i] = k;
	return &x;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
template <class T>
class maxNonsequenceList: maxPQ<T>
{
public:
	maxNonsequenceList(int sz = DefaultSize);
	void Insert(const element<T>& item);
	element<T>* Delete(element<T>& x);

private:
	list<element<T> > nonsequenceList;
	int currentSize;
	int maxSize;
};

template <class T>
maxNonsequenceList<T>::maxNonsequenceList(int sz = DefaultSize)
{
	maxSize = sz;
	currentSize = 0;
}

template <class T>
void maxNonsequenceList<T>::Insert(const element<T>& x)
{
	assert(currentSize<maxSize);
	currentSize++;
	nonsequenceList.insert(nonsequenceList.end(), x);
}

template <class T>
element<T>* maxNonsequenceList<T>::Delete(element<T>& x)
{
	assert(currentSize>0);
	list<element<T> >::iterator m=nonsequenceList.begin();
	for (list<element<T> >::iterator i = nonsequenceList.begin(); i!=nonsequenceList.end(); ++i)
	{
		if ( (*i).key > x.key )
			m = i;
	}
	currentSize--;
	nonsequenceList.erase(m);
	x = *m;
	return &x;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
template <class T>
class maxSequenceList: maxPQ<T>
{
public:
	maxSequenceList(int sz = DefaultSize);
	void Insert(const element<T>& item);
	element<T>* Delete(element<T>& x);

private:
	list<element<T> > sequenceList;
	int currentSize;
	int maxSize;
};

template <class T>
maxSequenceList<T>::maxSequenceList(int sz = DefaultSize)
{
	maxSize = sz;
	currentSize = 0;
}

template <class T>
void maxSequenceList<T>::Insert(const element<T>& x)
{
	assert(currentSize<maxSize);
	currentSize++;
	list<element<T> >::iterator m=sequenceList.begin();
	for (list<element<T> >::iterator i = sequenceList.begin(); i!=sequenceList.end(); ++i)
	{
		if ( (*i).key > x.key )
			m = i;
	}

	sequenceList.insert(m, x);
}

template <class T>
element<T>* maxSequenceList<T>::Delete(element<T>& x)
{
	assert(currentSize>0);
	currentSize--;
	x = *sequenceList.begin();
	sequenceList.erase(sequenceList.begin());
	return &x;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

#endif