#pragma once
#include<assert.h>
namespace Mydeque
{
	template<class inputiterator,class T>
	void fill(inputiterator first, inputiterator last, const T& val);

	template<class inputiterator,class outputiterator>
	void copyAtfirst(inputiterator first, inputiterator last, outputiterator dest); //从后往前拷贝
	template<class inputiterator,class outputiterator>
	void copyAtlast(inputiterator first, inputiterator last, outputiterator dest); //从前往后拷贝

	template<class T, class Ref, class Ptr, size_t buffsize>
	struct deque_iterator
	{
		typedef typename Ref Ref;
		typedef typename Ptr Ptr;
		typedef Ptr* map_pointer;
		typedef deque_iterator self;
		deque_iterator()
			:first(nullptr),
			last(nullptr),
			cur(nullptr),
			node(nullptr)
		{ }
		void setnode(map_pointer Node)
		{
			node = Node;
			first = *Node;
			cur = first;
			last = first + buffsize;
		}
		Ref operator*()
		{
			return *cur;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		self& operator++() //前置++
		{
			++cur;
			if (cur == last) //判断当前元素是否在缓冲区的末尾位置
			{
				setnode(node + 1);//让node跳跃到下一个缓冲区
				cur = first; //cur指向起始位置
			}
			return *this;
		}
		self& operator--()
		{
			if (cur == first) { //判断当前元素是否在缓冲区的起始位置
				setnode(node - 1); //让node跳跃到上一个缓冲区
				cur = last - 1; //cur指向末尾位置
			}
			else {
				--cur;
			}
			return *this;
		}
		self operator++(int)
		{
			self tmp(*this);
			++(*this);
			return tmp;
		}
		self operator--(int)
		{
			self tmp(*this);
			--(*this);
			return tmp;
		}
		int operator-(const self& dq) const
		{
			return int((node - dq.node - 1) * buffsize) + (cur - first) + (dq.last - dq.cur);
		}
		self& operator+=(int n)
		{
			int offset = n + (cur - first);
			if (offset >= 0 && offset < buffsize)//判断是否在缓冲区内
			{
				cur += n;
			}
			else//目标不在缓冲区内
			{
				int offset_node =
					offset > 0 ? offset / int(buffsize) : ((offset + 1) / (int)buffsize) - 1;
				setnode(node + offset_node);//切换到正确的缓冲区
				cur = first + offset - offset_node * buffsize;//切换到正确的位置
			}
			return *this;
		}
		self operator+(int n)
		{
			self tmp(*this);
			return tmp += n;
		}
		self& operator-=(int n)
		{
			return *this += (-n);
		}
		self operator-(int n)
		{
			self tmp(*this);
			return tmp -= n;
		}
		Ref operator[](int n)
		{
			return *(*this + n);
		}
		bool operator==(const self& dq) const
		{
			return cur == dq.cur;
		}
		bool operator!=(const self& dq) const
		{
			return cur != dq.cur;
		}
		bool operator<(const self& dq) const
		{
			return node == dq.node ? cur < dq.cur : node < dq.node;
		}
		bool operator>(const self& dq) const
		{
			return node == dq.node ? cur > dq.cur : node > dq.node;
		}
		Ptr first; //指向缓冲区的头
		Ptr last; //指向缓冲区的尾
		Ptr cur; //指向缓冲区的当前元素
		map_pointer node; //指向缓冲区的指针
	};

	template<class T, size_t buffsize = 25>
	class deque {
	public:
		typedef T* Ptr;
		typedef T& Ref;
		typedef T** map_pointer;
		typedef deque self;
		typedef deque_iterator<T, T&, T*, buffsize> iterator;
		typedef deque_iterator<T, const T&, const T*, buffsize> const_iterator;
		deque()
		{
			Create_Map_And_Node(0);
		}
		deque(size_t n, const T& val)
		{
			Create_Map_And_Node(n);
			iterator it = start;
			while (it != finish)
			{
				*it = val;
				++it;
			}
		}
		~deque()
		{
			for (map_pointer it = start.node; it <= finish.node; it++)
			{
				delete[] * it;
			}
			delete[] map;
		}
		void push_back(const T& val)
		{
			if (finish.cur != finish.last-1)
			{
				*finish = val;
				++finish;
			}
			else {
				ReserveMapAtBack();
				*finish = val;
				*(finish.node + 1) = new T[buffsize];
				finish.setnode(finish.node + 1);
				finish.cur = finish.first;
			}
		}
		void push_front(const T& val)
		{
			if (start.cur != start.first)
			{
				--start;
				*start = val;
			}
			else {
				ReserveMapAtFront();
				*(start.node - 1) = new T[buffsize];
				/*start.setnode(start.node - 1);
				start.cur = start.last - 1;*/
				--start;
				*start = val;
			}
		}
		void pop_back()
		{
			assert(!empty());
			if (finish.cur != finish.first)
			{
				--finish;
			}
			else {
				delete[] finish.first;
				finish.setnode(finish.node - 1);
				finish.cur = finish.last - 1;
			}
		}
		void pop_front()
		{
			assert(!empty());
			if (start.cur != start.last - 1)
			{
				++start;
			}
			else {
				delete[] start.first;
				start.setnode(start.node + 1);
				start.cur = start.first;
			}
		}
		void clear()
		{
			for (map_pointer i = start.node; i <= finish.node; i++)
			{
				delete[] * i; //清除所有缓冲区
			}
			map_pointer tmp = map + map_size / 2;
			*tmp = new T[buffsize];
			start.setnode(tmp);
			start.cur = start.first;
			finish = start;
		}
		iterator insert(iterator pos, const T& val)
		{
			if (pos == finish) {
				push_back(val);
				return finish - 1;
			}
			else if (pos == start) {
				push_front(val);
				return start;
			}
			else {
				int index = pos - start;
				if (index < (size() / 2)) {
					push_front(front());
					copyAtfirst(start + 2, pos, start + 1);
					--pos;
				}
				else {
					push_back(back());
					copyAtlast(pos, finish - 2, finish - 1);
				}
				*pos = val;
				return pos;
			}
		}
		
