/* ==========================================================================
* ÀÛ ¼º ÀÚ : À̼ø±Ô
* ÀÛ ¼º ÀÏ : 2007.10.08
* ³»    ¿ë : ¿ì¼±¼øÀ§ Å¥
* ÁÖÀÇ»çÇ× : 
*===========================================================================*/
#pragma once

#include "Functor.h"

/// ¿ì¼±¼øÀ§ Å¥
/// ÀÌÁø Æ®¸®¸¦ ÀÌ¿ëÇÏ¿© Á¦°øµÈ Á¤·Ä ±âÁØ¿¡ µû¶ó¼­ ¿ø¼Ò¸¦ ÀÚµ¿À¸·Î Á¤·ÄÇÑ´Ù.
/// Çѹø ´Ã¾î³­ ¿ë·®Àº ÁÙ¾îµéÁö ¾Ê´Â´Ù.
template <class T, class COMPARE = tBinaryLess<T> >
class tPriorityQueue
{
	/*
	explicit tPriorityQueue( unsigned int capacity );
	~tPriorityQueue();

	/// ¸ðµç ¿ø¼Ò¸¦ Á¦°Å
	void Clear();

	/// ¿ë·®À» ¼³Á¤
	void Reserve( unsigned int capacity );

	/// ¿ø¼Ò¸¦ Ãß°¡
	/// ¿ë·®À» ³Ñ¾î¼­¸é false¸¦ ¸®ÅÏÇÑ´Ù.
	bool Push( T val );

	/// ù¹ø° ¿ø¼Ò¸¦ Á¦°Å
	/// ¿ø¼Ò°¡ Çϳªµµ ¾ø´Â °æ¿ì false¸¦ ¸®ÅÏÇÑ´Ù.
	bool PopFront();

	/// ù¹ø° ¿ø¼Ò¸¦ ¸®ÅÏ
	T Front();
	T Front() const;

	/// ¿ø¼Ò ¼ö¸¦ ¸®ÅÏ
	unsigned int GetCount() const;

	/// ¿ë·®À» ¸®ÅÏ
	unsigned int GetCapacity() const;
	*/

protected:
	typedef tPriorityQueue<T, COMPARE> cSelf;

protected:
	/// ºñ±³ ÇÔ¼öÀÚ
	COMPARE mCompare;

	/// ¹è¿­
	T* mHead;

	/// ¿ë·®
	unsigned int mCapacity;

	/// ¿ø¼Ò ¼ö
	unsigned int mCount;

protected:
	void Reserve( unsigned int capacity )
	{
		if( capacity <= mCapacity )
			return;

		/// ¹è¿­À» »ý¼º
		T* newHead = new T[capacity];
		assert( newHead );

		/// ÀÌÀü ¹è¿­À» º¹»ç
		for( unsigned int i = 0; i < mCount; ++i )
			newHead[i] = mHead[i];

		delete[] mHead;
		mHead = newHead;
		mCapacity = capacity;
	}

	void WalkUp( unsigned int index )
	{
		unsigned int parent = index / 2;
		unsigned int child = index;

		T temp = mHead[child];

		while( parent > 0 )
		{
			if( mCompare( temp, mHead[parent] ) )
			{
				mHead[child] = mHead[parent];
				child = parent;
				parent /= 2;
			}
			else
				break;
		}

		mHead[child] = temp;
	}

	void WalkDown( unsigned int index )
	{
		unsigned int parent = index;
		unsigned int child = index * 2;

		T temp = mHead[parent];

		while( child < mCount )
		{
			if( child < mCount - 1 )
			{
				if( mCompare( mHead[child], mHead[child + 1] ) == false )
				{
					child++;
				}
			}
			if( mCompare( temp, mHead[child] ) == false )
			{
				mHead[parent] = mHead[child];
				parent = child;
				child *= 2;
			}
			else
				break;
		}

		mHead[parent] = temp;
	}

public:
	explicit tPriorityQueue( unsigned int capacity )
		: mHead( 0 )
		, mCapacity( 0 )
		, mCount( 0 )
	{
		assert( capacity );

		Reserve( capacity + 1 );
	}

	~tPriorityQueue()
	{
		delete [] mHead;
	}

	void Clear()
	{
		mCount = 0;
	}

	bool Push( T value )
	{
		if( mCount + 1 >= mCapacity )
		{
			return false;
		}

		++mCount;
		mHead[mCount] = value;
		WalkUp( mCount );
		return true;
	}

	void PopFront()
	{
		if( mCount )
		{
			mHead[1] = mHead[mCount];
			WalkDown( 1 );
			--mCount;
		}
	}

	T Front()
	{
		return mHead[1];
	}

	T Front() const
	{
		return mHead[1];
	}

	unsigned int GetCount() const
	{
		return mCount;
	}

	unsigned int GetCapacity() const
	{
		return mCapacity;
	}
};