//------------------------------------------------------------------------------
// Lamp : Open source game middleware
// Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//------------------------------------------------------------------------------

/** @file
 * デックヘッダ
 * @author Junpee
 */

#ifndef DEQUE_H_
#define DEQUE_H_

namespace Lamp{

//------------------------------------------------------------------------------
/**
 * デック
 *
 * このクラスは継承しないで下さい。
 */
template <typename Type>
class Deque{
public:
	//--------------------------------------------------------------------------
	// 構築、破棄
	//--------------------------------------------------------------------------
	/**
	 * コンストラクタ
	 */
	Deque(){
		capacity_ = defaultCapacity_;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	/**
	 * コンストラクタ
	 * @param capacity 初期キャパシティ。2の累乗が好ましい。
	 */
	explicit Deque(int capacity){
		Assert(capacity > 0);
		capacity_ = capacity;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	/**
	 * デストラクタ
	 */
	~Deque(){ delete[] array_; }

	/**
	 * クローン
	 * @param destination クローン先デック
	 */
	void clone(Deque& destination) const{
		delete[] destination.array_;
		destination.capacity_ = capacity_;
		destination.array_ = new Type[capacity_];
		destination.front_ = front_;
		destination.count_ = count_;
		// 文字列クラス等を正しくコピーするにはmemcpyでは駄目
		for(int i = 0; i < count_; i++){
			int index = (i + front_) % capacity_;
			destination.array_[index] = array_[index];
		}
	}

	//--------------------------------------------------------------------------
	// 情報の取得
	//--------------------------------------------------------------------------
	/**
	 * 要素数の取得
	 * @return 要素数
	 */
	int getCount() const{ return count_; }

	/**
	 * 空かどうか
	 * @return 空ならtrueを返す
	 */
	bool isEmpty() const{ return (count_ == 0); }

	/**
	 * 要素の取得
	 * @param index 取得する要素のインデックス
	 * @return 要素
	 */
	Type& get(int index) const{
		Assert(index >= 0);
		Assert(index < count_);
		return array_[(front_ + index) % capacity_];
	}

	/**
	 * 要素の取得
	 * @param index 取得する要素のインデックス
	 * @return 要素
	 */
	Type& operator [](int index) const{
		Assert(index >= 0);
		Assert(index < count_);
		return array_[(front_ + index) % capacity_];
	}

	/**
	 * キャパシティの取得
	 * @return キャパシティ
	 */
	int getCapacity() const{ return capacity_; }

	/**
	 * 前からの値の検索
	 *
	 * デックの前から値を検索し、発見できればそのインデックスを返します。
	 * @param searchValue 検索する値
	 * @return 値のインデックス。値が無ければ-1を返す。
	 */
	int indexOf(const Type& searchValue) const{
		for(int i = 0; i < count_; i++){
			if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
		}
		return -1;
	}

	/**
	 * 後からの値の検索
	 *
	 * デックの後ろから値を検索し、発見できればそのインデックスを返します。
	 * @param searchValue 検索する値
	 * @return 値のインデックス。値が無ければ-1を返す。
	 */
	int lastIndexOf(const Type& searchValue) const{
		for(int i = count_ - 1; i >= 0; i--){
			if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
		}
		return -1;
	}

	//--------------------------------------------------------------------------
	// デックの変更
	//--------------------------------------------------------------------------
	/**
	 * 先頭への要素の追加
	 * @param value 要素
	 */
	void pushFront(const Type& value){
		if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
		front_--;
		if(front_ < 0){ front_ += capacity_; }
		array_[front_] = value;
		count_++;
	}

	/**
	 * 末尾への要素の追加
	 * @param value 要素
	 */
	void pushBack(const Type& value){
		if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
		array_[(front_ + count_) % capacity_] = value;
		count_++;
	}

	/**
	 * 先頭からの要素の削除
	 * @return 削除した要素
	 */
	Type popFront(){
		Assert(count_ > 0);
		int resultIndex = front_;
		front_ = (front_ + 1) % capacity_;
		count_--;
		return array_[resultIndex];
	}

	/**
	 * 末尾からの要素の削除
	 * @return 削除した要素
	 */
	Type popBack(){
		Assert(count_ > 0);
		int resultIndex = (front_ + count_ - 1) % capacity_;
		count_--;
		return array_[resultIndex];
	}

	/**
	 * 要素の設定
	 * @param index 要素を設定するインデックス
	 * @param value 要素
	 */
	void set(int index, const Type& value) const{
		Assert(index >= 0);
		Assert(index < count_);
		array_[(front_ + index) % capacity_] = value;
	}

	/**
	 * 要素の削除
	 * @param index 削除する要素のインデックス
	 * @return デックから削除した要素
	 */
	Type remove(int index){
		Assert(index >= 0);
		Assert(index < count_);
		Assert(count_ > 0);
		Type result = array_[(front_ + index) % capacity_];
		count_--;
		if(index < (count_ / 2)){
			// 前を詰める
			for(int i = index - 1; i >= 0; i--){
				int source = (front_ + i) % capacity_;
				int destination = (source + 1) % capacity_;
				array_[destination] = array_[source];
			}
			// 前インデックスもずらす
			front_ = (front_ + 1) % capacity_;
		}else{
			// 後を詰める
			for(int i = index; i < count_; i++){
				int destination = (front_ + i) % capacity_;
				int source = (destination + 1) % capacity_;
				array_[destination] = array_[source];
			}
		}
		return result;
	}

	/**
	 * 値による要素の削除
	 *
	 * デックの後ろから削除する値を検索し、同じ要素があれば削除します。
	 * @param removeValue 削除する要素の値
	 * @return 削除したインデックス。-1なら該当する要素無し。
	 */
	int removeByValue(const Type& removeValue){
		int index = lastIndexOf(removeValue);
		if(index == -1){ return index; }
		remove(index);
		return index;
	}

	/**
	 * 全要素を削除
	 */
	void clear(){ front_ = count_ = 0; }

	/**
	 * 全要素を削除
	 * @param capacity クリア後のキャパシティ
	 */
	void clear(int capacity){
		Assert(capacity >= 0);
		if(capacity <= 0){ capacity = 1; }
		delete[] array_;
		capacity_ = capacity;
		array_ = new Type[capacity_];
		front_ = count_ = 0;
	}

	/**
	 * キャパシティの設定
	 * @param newCapacity 新しいキャパシティ
	 */
	void setCapacity(int newCapacity){
		Assert(newCapacity >= count_);
		resize(newCapacity);
	}

	/**
	 * トリム
	 *
	 * 現在のサイズに合わせて使用メモリを最小にします。
	 */
	void trim(){
		if(count_ == 0){ resize(1);}
		else{ resize(count_); }
	}

	//--------------------------------------------------------------------------
	// ソートとサーチ
	//--------------------------------------------------------------------------
	/**
	 * ソート
	 *
	 * クイックソートでデックをソートします。<br>
	 * compareの返り値を以下のようにすると昇順にソートされます。<br>
	 * 第一引数が第二引数より大きいときは1以上<br>
	 * 第一引数と大に引数が同じ場合は0<br>
	 * 第一引数が第二引数より小さいときは-1以下
	 * @param compare 比較関数。
	 */
	void sort( int(*compare)(const Type*, const Type*) ){
		// 一塊にする
		if((front_ + count_) > capacity_){
			if(count_ != capacity_){
				// 隙間を詰める
				int destination = (front_ + count_) % capacity_;
				for(int i = front_; i < capacity_; i++, destination++){
					array_[destination] = array_[i];
				}

			}
			front_ = 0;
		}
		qsort(array_ + front_, count_, sizeof(Type),
			(int(*)(const void*, const void*))compare);
	}

	/**
	 * サーチ
	 *
	 * バイナリサーチでデックを検索します。<br>
	 * デックは昇順にソートされている必要があります。<br>
	 * 要素が見つからなかった場合はNULLを返します。
	 * compareは以下のような返り値を返してください。<br>
	 * 第一引数が第二引数より大きいときは1以上<br>
	 * 第一引数と大に引数が同じ場合は0<br>
	 * 第一引数が第二引数より小さいときは-1以下
	 * @param key 検索する値
	 * @param compare 比較関数
	 * @return 検索結果、見つからなければNULL
	 */
	Type* search(Type key, int(*compare)(const Type*, const Type*) ){
		return (Type*)bsearch(&key, array_ + front_, count_, sizeof(Type),
			(int(*)(const void*, const void*))compare);
	}

private:
	// リサイズ
	void resize(int newCapacity){
		Assert(newCapacity > 0);
		Type* newArray = new Type[newCapacity];
		// 文字列クラス等を正しくコピーするにはmemcpyでは駄目
		for(int i = 0; i < count_; i++){
			int index = i + front_;
			int source = index % capacity_;
			int destination = index % newCapacity;
			newArray[destination] = array_[source];
		}
		delete[] array_;
		array_ = newArray;
		capacity_ = newCapacity;
	}

	// コピーコンストラクタの隠蔽
	Deque(const Deque& copy);

	// 代入コピーの隠蔽
	void operator =(const Deque& copy);

	// 配列
	Type* array_;
	// 前インデックス
	int front_;
	// 要素数
	int count_;
	// キャパシティ
	int capacity_;
	// デフォルトキャパシティ
	static const int defaultCapacity_ = 16;

};

//------------------------------------------------------------------------------
} // End of namespace Lamp
#endif // End of DEQUE_H_
//------------------------------------------------------------------------------
