
/*!
  @author d金魚
	@note 
	copyright (c) d金魚
	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 _dkutilTL_array_onebyone_mingw_hpp_
#define _dkutilTL_array_onebyone_mingw_hpp_

//#include "dKingyoMacro.h"



namespace dkutil{







/*!
配列から高速に空いている領域を割り当てるもの。
どんなに増えてもほとんど分岐しないので高速。
注意：対象にするデータ型にはコピーコンストラクタを宣言しておいてください。
@param T 対照のデータ型
@param A allocator
@param VECTOR STLのvectorの互換コンテナ（デフォルトではSTLのvector
@param DEQUE STLのdequeの互換コンテナ（デフォルトではSTLのdeque
@param SizeAfterInit array_onebyone_exが生成された時の最初の配列要素の数
*/
template<class T,typename A=std::allocator<T>,
	class VECTOR=std::vector<T,A> ,
	class DEQUE=std::deque<size_t,A> ,
	unsigned int SizeAfterInit=200>
class array_onebyone_ex{
public:
	enum{
		enuExtendSize = SizeAfterInit,
	};
	typedef A allocator_type;
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef _List_node<_Tp> _Node;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
	typedef size_type handle;
	typedef VECTOR VECTOR_TYPE;
	typedef DEQUE DEQUE_TYPE;
#ifndef BOOST_NO_PRIVATE_IN_AGGREGATE //なぜか boost 対応･･･
protected:
#endif
	DEQUE mq;
	VECTOR mv;
	
	VECTOR_TYPE::size_type now_size;

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


	virtual ~array_onebyone_ex(){clear();}
	/*!
	@param x[in] 入れるデータ
	@return handle ハンドルが帰る。このハンドルを使って入れたデータを操作する
	*/
	///データを入れる
	handle push(const T &x){
		
		now_size++;//今のサイズをいんくりめんとぉ！
		
		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_ex:push:logic error");
		return NULL;
	}
	
	///データを削除する @param h[in] pushで得たハンドル
	void pop(const handle &h){
		if(now_size == UINT_MAX){//buffer overflow
			throw std::invalid_argument("buffer overflow ");
			return;
		}
		if(now_size ==0){
			throw std::invalid_argument("now_size == 0 push() is not called. ");
			return;
		}
		now_size--;
		//コンテナに入っているデストラクタは呼び出しておく･･･
		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_ex内部で使われているvectorをゲット
	VECTOR &get_vector()const{return mv;}
	///array_onebyone_ex内部で使われているdequeをゲット
	DEQUE &get_deque()const{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()){
			throw 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()){
			throw
				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(); }

};


///新しいメモリ領域を作成してもとのメモリの内容をコピーする
template<class T>
inline int ReallocateByNew(T **before,DWORD oldcount,T **after,DWORD extend,UINT *aftercount)
{
	DWORD total = oldcount + extend;//合計の新規確保分
	T *get = new T[total];//maxcountはここで更新
	if(get==NULL){
		return -1;//だめじゃん！！最悪〜〜
	}
	//メモリコピー
	for(DWORD i=0;i<oldcount;i++){
		get[i]=(*before)[i];
	}
	//memcpyはC++のオブジェクトも出来るかどうか分からないので＾＾；

	delete[] (*before);//元のは開放
	(*after) = get;//アドレスを入れる。
	(*aftercount) = total;//合計の確保した数を入れる
	return 0;
}





/*!
@param T 対象
@param EXTEND_ARRAY 再確保する時のサイズ
@param A allocator
*/
///元祖array_onebyone
template <class T,unsigned int EXTEND_ARRAY=enuDefaultExpandSize,typename A = std::allocator<T> >
class array_onebyone{
public:
	typedef A allocator_type;
  typedef A::size_type size_type;
  typedef A::difference_type difference_type;
  typedef A::reference reference;
  typedef A::const_reference const_reference;
  typedef A::value_type value_type;
	typedef std::deque<unsigned int,A> DEQUE_TYPE;
#ifndef BOOST_NO_PRIVATE_IN_AGGREGATE //なぜか boost 対応･･･
protected:
#endif
	A allocator;

