#pragma once


namespace bite
{
	//List的节点类
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_pPrve(nullptr)
			,_pNext(nullptr)
			,_val(val)
		{}
		ListNode<T>* _pPrve;
		ListNode<T>* _pNext;
		T _val;
	};
	//List的迭代器类
	template<class T,class Ref,class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T,Ref,Ptr> Self;
	public:
		ListIterator(Node* pNode = nullptr)
			:_pNode(pNode)
		{}
		ListIterator(const Self& it)
			:_pNode(it._pNode)
		{}
		Ref operator*()
		{
			return _pNode->_val;
		}
		Ptr operator->()
		{
			return &(_pNode->_val);
		}
		Self& operator++()
		{
			_pNode = _pNode->_pNext;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_pNode = _pNode->_pNext;
			return tmp;
		}
		Self& operator--()
		{
			_pNode = _pNode->_pPrve;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_pNode = _pNode->_pPrve;
			return *this;
		}
		bool operator!=(const Self& it)
		{
			return _pNode != it._pNode;
		}
		bool operator==(const Self& it)
		{
			return _pNode == it._pNode;
			
		}
	/*private:*/
		Node* _pNode;
	};
		//list类
		template<class T>
		class list
		{
			typedef ListNode<T> Node;
			
		public:
			typedef ListIterator<T, T&, T*> iterator;
			typedef ListIterator<T, const T&, const T*> const_iterator;
		public:
			//list的构造
			/*CreateHead()
			{
				_pHead = new Node(T());
				_pHead->_pPrve = _pHead;
				_pHead->_pNext = _pHead;
				_size = 0;
			}*/
			list()
			{
				CreateHead();
			}
			list(initializer_list<T> il)
			{
				CreateHead();
				for (auto& e : il)
				{
					push_back(e);
				}
			}
			list(int n, const T& value = T())
			{
				CreateHead();
				while (n--)
				{
					push_back(value);
				}
			}
			template<class iterator>
			list(iterator first, iterator last)
			{
				CreateHead();
				while (first != last)
				{
					push_back(*first);
					++first;
				}
			}
			//拷贝构造 it2(it1)
			list(const list<T>& it)
			{
				CreateHead();

				list<T> tmp(it.begin(), it.end());
				swap(tmp);
			}
			//赋值重载
			list<T>& operator=( list<T> it)
			{
				CreateHead();
				swap(it);
				return *this;
			}
			list<T>& operator=(initializer_list<T> il)
			{
				list<T> ret(il);
				CreateHead();
				swap(ret);
				return *this;
			}
			//析构
			~list()
			{
				clear();
				delete _pHead;
				_pHead = nullptr;
			}

			//迭代器
			iterator begin()
			{
				return iterator(_pHead->_pNext);
			}
			iterator end()
			{
				return iterator(_pHead);
			}
			const_iterator begin()const
			{
				return const_iterator(_pHead->_pNext);
			}
			const_iterator end()const
			{
				return const_iterator(_pHead);
			}
			//容量
			size_t size()const
			{
				return _size;
			}
			bool empty()const
			{
				return _size == 0;
			}
			//取头节点的值
			T& front()
			{
				return _pHead->_pNext->_val;
			}
			const T& front()const
			{
				return _pHead->_pNext->_val;
			}
			//取尾节点的值
			T& back()
			{
				return _pHead->_pPrve->_val;
			}
			const T& back()const
			{
				return _pHead->_pPrve->_val;
			}
			//增删查改
			void push_back(const T& val)
			{
				insert(end(), val);
			}
			void pop_back()
			{
				erase(--end());
			}
			void push_front(const T& val)
			{
				insert(begin(), val);
			}
			void pop_front()
			{
				erase(begin());
			}
			// 在pos位置前插入值为val的节点
			iterator insert(iterator pos, const T& val)
			{
				Node* newnode = new Node(val);
				Node* cur = pos._pNode;
				Node* prve = cur->_pPrve;

				prve->_pNext = newnode;
				newnode->_pPrve = prve;
				newnode->_pNext = cur;
				cur->_pPrve = newnode;
				++_size;
				return iterator(newnode);
			}
			// 删除pos位置的节点，返回该节点的下一个位置
			iterator erase(iterator pos)
			{
				assert(pos != end());
				Node* prve = pos._pNode->_pPrve;
				Node* next = pos._pNode->_pNext;

				prve->_pNext = next;
				next->_pPrve = prve;

				delete pos._pNode;
				--_size;

				return iterator(next);
			}
			//清除链表节点
			void clear()
			{
				iterator it = begin();
				while (it != end())
				{
					it = erase(it);
				}
			}
			void swap(list<T>& it)
			{
				std::swap(_pHead, it._pHead);
				std::swap(_size, it._size);
			}

		private:
			void CreateHead()
			{
				_pHead = new Node(T());
				_pHead->_pPrve = _pHead;
				_pHead->_pNext = _pHead;
				_size = 0;
			}
			Node* _pHead;
			size_t _size;
		};
	
	void test_list1()
	{
		list<int> it;
		it.push_back(1);
		it.push_back(2);
		it.push_back(3);
		it.push_back(4);
		it.push_front(10);
		it.push_front(20);
		it.push_front(30);
		it.push_front(40);
		list<int>::iterator It = it.begin();
		while (It != it.end())
		{
			cout << *It << " ";
			++It;
		}
		cout << endl;

		it.pop_back();
		it.pop_back();
		it.pop_front();
		it.pop_front();
		for (auto e: it)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_list2()
	{
		list<int> it;
		it.push_back(1);
		it.push_back(2);
		it.push_front(10);
		it.push_front(20);
		for (auto e : it)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> it1(4,1);
		for (auto e : it1)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> it2(it);
		for (auto e : it2)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> it3;
		it3 = it1;
		for (auto e : it3)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_list3()
	{
		list<int> it;
		it.push_back(1);
		it.push_back(2);
		it.push_front(10);
		it.push_front(20);
		cout << it.back() << endl;
		cout << it.front() << endl;
		cout << it.size() << endl;

		for (auto e : it)
		{
			cout << e << " ";
		}
		cout << endl;
		it.clear();
		for (auto e : it)
		{
			cout << e << " ";
		}
		cout << endl;


	}
	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) += 2; // const迭代器内容不能被修改不能写
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);

		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			(*it) += 2; // 可以写
			cout << *it << " ";
			++it;
		}
		cout << endl;

		print_list(lt1);
	}
	void test_list5()
	{
		list<int> lt1 = { 1,2,3,4,5,6,7,8,9,10 };
		
		for (const auto& e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt2;
		lt2 = { 1,2,3,4,5,6,7,8 };
		for (const auto& e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
		
	}
}