#ifndef DEQUE_H_
#define DEQUE_H_

namespace std {
	template <class T>
	class deque {
		// コピーコンストラクタ用法禁止
		deque(deque& org) {}
		// コピー代入演算子用法禁止
		void operator =(deque& org) {}
		
	protected:
		T* pt_; // 動的に割り当てた配列へのポインタ
		size_t capacity_; // 割り当て済みの配列サイズ
		size_t elements_; // 格納した要素数
		int increase_; // 配列増加分
		int findex_; // 先頭要素操作用
		int bindex_; // 末尾要素操作用
		
		/*
		 * キャパシティを広げる
		 */
		void expand();
		
	public:
		/*
		 * 引数付き兼デフォルトコンストラクタ
		 */
		explicit
		deque(int capacity = 5, int increase = 5);
		
		/*
		 * デフォルトデストラクタ
		 */
		virtual ~deque();
		
		/*
		 * 要素数を返す
		 */
		inline size_t size() const;
		
		/*
		 * 最大要素数を返す
		 */
		inline size_t max_size() const;
		
		/*
		 * 配列が空かどうか
		 */
		bool empty() const;
		
		/*
		 * 先頭に要素を追加
		 */
		void push_front(const T& x);
		
		/*
		 * 末尾に要素を追加
		 */
		void push_back(const T& x);
		
		/*
		 * 先頭要素を削除
		 */
		void pop_front();
		
		/*
		 * 末尾要素を削除
		 */
		void pop_back();
		
		/*
		 * 先頭要素を参照
		 */
		T& front();
		
		/*
		 * 末尾要素を参照
		 */
		T& back();
	};

	template <class T>
	void deque<T>::expand() {
		// increase_分キャパシティを広げる
		capacity_ += increase_;
		
		// 新しい配列を動的に確保
		T* newpt_ = new T[capacity_];
		
		int newfindex_ = (capacity_ - elements_) / 2;
		
		// データを新しい配列にコピー
		int i;
		for(i = 0; i < elements_; i++) {
			newpt_[newfindex_ + i] = pt_[findex_ + i];
		}
		findex_ = newfindex_;
		bindex_ = newfindex_ + elements_;
		
		delete[] pt_;
		pt_ = newpt_;
	}
	
	template <class T>
	deque<T>::deque(int capacity, int increase) {
		// キャパシティを設定 最低値5
		capacity_ = capacity > 5 ? capacity : 5;
		// 増加分設定
		increase_ = increase > 0 ? increase : 5;
		
		capacity_ = capacity;
		increase_ = increase;
		
		// 配列を動的に確保
		pt_ = new T[capacity_];
		
		// 空の値T()で初期化
		for(int i = 0; i < capacity_; i++) {
			pt_[i] = T();
		}
		
		// findex_とbindex_を中央位置に設定
		findex_ = bindex_ = capacity_ / 2;
	}
	
	template <class T>
	deque<T>::~deque() {
		delete[] pt_;
	}
		
	template <class T>
	size_t deque<T>::size() const {
		return elements_;
	}
	
	template <class T>
	size_t deque<T>::max_size() const {
		return capacity_;
	}
	
	template <class T>
	bool deque<T>::empty() const {
		return elements_ == 0 ? true : false;
	}
	
	template <class T>
	void deque<T>::push_front(const T& x) {
		if(--findex_ >= 0) {
			pt_[findex_] = x;
			elements_++;
		} else {
			// findex_を元に戻す
			findex_++;
			
			// キャパシティを広げる
			expand();
			pt_[findex_] = x;
			elements_++;
		}
	}

	template <class T>
	void deque<T>::push_back(const T& x) {
		if(bindex_ <= capacity_ - 1) {
			pt_[bindex_++] = x;
			elements_++;
		} else {
			// キャパシティを広げる
			expand();
			pt_[bindex_++] = x;
			elements_++;
		}
	}
	
	template <class T>
	void deque<T>::pop_front() {
		if(findex_ != bindex_) {
			pt_[findex_] = T();
			findex_++;
			elements_--;
		} else {
			pt_[findex_] = T();
		}
	}
	
	template <class T>
	void deque<T>::pop_back() {
		if(bindex_ != findex_) {
			pt_[--bindex_] = T();
			elements_--;
		} else {
			pt_[findex_] = T();
		}
	}
	
	template <class T>
	T& deque<T>::front() {
		return pt_[findex_];
	}
	
	template <class T>
	T& deque<T>::back() {
		return pt_[bindex_];
	}
}

#endif /*QUEUE_H_*/
