
/*!
  @author d金魚
	@note 
	licence:BSD Licence<br>
	d金魚が唯一、これは有用なクラスだ！と言えるもの･･･<br>
	array_onebyoneはvectorのデータ保存専用版のようなものです。
	<table border>
	<tr><td></td><th> vector </th><th> array_onebyone </th></tr>
	<tr><th>長所</th><td>
		iteratorがある( iterateできる。)
		</td><td>iteratorは無いが、handleがあるので、それを使えば、vectorのように
		要素を削除してもiterator(array_onebyoneではhandle)は無効にならない。
		</td></tr>
	<tr><th>短所</th><td>
		std::vectorは要素を一つでも開放するとiteratorが無効になる。
		</td><td>iteratorが無い。メモリをvectorより多く使う。
		今のところ、二重開放チェックが出来ない。
		</td></tr>
	</table>
*/



#ifndef DKUTIL_DKTL_ARRAY_ONEBYONE_HPP
#define DKUTIL_DKTL_ARRAY_ONEBYONE_HPP


#include <dkutil/macro.hpp>
#include <vector>
#include <deque>
#include <dkutil/utility.hpp>



namespace dkutil{


/*!
配列から高速に空いている領域を割り当てるもの。
どんなに増えてもほとんど分岐しないので高速。
注意：対象にするデータ型にはコピーコンストラクタを宣言しておいてください。
@param T 対照のデータ型
@param A allocator
@param VECTOR STLのvectorの互換コンテナ（デフォルトではSTLのvector
@param DEQUE STLのdequeの互換コンテナ（デフォルトではSTLのdeque
@param SizeAfterInit array_onebyoneが生成された時の最初の配列要素の数
*/
//BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
/*#if DKUTIL_MSVC_COMPILER

template<class T,typename A=std::allocator<T>,class VECTOR=std::vector<T,A> ,class DEQUE=std::deque<VECTOR::size_type,A> ,unsigned int SizeAfterInit=200>
class array_onebyone{
public:

#else

template<class T,typename A=std::allocator<T>,class VECTOR=std::vector<T,A> ,class DEQUE=std::deque<unsigned long,A>,unsigned int SizeAfterInit=200>
class array_onebyone{
public:

#endif*/
template<class T,unsigned int SizeAfterInit=200,
	typename A=std::allocator<T>,
	class VECTOR=std::vector<T,A> ,class DEQUE=std::deque<unsigned long,A> 
>
class array_onebyone{
public:
	
	BOOST_STATIC_CONSTANT(size_t,	enuExtendSize = SizeAfterInit);
	
	typedef A allocator_type;
  typedef typename A::size_type size_type;
  typedef typename A::difference_type difference_type;
  typedef typename A::reference reference;
  typedef typename A::const_reference const_reference;
  typedef typename A::value_type value_type;
	typedef size_type handle;
	typedef VECTOR VECTOR_TYPE;
	typedef DEQUE DEQUE_TYPE;

DKUTIL_PROTECTED://なぜか boost 対応･･･

	DEQUE mq;
	VECTOR mv;
	
	typename VECTOR_TYPE::size_type now_size;

public:
	//array_onebyone(){clear();now_size = 0;}
	array_onebyone(size_type construct_size=enuExtendSize){
		clear();
		mv.reserve(construct_size);
		now_size = 0;
	}


	~array_onebyone(){
		clear();
	}
	/*!
	@param x[in] 入れるデータ
	@return handle ハンドルが帰る。このハンドルを使って入れたデータを操作する
	*/
	///データを入れる
	handle push(const T &x){
		
		now_size++;//今のサイズをいんくりめんとぉ！
		
		if(now_size==UINT_MAX)
		{
			DKUTIL_THROW_OR_NOTICE(
				std::runtime_error("dkutil::array_onebyone なんかもう入らないらしいよ。")
			);
			return NULL;
		}
		if(mq.empty())
		{//キューが空だったら？	
			//そのままvector配列にぶち込む
			mv.push_back(x);
			return (now_size - 1);
			//return (mv.size() - 1);//これでいいのかは不明･･･
		}
		/*else//キューの中身が空じゃなかったら
		{

		}*/
		size_type temp;
		mv[temp = mq.front()]=x;//キューのフロントを参照して添え字を見つけ、データ挿入。
		mq.pop_front();//frontを削除
		return temp;//添え字をハンドルとして返す。

		//実際、ありえないけど念のため書いておく^^;
		//throw std::logic_error("array_onebyone:push:logic error");
		//return NULL;
	}
	