	T *m;// Memory
	unsigned int maxcount;//配列の最大数
	unsigned int nowmp;//now  m point
	bool mflag;//is OK?)
	DEQUE_TYPE mp;//添え字のキュー
	enum{//,DWORD EXTEND_ARRAY=100
		enuExtendArray=EXTEND_ARRAY,
	};
	
public:
	typedef unsigned int handle;
	explicit array_onebyone(){
		maxcount=NULL;
		//nowmp=NULL;rend();をサポートするため･･･ 0では困る。Initで1にしておく
		nowmp=0;
		m=NULL;
		mflag=false;
		Init(enuExtendArray);
	}
  array_onebyone(const array_onebyone<T,EXTEND_ARRAY,A> &a){
		mflag=false;
		maxcount = a.maxcount;
	  nowmp = a.nowmp;
	  //getflag = a.getflag;
	  mp = a.mp;
		if(a.maxcount > 0){
			m = new T[a.maxcount];
			if(!m)
			{//例外発生しました！！
				//ここでなぎぇたいのぬぃ〜〜〜！！！！
				// throw std::domain_error("array_onebyone:copy constructor:memory allocate error");
				return;
			}
			for(int i = 0; i < a.maxcount; i++){//メモリコピー
				 *(m + i) = *(a.m + i);
			}
			//memcpy(m, a.m, a.maxcount);これだとC++のオブジェクトも出来るかどうかは不明
		}
		else{
			m = NULL;
		}
		mflag=true;//初期化済み
	}

	bool empty_free_queue(){
		return mp.empty();
	}

  void resize(size_type n){
		if(maxcount >= n){
			std::domain_error("Size is not made small.");
		}
		ReallocateByNew<T>(&m,maxcount,&m,n,&maxcount);
	}
  size_type size() const{return nowmp-1;}
  size_type max_size() const{return maxcount;}
  bool empty() const{
		if((mp.empty() && nowmp<=1) || mp.size()==nowmp)
			return true;
		return false;
	}
  A get_allocator() const{return allocator;}
  reference at(size_type pos){
		if(nowmp <= pos){
			throw std::range_error("range error");
		}
		return m[pos];
	}
	
  const_reference at(size_type pos) const{
		if(nowmp <= pos){
			throw std::range_error("range error");
		}
		return m[pos];
	}
  reference operator[](size_type pos){return m[pos]; }
  const_reference operator[](size_type pos)const{	return m[pos]; }
  //reference front(){	return m;}
  //const_reference front() const;
  //reference back(){return	m[nowmp-1];}
  //const_reference back() const;
  handle push(const T& x){
		if(mflag==false){
			Init(enuExtendArray);
		}
		if(nowmp>=maxcount)
		{//ちょっとこのままじゃアクセスバイオレーションだ〜よ！
			if(mp.empty())
			{//キューが空だったら？	
				if(-1==Reallocate())//リアロックする。
				{
					return NULL;//最悪〜〜失敗。
				}
				else//上手くできたようなので
				{
					return push(x);//再起呼び出し
				}
			}
			else//キューの中身が空じゃなかったら
			{
				DWORD l_num;//配列の添え字をゲットする
				l_num=(mp.front());//ってことでGET!
				mp.pop_front();//削除する
				m[l_num]=x;//データ挿入。
				return l_num;//添え字をハンドルとして返す。
			}
		}else{
			m[nowmp] = x;//でーたを入れとく
			return nowmp++;//添え字をハンドルとして返す
		}
		//実際、ありえないけど念のため書いておく^^;
		return NULL;
	}
  void pop(handle item){mp.push_back(item);}
  //void assign(const_iterator first, const_iterator last);
  //void assign(size_type n, const T& x = T());
  //iterator insert(iterator it, const T& x = T());
  //void insert(iterator it, size_type n, const T& x);
  //void insert(iterator it,  const_iterator first, const_iterator last);
  //iterator erase(iterator it);
  //iterator erase(iterator first, iterator last);
  void clear(){
		if(m){
			delete[] m;
			m=NULL;
		}	
		maxcount=NULL;
		nowmp=NULL;
		m=NULL;
		mp.clear();//キューもすべて削除
		mflag=false;//フラグを下ろす
	}
  //void swap(deque x);
   
	virtual ~array_onebyone(){
		clear();
	}
protected:
	/*!
	@param memory_count[in] 事前に確保するT型の変数の数
	*/
	///配列を初期化する。
	int Init(size_t memory_count)
	{
		if(mflag==true)return 1;//もう一回呼び出しはダメです。
		maxcount=memory_count;
		//Dyanamic memoryだったらnewしかないでしょ＾＾；
		m = new T[memory_count];
		if(!m) return -1;//だめじゃんNULLじゃ

		nowmp=1;//rend()を使うため
		mflag=true;//フラグを立てる
		
		return 0;
	}
	///配列をEXNTEND_ARRAY分　拡張する。縮小は出来ないのでclear()ですべてを開放すること
	int Reallocate(){
		if(mflag==false){
			if(-1==Init(100)){//百個くらい＾＾；
				throw std::runtime_error("The worst error");
			}
		}
		return ReallocateByNew<T>(&m,maxcount,&m,enuExtendArray,&maxcount);
	}
};

}//end of dkutil namespace


#endif // end of include once
