#pragma once

namespace list_realize
{
	template<class T>
	struct List_node
	{
		List_node<T>* _next; // 前驱指针
		List_node<T>* _prev; // 后继指针
		T _data; // 记录存放数据

		List_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
	};

	// 普通迭代器
	//template<class T>
	//struct __list_iterator
	//{
	//	typedef List_node<T> node;
	//	node* _pnode;

	//	// 构造函数
	//	__list_iterator(node* p)
	//		:_pnode(p)
	//	{}

	//	T& operator*()
	//	{
	//		return _pnode->_data;
	//	}

	//	T* operator->()
	//	{
	//		return &_pnode->_data;
	//		return &(operator*());//返回结点指针所指结点的数据的地址
	//	}

	//	__list_iterator<T>& operator++()
	//	{
	//		_pnode = _pnode->_next;
	//		return *this;
	//	}

	//	__list_iterator<T> operator++(int)
	//	{
	//		__list_iterator tmp(*this);
	//		_pnode = _pnode->_next;
	//		return tmp;
	//	}

	//	__list_iterator<T>& operator--()
	//	{
	//		_pnode = _pnode->_prev;
	//		return *this;
	//	}

	//	__list_iterator<T> operator--(int)
	//	{
	//		__list_iterator tmp(*this);
	//		_pnode = _pnode->_prev;
	//		return tmp;
	//	}

	//	bool operator==(const __list_iterator<T>& it)
	//	{
	//		return _pnode == it._pnode;
	//	}

	//	bool operator!=(const __list_iterator<T>& it)
	//	{
	//		return _pnode != it._pnode;
	//	}
	//};

	// const迭代器 跟普通迭代器的区别：遍历，不能用*it修改数据
	/*template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> node;
		node* _pnode;

		__list_const_iterator(node* p)
			:_pnode(p)
		{}

		const T& operator*()
		{
			return _pnode->_data;
		}

		__list_const_iterator<T>& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		__list_const_iterator<T> operator++(int)
		{
			__list_const_iterator tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		__list_const_iterator<T>& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		__list_const_iterator<T> operator--(int)
		{
			__list_const_iterator tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		bool operator!=(const __list_const_iterator<T>& it)
		{
			return _pnode != it._pnode;
		}
	};*/

	// SGI STL库的迭代器 ——> 大佬的写法
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef List_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> Self;

		__list_iterator(node* pnode)
			:_pnode(pnode)
		{}

		/*
		 *it2 = it1 浅拷贝
		 * 拷贝构造和负值重载是否需要我们自己实现
		 * 析构函数呢？ 迭代器是借助节点的指针访问修改链表
		 * 节点属于链表，不属于迭代器，所以它不负责释放
		 * 拷贝构造、负值重载我们都不需要实现，默认生成的即可
		*/

		Ref operator*()
		{
			return _pnode->_data;
		}

		Ptr operator->()
		{
			return &_pnode->_data;
			//return &(operator*());
		}

		// ++it
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		// it++
		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		// ++it
		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		// it--
		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		bool operator!=(const Self& it) const
		{
			return _pnode != it._pnode;
		}

		bool operator==(const Self& it) const
		{
			return _pnode == it._pnode;
		}