	///データを削除する @param h[in] pushで得たハンドル
	void pop(const handle &h){
		if(now_size == UINT_MAX){//buffer overflow
			DKUTIL_THROW_OR_NOTICE(std::invalid_argument("array_onebyone buffer overflow "));
			//throw std::invalid_argument("buffer overflow ");
			return;
		}
		if(now_size ==0){
			DKUTIL_THROW_OR_NOTICE(std::invalid_argument("array_onebyone::now_size == 0 push() is not called. "));
			return;
		}
		now_size--;
		if(now_size==UINT_MAX){
			DKUTIL_THROW_OR_NOTICE(
				std::runtime_error("array_onebyone なんかpopしすぎらしいよ。")
			);
		}
		//コンテナに入っているデストラクタは呼び出しておく･･･
		A alc = mv.get_allocator();
		alc.destroy(alc.address(mv.at(h)));
		//使われていないよキュー　にぶち込む
		mq.push_back(h);
	}
	///vectorで使われているallocatorをゲットする
	A get_allocator() const{
		return mv.get_allocator();
	} 
	///何個　vectorに入っているか。vectorのsize()ではない
	size_type size()const{ 
		return now_size;//mv.size();
	}
	//size_type max_size()const{	return mv.max_size();}
	///vectorのcapacity
	size_type capacity()const{
		return mv.capacity();
	}
	///array_onebyone内部で使われているvectorをゲット
	const VECTOR &get_vector()const{
		return mv;
	}
		///使い方によっては危ない。
	VECTOR &get_vector(){
		return mv;
	}
	///array_onebyone内部で使われているdequeをゲット
	const DEQUE &get_deque()const{
		return mq;
	}
	///使い方によっては危ない。
	DEQUE &get_deque(){
		return mq;
	}
	bool empty()const{	//return (mv.empty() && mq.empty());
		return (now_size == 0);
		//return mv.empty();
	}
	void resize(size_type new_size,const T &x=T()){
		if(new_size < mv.size()){
			DKUTIL_THROW_OR_NOTICE(
				std::invalid_argument("resize member function :argument new_size is too small.")
			);
			return;
		}
		mv.resize(new_size,x);
	}
	void reserve(size_type n){
		if(n < mv.size()){
			DKUTIL_THROW_OR_NOTICE(
				std::invalid_argument("reserve member function :argument n is too small.")
			);
			return;
		}
		mv.reserve(n);
	}
	bool empty_free_queue()
	{
		return mp.empty();
	}
	//要素の参照
	///vectorのatと同じです。@param pos[in] ちなみにpushで得たhandleをposに入れるのでもOKだと。？
	reference at(size_type pos){
		return mv.at(pos);
	}
	///atのpointer version
	T *at_ptr(size_type pos){
		return &at(pos);
	}
  const_reference at(size_type pos) const
	{
		return mv.at(pos);
	}
	///vector のoperator[]と同じ。@param pos[in] posにはpushで得たハンドルでもOK
	reference operator[](size_type pos){
		return mv[pos]; 
	}
  const_reference operator[](size_type pos)const{
		return mv[pos]; 
	}
	
	///挿入 @param pos[in] pushで得たhandle @param x[in] 入れたいもの
	void insert(handle pos,T &x){
		//now_size ++;
#	ifdef _DEBUG
		try{
			mv.at(pos);
		}catch(...){
			char *str="posが無効です。";
			DEBUGMB(str);
			::assert(!str);
		}
#	endif
		mv[pos] = x;
		
	} 
	
	void clear(){ 
		now_size = 0;
		mv.clear();
		mq.clear(); 
	}

};

#define array_onebyone_ex array_onebyone
}//end of dkutil namespace


#endif // end of include once
