

/*!
  @author d金魚
  @since 2003/8/21
	@note
	licence:BSD Licence
*/

#ifndef dkutil_container__
#define dkutil_container__

#include "array_onebyone.h"

namespace dkutil{
//**********************************************************
//構造 
//メモリの領域　構造
//SIZE分の配列をコンテナとする。
//*は配列の1つの要素だと思ってください。
// 1 *********************
// 2 *********************
// 3 *********************
// ･ *********************
// ･ *********************
// ･ *********************
// UINT_MAX *********************

//この中から開いている1つの要素を探し出して　その中に代入するというものです。
//もちろん UINT_MAXまで配列を作成するわけではありません。必要に応じて追加していきます。
//最大UINT_MAXまでの配列を作ることができます。
//最大 SIZE * UINT_MAX までの要素を管理できると思います。

//改造の余地
//・CONTAINER自体に空きが出てきた場合、計算して二つのコンテナを一つにまとめる処理とか。
//・STLのlistのiteratorは12byte と超重い･･･　自作listを作る予定･･･


//**********************************************************

template<class T,unsigned int SIZE=enuDefaultExtendSize,typename A=std::allocator<T>,
	class CONTAINER= array_onebyone_ex<T,A,std::vector<T,A> ,std::deque<T,A> ,SIZE>,
	class CHAIN=std::list<CONTAINER,A> 
>
class container{
public:
	enum{
		enuExtendNum = SIZE,
	};
	typedef CONTAINER CONTAINER_TYPE;
	typedef CHAIN LIST_TYPE;
	typedef CONTAINER::DEQUE_TYPE DEQUE_TYPE;
	typedef CONTAINER::VECTOR_TYPE VECTOR_TYPE;
	

	typedef struct tugHandle{
		LIST_TYPE::iterator it;//iterator
		CONTAINER_TYPE::handle h;//handle
		T &operator *(){return (*it).at(h);}
		//T *operator ->(){return (*it).at_ptr(h);}
	}handle;


	explicit container(){
		m_c.clear();
		m_now_it = new_it();
		//dOutputDebugString("it size = %d\n",sizeof(iterator));
	}
	virtual ~container(){	m_c.clear();}
	///@param x[in] コンテナにxを入れます。
	///@return ハンドル（iterator)が帰ります。変える変数の型はcontainer::iteratorですので。
	handle push(const T &x)
	{
		if((*m_now_it).size() >= enuExtendNum && (*m_now_it).empty_free_queue())
		{//すでに今使っているコンテナに空き領域がなくなっていたら
			m_now_it = sarch_free_container();
			if(m_now_it == m_c.end())
			{//さらにすでに確保済みの空き領域もなくなっていたら
				//新しい領域作るしかないでしょう･･･
				m_now_it = new_it();
			}
			else
			{//いや、他のコンテナに空き領域はある。
			}
		}
		
		handle hand;
		hand.h = (*m_now_it).push(x);//ハンドルを保存する
		hand.it = m_now_it;//今のイテレータ

		return tit;
	}
	void pop(const handle &get_it){
		(*(get_it.it)).pop(get_it.h);
	}
	T &reference_item(const handle &ref){
		return (*ref);
	}

protected:
	LIST_TYPE::iterator new_it(){
		m_c.push_back(CONTAINER_TYPE());
		LIST_TYPE::iterator it=boost::prior(m_c.end());
		//for(int c=0;c != m_c.size() - 1;it++,c++){}
		//if((*it) != m_c.back()){MB("ERROR");}
		return it;
	}
	bool all_empty_container(){
		LIST_TYPE::iterator it=m_c.begin();
		for(int count=0;it != m_c.end();it++){
			if((*it).empty_free_queue()){
				count++;
			}
		}
		return (count==m_c.size());// == true or false??
	}
	LIST_TYPE::iterator sarch_free_container(){
		for(LIST_TYPE::iterator it=m_c.begin();it != m_c.end();it++){
			if(!(*it).empty_free_queue()){
				return it;
			}
		}
		return m_c.end();
	}
		
	LIST_TYPE::iterator m_now_it;//member of container list now pointing iterator

	LIST_TYPE m_c;//member of container list
};




}//end of dkutil



#endif//end of dkutil_container__