//------------------------------------------------------------------------------
// 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 ARRAY_LIST_H_
#define ARRAY_LIST_H_

namespace Lamp{

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

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

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

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

	//--------------------------------------------------------------------------
	// 情報の取得
	//--------------------------------------------------------------------------
	/**
	 * 要素数の取得
	 * @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_[index];
	}

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

	/**
	 * キャパシティの取得
	 * @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_[i] == 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_[i] == searchValue){ return i; }
		}
		return -1;
	}

	//--------------------------------------------------------------------------
	// アレイリストの変更
	//--------------------------------------------------------------------------
	/**
	 * 要素の追加
	 * @param value 要素
	 */
	void add(const Type& value){
		if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
		array_[count_] = value;
		count_++;
	}

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

	/**
	 * 要素の削除
	 * @param index 削除する要素のインデックス
	 * @return アレイリストから削除した要素
	 */
	Type remove(int index){
		Assert(index >= 0);
		Assert(index < count_);
		Assert(count_ > 0);
		Type result = array_[index];
		count_--;
		for(int i = index; i < count_; i++){ array_[i] = array_[i + 1]; }
		return result;
	}

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

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

	/**
	 * 全要素を削除
	 * @param capacity クリア後のキャパシティ
	 */
	void clear(int capacity){
		Assert(capacity >= 0);
		if(capacity <= 0){ capacity = 1; }
		delete[] array_;
		capacity_ = capacity;
		array_ = new Type[capacity_];
		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*) ){
		qsort(array_, 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_, count_, sizeof(Type),
			(int(*)(const void*, const void*))compare);
	}

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

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

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

	// アレイ本体
	Type* array_;
	// サイズ
	int count_;
	// キャパシティ
	int capacity_;
	// デフォルトキャパシティ
	static const int defaultCapacity_ = 16;
};

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