/*!
	SimpleQueueTemplate.h

	Queue テンプレート
	データはCSimpleArrayTemplateに格納される
	追加・取得は基本的に高速だが、キューサイズ増大には非常に時間がかかるため、あらかじめサイズを設定して利用する。
*/
#pragma once
#include "SimpleArrayTemplate.h"


/*!
	Queue テンプレート
*/
template< class _TYPE, class _ARG_TYPE = _TYPE&, class _CONSTRUCTOR = CSimpleArrayTemplateItmeConstructor<_TYPE>, int INIT_ALLOC = 5>
class CSimpleQueueTemplate
{
protected:
	//	子クラスで使用できるように
	typedef	_TYPE			TYPE;
	typedef	_ARG_TYPE		ARG_TYPE;
	typedef	_CONSTRUCTOR	CONSTRUCTOR;

public:
	CSimpleQueueTemplate(void)
	{
		InitInternal();
		SetMinQueueSize(INIT_ALLOC);
	}

	virtual ~CSimpleQueueTemplate(void)
	{
		Close();
	}

	//////////////////////////////////////////////////////////////
	//	操作、情報
	//////////////////////////////////////////////////////////////
	/*!
		格納サイズ設定
	*/
	virtual void SetMinQueueSize(int size)
	{
		int oldSize = m_array.GetCount();
		if(oldSize < size)
		{
			//	増大
			m_array.SetSize(size);

			//	移動
			Relocation(oldSize, size);
		}
	}

	/*!
		格納中のサイズ取得
	*/
	virtual int GetCount()
	{
		return m_usingSize;
	}

	/*!
		全クリア
	*/
	virtual void RemoveAll()
	{
		Close();
	}

	//////////////////////////////////////////////////////////////
	//	追加、取得
	//////////////////////////////////////////////////////////////
	/*!
		追加
	*/
	virtual void AddTail(ARG_TYPE item)
	{
		Grow(1);

		//	保存
		m_array[m_writePoint] = item;
		m_usingSize++;
		ASSERT(m_usingSize <= m_array.GetCount());

		//	書き込みポインタ移動
		m_writePoint++;
		if(m_writePoint == m_array.GetCount())
			m_writePoint = 0; 

		ASSERT(	(m_writePoint == m_readPoint && (m_usingSize == 0 || m_usingSize ==  m_array.GetCount())) ||
				(m_writePoint > m_readPoint && m_writePoint - m_readPoint == m_usingSize) || 
				(m_writePoint < m_readPoint && m_array.GetCount() - (m_readPoint - m_writePoint)  == m_usingSize));
	}

	/*!
		取得
	*/
	virtual ARG_TYPE RemoveHead()
	{
		ASSERT(m_usingSize > 0);

		//	取得
		ARG_TYPE ret = m_array[m_readPoint];
		m_usingSize--;

		//	読み込みポインタ移動
		m_readPoint++;
		if(m_readPoint == m_array.GetCount())
			m_readPoint = 0; 

		ASSERT(	(m_writePoint == m_readPoint && (m_usingSize == 0 || m_usingSize ==  m_array.GetCount())) ||
				(m_writePoint > m_readPoint && m_writePoint - m_readPoint == m_usingSize) || 
				(m_writePoint < m_readPoint && m_array.GetCount() - (m_readPoint - m_writePoint)  == m_usingSize));

		return	ret;
	}

	/*!
		取得
	*/
	virtual ARG_TYPE GetHead()
	{
		ASSERT(m_usingSize > 0);

		//	取得
		ARG_TYPE ret = m_array[m_readPoint];

		ASSERT(	(m_writePoint == m_readPoint && (m_usingSize == 0 || m_usingSize ==  m_array.GetCount())) ||
				(m_writePoint > m_readPoint && m_writePoint - m_readPoint == m_usingSize) || 
				(m_writePoint < m_readPoint && m_array.GetCount() - (m_readPoint - m_writePoint)  == m_usingSize));

		return	ret;
	}

protected:
	//////////////////////////////////////////////////////////////
	//	補助
	//////////////////////////////////////////////////////////////
	//!	変数初期化
	virtual void InitInternal()
	{
		m_readPoint = 0;
		m_writePoint = 0;
		m_usingSize = 0;
	}

	//!	全データ解放
	virtual void Close()
	{
		m_array.RemoveAll();
		InitInternal();
	}

	//!	必要なら増加
	virtual void Grow(int wantSize)
	{
		while(m_array.GetCount() < wantSize + m_usingSize)
			SetMinQueueSize(m_array.GetCount() * 2 + 1);	//	2倍に
	}

	//!	再配置
	virtual void Relocation(int oldSize, int newSize)
	{
		if(m_readPoint <= m_readPoint)
		{
			//	増大分
			int grew = newSize - oldSize;

			//	移動
			if(m_writePoint < grew)
			{
				//	後ろへ移動する
				for(int i=0;i<m_writePoint;i++)
					m_array[oldSize + i] = m_array[i];
				m_writePoint = oldSize + m_writePoint;
			}
			else
			{
				//	後ろへ移動する
				for(int i=0;i<grew;i++)
					m_array[oldSize + i] = m_array[i];

				//	残りを先頭へ移動する
				int left = m_writePoint - grew;
				for(int i=0;i<left;i++)
					m_array[i] = m_array[i + grew];
				m_writePoint = left;
			}
		}
	}

public:
	//////////////////////////////////////////////////////////////
	//	メンバ変数
	//////////////////////////////////////////////////////////////
	//!	バッファ
	CSimpleArrayTemplate<TYPE, ARG_TYPE, CONSTRUCTOR, INIT_ALLOC>	m_array;

	//!	読み込み位置
	int						m_readPoint;

	//!	書き込み位置
	int						m_writePoint;

	//!	使用サイズ
	int						m_usingSize;
};



/*!
	ポインタ用 Queue テンプレート
*/
template< class _TYPE, int INIT_ALLOC = 10>
class CPtrQueueTemplate : public CSimpleArrayTemplate<_TYPE, _TYPE, CSimpleArrayTemplateItmeConstructor<_TYPE>, INIT_ALLOC>
{
protected:
	//	子クラスで使用できるように
	typedef	_TYPE			TYPE;
};