		node* _pnode;
	};

	template <class Iterator, class Ref, class Ptr>
	class reverse__list_iterator
	{
		typedef reverse__list_iterator<Iterator, Ref, Ptr> Self;
	public:
		reverse__list_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator prev = _it;
			return *--prev;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self& operator++(int)
		{
			_it--;
			return *this;
		}

		Self& operator--(int)
		{
			_it++;
			return *this;
		}

		bool operator!=(const Self& rit) const
		{
			return _it != rit._it;
		}

		bool operator==(const Self& rit) const
		{
			return _it == rit._it;
		}

	private:
		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef List_node<T> node;
	public:
		/*typedef __list_iterator<T> iterator;
		typedef __list_iterator<T> const_iterator;*/

		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		typedef reverse__list_iterator<iterator, T&, T*> reverse_iterator;
		typedef reverse__list_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		iterator begin()
		{
			/*iterator it(_head->_next);
			return it;*/
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		reverse_iterator rbegin()
		{
			/*iterator it(_head->_next);
			return it;*/
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			/*iterator it(_head->_next);
			return it;*/
			return reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return reverse_iterator(begin());
		}

		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		// 构造函数
		list()
		{
			empty_initialize();
		}

		list(size_t n, const T& val = T())
		{
			empty_initialize();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		template <class InputIterator> 
		list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}


		// 拷贝构造 lt2(lt1)
		// 传统写法
		//list(const list<T>& lt)
		////list(const list& lt) // 不建议，不规范
		//{
		//	empty_initialize();

		//	for (const auto& e : lt)
		//	{
		//		push_back(e);
		//	}
		//}
		// 现代写法
		list(const list<T>& lt)
		{
			empty_initialize();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		
		// 赋值运算符重载
		// 传统写法
		/*list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/
		// 现代写法
		/*list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				list<T>& tmp(lt.begin(), lt.end());
				swap(tmp);
			}
			return *this;
		}*/
		// 简化
		list<T> operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		// 析构函数
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		size_t size() const
		{
			return _size;
		}
		/*size_t size() const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}
			return count;
		}*/

		void resize(size_t newsize, const T& val = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(val);
					oldsize++;
				}
			}
		}

		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back() const
		{
			return _head->_prev->_val;
		}

		bool empty() const 
		{
			return _head->_next == _head;
			//return _size == 0;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		 void push_back(const T& val)
		 {
			node* newnode = new node(val);
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			_head->_prev = newnode;
			newnode->_next = _head; 
			++_size;
			//insert(end(), val);
		 }

		 void push_front(const T& val)
		 {
			 insert(begin(), val);
		 }

		 void pop_front()
		 {
			 erase(begin());
		 }

		 void pop_back()
		 {
			 erase(--end());
		 }

		 iterator insert(iterator pos, const T& val)
		 {
			 node* newnode = new node(val);
			 node* cur = pos._pnode;
			 node* prev = cur->_prev;
			 prev->_next = newnode;
			 newnode->_prev = prev;
			 newnode->_next = cur;
			 cur->_prev = newnode;
			 ++_size;
			 return iterator(newnode);
		 }

		 iterator erase(iterator pos)
		 {
			 node* cur = pos._pnode;
			 node* prev = cur->_prev;
			 node* next = cur->_next;
			 prev->_next = next;
			 next->_prev = prev;
			 delete cur;
			 cur = nullptr;
			 _size--;
			 return iterator(next);
		 }

	private:
		node* _head;
		size_t _size;
	};

	// const T* p1;
	// T* const p2;
	// const迭代器类似p1的行为，保护指向的对象不被修改，迭代器本身可以修改
	//void print_list(const list<int>& lt)
	//{
	//	// const list<int>::iterator cit = lt.begin();
	//	// 不符合const迭代器的行为，因为他保护迭代器本身不能修改，那么我们也就不能++迭代器
	//}

	// 对模拟实现的list进行测试
	// 正向打印链表
	template<class T>
	void PrintList(const list<T>& lt)
	{
		auto it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void list_test1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_back();
		lt.pop_back();
		lt.pop_back();
	}

	void list_test2()
	{
		list<int> lt;
		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);

		//list<int>::iterator pos = find(lt.begin(), lt.end(), 30);
		list<int>::iterator pos = lt.begin();
		if (pos != lt.end())
		{
			// insert之后，迭代器是否失效? 不失效
			lt.insert(pos, 3);
		}
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << *pos << endl;
		(*pos)++;
		cout << endl;

		 // 删除导致迭代器失效 ：形成野指针
		lt.erase(pos);
		cout << *pos << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void list_test3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(5);
		lt.push_front(6);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << lt.size() << endl;

		list<int> lt1(lt);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.clear();

		PrintList(lt);

		list<int> lt2;
		lt2.push_back(10);
		lt2.push_back(20);
		lt2.push_back(30);
		lt2.push_back(40);
		cout << lt2.size() << endl;

		lt = lt2;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void list_test4()
	{
		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;

		PrintList(lt1);
	}

	struct Pos
	{
		int _row;
		int _col;

		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};

	void print_list(const list<Pos>& lt)
	{
		list<Pos>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//it->_row++;

			cout << it->_row << ":" << it->_col << endl;

			++it;
		}
		cout << endl;
	}

	void list_test5()
	{
		list<Pos> lt;
		Pos p1(1, 1);
		lt.push_back(p1);
		lt.push_back(p1);
		lt.push_back(p1);
		lt.push_back(Pos(2, 2));
		lt.push_back(Pos(3, 3));

		// int* p  -> *p
		// Pos* p  -> p->
		list<Pos>::iterator it = lt.begin();
		//list<Pos>::iterator it2 = it;
		while (it != lt.end())
		{
			it->_row++;

			//cout << (&(*it))->_row << ":" << (*it)._col << endl;
			cout << it->_row << ":" << it->_col << endl;
			//cout << it.operator->()->_row << ":" << it->_col << endl;

			++it;
		}
		cout << endl;

		print_list(lt);
	}
}