		iterator erase(iterator pos)
		{
			assert(!empty());
			int index = pos - start;
			if (index < (size() / 2))
			{
				copyAtlast(start, pos, pos + 1);
				pop_front();
				return pos + 1;
			}
			else {
				copyAtfirst(pos + 1, finish, pos);
				pop_back();
				return pos;
			}
		}
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return *(start + pos);
		}
		iterator begin()
		{
			return start;
		}
		iterator end()
		{
			return finish;
		}
		const_iterator begin() const
		{
			return start;
		}
		const_iterator end() const
		{
			return finish;
		}
		T& front()
		{
			return *start;
		}
		const T& front() const
		{
			return *start;
		}
		T& back()
		{
			return *(finish - 1);
		}
		const T& back() const
		{
			return *(finish - 1);
		}
		size_t size() const
		{
			return finish - start;
		}
		bool empty() const
		{
			return finish == start;
		}
	private:
		void Create_Map_And_Node(size_t elementNum)
		{
			size_t nodeNum = elementNum / buffsize + 1; //计算缓冲区的大小
			map_size = nodeNum < 8 ? 8 : nodeNum + 2; //预留缓冲区，提高效率
			map = new Ptr[map_size]; //开辟map_size个缓冲区

			//计算[nstart,nfinish]的区间
			map_pointer nstart = map + (map_size - (elementNum / buffsize)) / 2;
			map_pointer nfinish = nstart + nodeNum - 1;

			//初始化这个区间
			map_pointer tmp = nstart;
			while (tmp <= nfinish)
			{
				*tmp = new T[buffsize]; //生成缓冲区
				tmp++;
			}

			start.setnode(nstart);
			start.cur = start.first;
			finish.setnode(nfinish);
			finish.cur = finish.first + (elementNum % buffsize);
		}
		void ReserveMapAtBack(size_t AddNode = 1)
		{
			if (AddNode >= (map_size - (finish.node - map))) {
				reallocMap(AddNode, false);
			}
		}
		void ReserveMapAtFront(size_t AddNode = 1)
		{
			if (AddNode >= (start.node - map)) {
				reallocMap(AddNode, true);
			}
		}
		void reallocMap(size_t AddNode, bool AllocAtFront)
		{
			size_t oldnodes = finish.node - start.node + 1; //旧的有效缓冲区大小
			size_t newnodes = oldnodes + AddNode; //新的有效缓冲区大小

			map_pointer newstart;
			size_t newmapsize = map_size + (map_size > AddNode ? map_size : AddNode) + 2; //新map的管理缓冲区个数

			map_pointer newmap = new Ptr[newmapsize]; //生成新的map数组

			newstart = newmap + (newmapsize - newnodes) / 2 + (AllocAtFront ? AddNode : 0);
			map_pointer newfinish = newstart + oldnodes - 1;

			copyAtfirst(start.node, finish.node + 1, newstart); //拷贝
			delete[] map; //释放旧空间

			map = newmap;
			map_size = newmapsize;
			start.setnode(newstart);
			finish.setnode(newfinish);

		}
		map_pointer map; //中控数组
		size_t map_size; //中控数组的长度
		iterator start; //指向第一个元素的迭代器
		iterator finish; //指向最后一个元素后一位的迭代器
	};

	template<class inputiterator, class T>
	void fill(inputiterator first, inputiterator last, const T& val)
	{
		while (first != last)
		{
			*first = val;
			++first;
		}
	}

	template<class inputiterator, class outputiterator>
	void copyAtfirst(inputiterator first, inputiterator last, outputiterator dest) //从后往前拷贝
	{
		while (first != last)
		{
			*dest = *first;
			++first;
			++dest;
		}
	}
	template<class inputiterator, class outputiterator>
	void copyAtlast(inputiterator first, inputiterator last, outputiterator dest) //从前往后拷贝
	{
		while (last != first)
		{
			--last;
			--dest;
			*dest = *last;
		}
	}
}