#pragma once
# include<iostream>
# include<assert.h>
using namespace std;

namespace wzf
{
	template<class T>
	struct __list_node
	{
		__list_node<T>* _prev;
		__list_node<T >* _next;
		T _data;

		__list_node(const T& x = T()) // 要给缺省值。因为头节点不好给值，用默认的初始值
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}

	};

	// 迭代器 (通过三个模版参数，来控制调用的是const迭代器还是非const的迭代器)
	// 【要注意不是迭代器这个类型的对象为const对象】
	// __list_iterator<T, T&, T*> -> iterator
	// __list_iterator<T, const T&, const T*> -> const_iterator
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		Node* _node; // 迭代器中的_node成员变量，存储着目前迭代器所指向的节点。

		// 这两个重命名是为了反向迭代器的实现
		typedef Ref Ref;
		typedef Ptr Ptr;


		__list_iterator(Node* node = nullptr)
			:_node(node)
		{}
		
		//返回Ref，const就返回const，非const返回非const 
		Ref operator*()
		{
			return _node->_data; // this->_node->_data;
		}

		// Ptr控制返回的是const属性还是非const
		Ptr operator->()
		{
			return &_node->_data;
		}

		// 前置++
		Self& operator++() 
		{
			_node = _node->_next;
			return *this;
		}

		// 后置++
		Self& operator++(int) // 加这个int才能让编译器知道这个是后置++的重载
		{
			/*__list_iterator<T> tmp = *this;
			_node = _node->_next;
			return tmp; */
			// 考虑用代码复用
			Self tmp(this->_node); // Self tmp(*this); 
			// 如果不实现拷贝构造，传*this去调用系统默认的拷贝构造也可以实现，但是是浅拷贝，要注意实际是否会出错
			++(*this);
			return tmp;
		}

		// 前置--
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// 后置--
		Self& operator--(int)
		{
			/*__list_iterator<T> tmp = *this;
			_node = _node->_prev; 
			return tmp; */
			// 考虑用代码复用
			Self tmp(this->_node);
			--(*this);
			return tmp;
		}

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

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

	};

	// 反向迭代器 (借助正向迭代器实现)
	template<class iterator>
	struct Reverse_list_iterator
	{
		// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
		typedef typename iterator::Ref Ref;
		typedef typename iterator::Ptr Ptr;
		typedef Reverse_list_iterator<iterator> Self;

		iterator _it; // 给一个成员变量是 正向迭代器类型的

		// 构造函数
		Reverse_list_iterator(iterator it)
			:_it(it)
		{}

		// 能够具有指针类似行为的* 和 ->的重载
		Ref operator*()
		{
			iterator temp(_it);
			--temp; // 对于反向迭代器来说，正向迭代器的迭代器整体往后移动一次，才能正常使用。具体可以画图
			return *temp;
		}

		Ptr operator->()
		{
			//return &(operator*()); // 让自己去调用*拿到存储的数据T

			return &(_it._node)->_data; //等价于上面
		}

		// 具备移动能力，对++，--等运算符进行重载
		Self& operator++()
		{
			--_it; // 反向迭代器的++就是正向的--
			return *this;
		}

		Self& operator++(int)
		{
			Self tmp(this->_it); // 也可以Self tmp(*this);
			--_it;
			return tmp;
		}

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

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

		// 具备相比的能力
		bool operator!=(const Self& rit) const
		{
			return _it != rit._it;
		}

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

	};

	template<class T>
	class list // 带头双向循环链表
	{
		typedef __list_node<T> Node;

	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef Reverse_list_iterator<iterator> reverse_iterator;
		typedef Reverse_list_iterator<const_iterator> const_reverse_iterator;

		// 正向迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head); //list的最后一个数据的下一个位置就是哨兵位
		}

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

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

		// 反向迭代器
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

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

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

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

		// 构造函数
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 拷贝构造
		list(const list<T>& l)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			// 遍历l，进行深拷贝
			const_iterator it = l.begin();
			while (it != l.end())
			{
				push_back(*it);
				++it;
			}
			// 要想代码简洁一点。可以用范围for，反正支持迭代期间就能支持范围for
		}

		//// 赋值运算符重载
		//list<T>& operator=(const list<T>& l)
		//{
		//	// 防止自己给自己赋值
		//	if (this != &l)
		//	{
		//		// 先清除掉自身，清除完再尾插。
		//		clear(); // 不清除会内存泄漏。

		//		// 直接用范围for。
		//		for (auto e : l)
		//			push_back(e);
		//	}

		//	return *this;
		//}

		// 赋值运算符——现代写法
		list<T>& operator=(list<T> l) // l通过拷贝构造就是我们要的
		{
			swap(_head, l._head); // 交换一下，把我们不要的给l，结束该作用域l会调用析构函数来销毁，清除我们不要的数据。
			return *this;
		}

		// 析构函数
		~list()
		{
			clear(); // 除了头节点，其他节点都已经释放了。
			delete _head; // 释放头节点
			_head = nullptr;
		}

		// clear要注意保留头节点(哨兵位)，因为clear之后可能继续插入数据。
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++); // ++的处理后，该迭代器不会失效
			}
		}

		void push_back(const T& x)
		{
			/*
			// 无论该链表是否有节点，下面这段代码都能完成任务。
			Node* tail = _head->_prev;
			Node* newnode = new Node(x); // 数据已经插入节点了
			// 接下来要做的就是处理节点之间的链接关系
			newnode->_next = _head;
			newnode->_prev = tail; 
			tail->_next = newnode;
			_head->_prev = newnode;*/

			// 实现insert了之后，可以代码复用
			insert(end(), x);
		}

		void pop_back()
		{
			// 用erase代码复用
			erase(--end());
		}

		void push_front(const T& x)
		{
			// 可以和push_back一样，常规实现，也可以用insert代码复用.
			insert(begin(), x);
		}

		void pop_front()
		{
			// 代码复用
			erase(begin());
		}

		void insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x); // 创建要插入的节点
			Node* cur = pos._node; // cur指向pos位置的节点
			Node* prev = cur->_prev; // prev指向pos位置的上一个节点

			cur->_prev = newnode;
			prev->_next = newnode;

			newnode->_next = cur;
			newnode->_prev = prev;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end()); // 不能删除哨兵位
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			iterator ret = ++pos; // 要返回pos的下一个节点，因为删除该位置的节点后pos会失效。

			delete cur; // cur是一个指针类型，指向节点（结构体）的指针
			cur = nullptr;

			return ret;
		}

	private:
		Node* _head; 
	};


	void test_list1()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);

		list<int>::iterator it = l.begin();
		while (it != l.end())
		{
			(*it)++;
			cout << *it << " ";
			++it;
		}
		cout << endl; // 2 3 4 
	}

	struct Date
	{
		int _year = 1;
		int _month = 10;
		int _day = 31;
	};

	// 迭代器的->和*的测试
	void test_list2()
	{
		list<Date> ld;
		ld.push_back(Date());
		ld.push_back(Date());

		list<Date>::iterator it = ld.begin();
		while (it != ld.end())
		{
			// ->的重载返回的是T*，在这里就是it.operator->(),返回Date*，因此这里本来应该是it->->_day,
			// 但是为了其可读性，编译器特殊处理了。
			cout << it->_day << " " << it->_month << " " << (*it)._day; // 实际上更喜欢用it->_day
			cout << endl;
			it++;
		}
	}

	template<class T>
	void print_list(const list<T>& l)
	{
		// l是const对象，因此cit需要是const的迭代器
		auto cit = l.begin();
		//cout << typeid(cit).name() << endl; 
		// 查看cit的类型—— struct wzf::__list_iterator<int,int const & __ptr64,int const * __ptr64>

		while (cit != l.end())
		{
			cout << *cit << " ";
			++cit;
		}
		cout << endl;
	}

	// const的正向迭代器的测试
	void test_list3()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_back(4);

		print_list(l);
	}

	// 测试insert和erase
	void test_list4()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(4);

		list<int>::iterator pos = l.end();
		l.insert(--pos, 3);
		print_list(l);

		l.insert(++pos, 5); // 此时pos指向哨兵位
		print_list(l);

		l.erase(--pos);
		print_list(l); // 1 2 3 4

		// erase要能解决迭代器失效的问题
		// list只会在删除节点的时候迭代器失效，插入的时候不会
		list<int>::iterator it = l.begin();
		while (it != l.end())
		{
			it = l.erase(it);
			//l.erase(it++);
		}
		
		print_list(l);
	}

	// 测试pop_back和pop_front
	void test_list5()
	{
		list<int> l;
		l.push_back(2);
		l.push_front(1);
		l.push_back(3);
		l.push_back(4);

		l.pop_back();
		print_list(l);

		l.pop_front();
		print_list(l);
	}

	// 测试拷贝构造
	void test_list6()
	{
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		print_list(l1);

		list<int> l2(l1); // 拷贝构造
		print_list(l2);
		
		// 要先程序不崩溃，要自己实现拷贝构造，实现深拷贝，而不是浅拷贝。这是老生常谈的问题了。
	}

	// 测试=的重载
	void test_list7()
	{
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		print_list(l1);

		list<int> l2;
		l2 = l1;
		print_list(l2);

		// 要支持连等
		list<int> l3;
		l3 = l2 = l1;
		print_list(l3);
	}

	// 测试反向迭代器
	void print_rever_list(const list<int>& l)
	{
		list<int>::const_reverse_iterator crit = l.rbegin();
		while (crit != l.rend())
		{
			cout << *crit << " ";
			++crit;
		}
		cout << endl;
	}

	void test_list8()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_back(4);

		list<int>::reverse_iterator rit = l.rbegin();
		while (rit != l.rend())
		{
			cout << *rit << " ";
			rit++;
		}
		cout << endl;

		print_rever_list(l);
	}

	// 测试存储的数据类型T是自定义类型的情况下，反向迭代器的->测试
	void test_list9()
	{
		list<Date> ld;
		ld.push_back(Date());
		ld.push_back(Date());
		ld.push_back(Date());

		list<Date>::reverse_iterator rit = ld.rbegin();
		while (rit != ld.rend())
		{
			cout << rit->_year << "/" << rit->_month << "/" << (*rit)._day;
			cout << endl;
			++rit;
		}
		cout << endl;
	}
}