#pragma once
#include<assert.h>

namespace HUE
{
	template <class T>
	//list节点
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;

		list_node(const T& x = T()) //  为什么用T(): 调用其默认构造
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}

	};

	//迭代器 --- 自定义类型封装node* --- STL的精华部分
	//分类：1.原生指针 2.用自定义类型对原生指针的封装，模拟指针的行为
	//即->迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为！

	//封装list迭代器
	template<class T, class Ref, class Ptr>  //通过增加模板参数，提供多版本迭代器
	struct _list_iterator
	{
		typedef list_node<T> node; //加上模板参数才是类型，否则只是类名
		typedef  _list_iterator<T, Ref, Ptr> self;  //方便后面返回值,做参数
		node* _node; //指针

		_list_iterator(node* n)  // 提供构造函数，遍历使用
			:_node(n)
		{}

		Ref operator* ()  //提供const版本迭代器
		{
			return _node->_data;
		}

		//const 迭代器和普通迭代器的区别是什么？   一个内容可修改 ，一个内容不可被修改

		Ptr operator->()  //->重载
		{
			return &_node->_data;  //引用返回减少拷贝
		}

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

		self& operator++(int) //后置++
		{
			self tmp(*this); //拷贝构造一下
			_node = _node->_next;

			return tmp;
		}

		//那这个迭代器是浅拷贝 可以吗？ 可以呀，因为这个是node的指针，浅拷贝后指针指向同一个node是可以的。那为什么没有报错呢？ 因为我们没有提供析构函数。 
		//那为什么不需要释放节点呢？节点的指针不属于迭代器啊，没有开辟空间，只是一个工具而已，释放也得由开辟空间的对象(list)来释放

		self& operator--()
		{
			_node = _node->_prev;

			return *this;
		}

		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		bool operator ==(const self& s)
		{
			return _node == s._node;

		}
	};

	//反向迭代器
	// 适配器 -- 复用
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		Iterator _it;
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

		Reverse_iterator(Iterator it)
			:_it(it)
		{}

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

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

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

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

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


	//下面是待优化const版本迭代器相关代码,这么写代码太冗余了
	//采用增加模板参数，控制返回值不一样，实现const版本迭代器，控制对象内容本身不可修改，STL的设计真的很巧妙！
	/*template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> node;
		typedef __list_const_iterator<T> self;
		node* _node;

		__list_const_iterator(node* n)
			:_node(n)
		{}

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

		self& operator++()
		{
			_node = _node->_next;

			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;

			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;

			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};*/

	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 _list_iterator<T> iterator;   ---- T*
		//typedef const iterator const_iterator;  ----- T* const 

		// 反向迭代器适配支持
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		iterator begin()
		{
			//iterator it(_head->_next);
			//return it;  //拷贝次数太多
			//使用匿名对象返回
			return iterator(_head->_next);
		}


		//为什么const 还可以构造普通迭代器？ 语法上来说，const修饰的是：*this 。this 指向的内容是node* _head 这个指针本身，
		//即 _head 这个指针本身不能被改变，但不影响_head可以被拷贝。
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

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

		const_iterator end() const
		{
			//iterator it(_head->_next);
			//return it;
			return const_iterator(_head);
		}

		const_reverse_iterator rbegin() const
		{
			// list_node<int>*
			return const_reverse_iterator(end());
		}

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

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

		//list 构造函数
		list()
		{
			CreatHead();

		}

		list(int n, const T& value = T())
		{
			CreatHead();
			for (int i = 0; i < n; ++i)
			{
				push_back(value);
			}
		}

		//区间构造
		list(iterator first, iterator last)
		{
			CreatHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//拷贝构造
		list(const list<T>& l)
		{
			CreatHead();
			// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> tmp(l.begin(), l.end());
			swap(tmp);
		}

		//赋值重载
		list<T>& operator=(const list<T> l)
		{
			swap(l);
			return *this;
		}

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

		//list capacity
		size_t size() const
		{
			size_T size = 0;
			node* p = _head->_next;
			while (p != _head)
			{
				size++;
				p = p->_next;
			}

			return size;
		}
			
		bool empty()  const
		{
			return size() == 0;
		}

		//list access
		T& front()
		{
			assert(!empty());
			return _head->_next->_data;
		}
		const T& front() const
		{
			assert(!empty());
			return _head->_next->_data;
		}


		T& back()
		{
			assert(!empty());
			return _head->_prev->_data;
		}

		const T& back() const
		{
			assert(!empty());
			return _head->_prev->_data;
		}

		void push_back(const T& x) //复用insert，现代写法
		{
			/*node* tail = _head->_prev;
			node* new_node = new node(x);

			tail->_next = new_node;
			new_node->_prev = tail;
			new_node->_next = _head;
			_head->_prev = new_node;*/

			insert(end(), x);//尾插，哨兵节点的prev就是
		}

		void push_front(const T& x)
		{
			insert(begin(), x);//头插
		}

		void pop_back()
		{
			erase(--end());//前置--，哨兵节点的prev
		}


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

		//insert函数 pos前插入x
		//insert这里迭代器会不会失效？  不会，pos指向节点不会发生地址改变
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node; //指针
			node* prev = cur->_prev;

			node* new_node = new node(x); //堆区申请

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

		//erase函数 删除pos位置
		//erase这里迭代器失效吗 肯定失效，pos被干掉了。所以我们可以加个断言啊----谁不可以erase？-- 哨兵位头节点
		void erase(iterator pos)
		{
			assert(pos != end());  //防止删除哨兵节点

			node* next = pos._node->_next;
			node* prev = pos._node->_prev;

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;

		}

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

		void swap(list<T>& l)
		{
			node tmp = _head;
			_head = l._head;
			l._head = tmp;
		}

	private:
		void CreatHead()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		node* _head;
	};


	void print_list(const list<int>& It)
	{
		list<int>::const_iterator it = It.begin();
		while (it !=It.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

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


		print_list(It);
		//本质：模拟的int*  的行为
		list<int>::iterator it = It.begin();
		while ( it != It.end())
		{
			(*it) *= 2; //可修改内容的迭代器
			cout << *it << " ";

			++it;
		}
		cout << endl;
		It.push_front(9999);
		It.push_back(10000);

		for (auto e : It) //范围for同样适用，注意 要typedef为iterator,编译器会做这些优化
		{
			cout << e << " ";
		}
		cout << endl;

		It.pop_back();
		It.pop_front();
		for (auto e : It)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct AA
	{
		int _a1;
		int _a2;

		AA(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}
	};
		

	void test_list2()
	{
		list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));

		// AA* ptr
		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;		
			cout << it->_a1 << ":" << it->_a2 << endl;
			cout << it.operator->()->_a1 << ":" << it.operator->()->_a1 << endl;
			++it;
		}
		cout << endl;
	}
}