#ifndef VECTOR_H__
#define VECTOR_H__

#include <algorithm>	// 使用std::swap
#include <sstream>		// 使用std::stringstream
#include <stdexcept>

template <typename T>
class Vector {
private:

	enum {
		INIT_SIZE = 10		// 初始大小, 必須大于0
	};

	/* 數據內部存儲結構為循環存儲結構
	 * data_	 指向被分配內存的首地址;
	 * begin_	 首個有效數據的下標;
	 * end_		 最后一個有效數據下標邏輯上的后一位
	 * capacity_ 已分配的空間大小
	 *
	 *	數據儲存于 [begin_, end_) 區間內
	 *	以begin_ == end_作為Vector為空標志,
	 *	為data_分配的空間總比實際利用空間多至少1,
	 *	以檢查Vector滿的情況
	 */
	T *data_;
	int begin_;
	int end_;
	int capacity_;

	/* 檢查參數index是否在合法范圍內, 
	 * 若超出范圍, 拋出std::out_of_range異常, 
	 * 否則返回
	 */
	void checkRange(int index) const {
		if ( 0 <= index && index < size() ) return;

		using namespace std;
		// 生成錯誤信息
		stringstream buf;
		buf << "Vector: Index out of range!\n"
			<< "\tSize: "	<< size()
			<< "\tIndex: "	<< index
			<< endl;

		throw out_of_range(buf.str());

	} // checkRange(int) const

	/* 返回邏輯上index的下一個位置
	 */
	int incr(int index) const {
		return (index+1) % capacity_;
	} // incr(int) const

	/* 返回邏輯上index的上一個位置
	 */
	int decr(int index) const {
		if (index == 0)
			return capacity_-1;
		else
			return index-1;
	} // decr(int) const

public:

	/* 構造函數, 初始化Vector使之為空并且有保留INIT_SIZE個T的空間
	 */
	Vector() {
		data_ = new T[INIT_SIZE];
		capacity_ = INIT_SIZE;
		begin_ = end_ = 0;
	} // Vector()

	/* 拷貝構造函數, 從that創建Vector,
	 * 使被創建的Vector所具有的元素和that相同
	 */
	Vector(const Vector& that) {
		capacity_ = that.size() + INIT_SIZE;	// 確定分配空間大小

		data_ = new T[capacity_];	// 分配空間

		// 拷貝數據
		for (int i=0, j=that.begin_; j != that.end_; ++i, j=that.incr(j)) {
			data_[i] = that.data_[j];
		}
		
		// 更新成員數據
		begin_ = 0;
		end_ = that.size();

	} // Vector(const Vector&)

	/* 析構函數, 清理所占用的資源
	 */
	~Vector() {
		delete [] data_;
	} // ~Vector()

	/* 賦值操作將當前Vector賦值為that
	 */
	Vector& operator=(const Vector& that) {
		if (this == &that) return *this;	// 自我賦值

		Vector v(that);		// 拷貝that的值
		swap(v);			// 保存到this

		return *this;
	} // operator=(const Vector&)

	/* 交換兩個Vector的內容
	 */
	void swap(Vector& that) {
		if (this == &that) return;	// 自我交換

		using std::swap;
		swap(data_, that.data_);
		swap(begin_, that.begin_);
		swap(end_, that.end_);
		swap(capacity_, that.capacity_);
	} // swap(Vector&)

	/* 將元素e插入Vector的頭部
	 * 若空間不足自動分配
	 */
	void pushFront(const T& e) {
		if ( size()+1 >= capacity_ )
			reserve(1 + capacity_*1.5);
		data_[decr(begin_)] = e;
		begin_ = decr(begin_);
	} // pushFront(const T&)

	/* 將元素e插入Vector的尾端
	 * 若空間不足自動分配
	 */
	void pushBack(const T& e) {
		if ( size()+1 >= capacity_ )
			reserve(1 + capacity_*1.5);
		data_[end_] = e;
		end_ = incr(end_);
	} // pushBack(const T&)

	/* 將頭部元素刪除
	 * 如果Vector為空, 拋出std::underflow_error異常
	 */
	void removeFront() {
		if (size() <= 0) {
			throw std::underflow_error("Vector: Underflow!\n"
									   "\tOperation: removeFront()\n");
		}
		begin_ = incr(begin_);
	} // removeFront()

	/* 將尾部元素刪除
	 * 如果Vector為空, 拋出std::underflow_error異常
	 */
	void removeBack() {
		if (size() <= 0) {
			throw std::underflow_error("Vector: Underflow!\n"
									   "\tOperation: removeBack()\n");
		}
		end_ = decr(end_);
	} // removeBack()

	/* 查詢頭部元素
	 * 如果Vector為空, 拋出std::out_of_range異常
	 */
	const T& front() const {
		checkRange(0);
		return data_[begin_];
	} // front() const

	/* 查詢尾部元素
 	 * 如果Vector為空, 拋出std::out_of_range異常
	 */
	const T& back() const {
		checkRange(size()-1);
		return data_[decr(end_)];
	} // back() const

	/* 查詢位置為index的元素
	 * 如果index不滿足 0 <= index && index < size(),
	 * 拋出out_of_range異常
	 * 提供const和非const兩個版本
	 */
	T& operator[](int index) {
		checkRange(index);
		return data_[(begin_ + index) % capacity_];
	} // operator[](int)

	const T& operator[](int index) const {
		checkRange(index);
		return data_[(begin_ + index) % capacity_];
	} // operator[](int) const


	/* 預留至少capacity的空間
	 */
	void reserve(int capacity) {
		if (capacity <= capacity_) return;	// 需要的空間已經被滿足

		T *new_data = new T[capacity];		// 分配新的空間

		// 拷貝數據
		int i, j;
		for (i=0, j=begin_; j != end_; ++i, j=incr(j)) {
			new_data[i] = data_[j];
		}

		delete [] data_;					// 釋放舊的空間

		// 更新成員數據
		data_ = new_data;
		capacity_ = capacity;

		begin_ = 0;
		end_ = i;

	} // reserve(int)

	/* 將向量增大到sz大小
	 */
	void enlarge(int sz) {
		reserve(sz+1);
		end_ = (begin_ + sz) % capacity_;
	} // enlarge(int)

	/* 查詢預留空間的大小
	 */
	int capacity() const {
		return capacity_;
	} // capacity() const

	/* 查詢Vector中現存元素的數目
	 */
	int size() const {
		return (begin_ <= end_) ?
			   (end_ - begin_) :
			   (end_ + capacity_ - begin_);
	} // size() const

	/* 查詢Vector是否為空
	 */
	bool isEmpty() const {
		return size() == 0;
	} // isEmpty() const

}; // Vector



#endif // VECTOR_H__