#include<iostream>
#include<assert.h>
//#include<algorithm>
using namespace std;

//定义结点结构
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)
	{}
};

//list迭代器
//__list_iterator<T,T&,T*>  对应的是一个普通的迭代器
//__list_iterator<T, const T&, const T*> 对应的是一个const迭代器 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;

	__list_iterator(node* node)
		:_node(node)
	{}

	//*it 解引用
	Ref operator*() 
	{
		return _node->_data;
	}


	//it->
	Ptr operator->()
	{
		return &_node->_data;
	}

	//++it  迭代器前置++，返回++后的迭代器
	Self operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//it++ 后置++返回的是++之前的值
	Self operator++(int)
	{
		Self tmp(*this);
		//_node = _node->_next;
		++(*this);

		return tmp;
	}

	//--it  迭代器前置--，返回--后的迭代器
	Self operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//it-- 后置--返回的是--之前的值
	Self operator--(int)
	{
		Self tmp(*this);
		//_node = _node->_prev;
		--(*this);

		return tmp;
	}

	//it!=end() 当前迭代器it与迭代器end()比较
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}

	//it==end() 当前迭代器it与迭代器end()比较
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
};

template<class T>
class MyList
{
	typedef __list_node<T> node;

public:
	//普通迭代器
	typedef __list_iterator<T, T&, T*> iterator;
	
	//const_iterator迭代器的实现
	typedef __list_iterator<T, const T&, const T*> const_iterator;

	//迭代器
	//begin()是双向循环链表头结点下一个位置的节点
	iterator begin()
	{
		return iterator(_head->_next);
	}

	//end()是链表最后一个节点的下一个位置，即头节点的位置
	iterator end()
	{
		return iterator(_head);
	}

	//const迭代器
	const_iterator begin()const
	{
		return const_iterator(_head->_next);
	}

	//const迭代器
	const_iterator end()const
	{
		return const_iterator(_head);
	}

	//1、带头双向循环链表，构造函数
	MyList()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	//2、析构函数，头结点也删除
	~MyList()
	{
		clear();
		delete _head;
		_head = nullptr;
	}

	//3、拷贝构造 lt2(lt1)
	MyList(const MyList<T>& lt)
	{
		//先创建一个新的只有头结点的链表
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;

		//将链表lt各结点中的数据插入新创建的链表中
		/*const_iterator it = lt.begin();
		while (it != lt.end())
		{
			push_back(*it);
			++it;
		}*/

		//也可将以上迭代器循环换成范围for循环
		for (auto e : lt)
		{
			push_back(e);
		}
	}

	//4、赋值 lt1=lt3
	/*MyList<T>& operator=(const MyList<T>& lt)
	{
		if (this != &lt)
		{
			for (auto e : lt)
				push_back(e);
		}

		return *this;
	}*/

	//5、赋值的常用写法 lt1=lt3
	MyList<T>& operator=(MyList<T> lt)
	{
		
		swap(_head, lt._head);
		return *this;
	}

	//清理链表，保留头结点
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			erase(it++);
		}
	}

	//6、尾插
	void push_back(const T& val)
	{
		/*node* tail = _head->_prev;
		node* newNode = new node(val);

		tail->_next = newNode;
		newNode->_prev = tail;

		_head->_prev = newNode;
		newNode->_next = _head;*/
		//end()是链表结尾的下一个位置，即头结点的位置
		insert(end(), val);
	}

	//2、insert函数，在pos之前插入结点newNode
	void insert(iterator pos, const T& val)
	{
		node* cur = pos._node;
		node* prev = cur->_prev;
		node* newNode = new node(val);

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

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

	//4、erase() 在指定位置删除数据
	iterator erase(iterator pos)
	{
		//注意不能删除头结点
		assert(pos != end());

		node* cur = pos._node;
		node* curPrev = cur->_prev;
		node* curNext = cur->_next;
		delete cur;

		curPrev->_next = curNext;
		curNext->_prev = curPrev;

		return iterator(curNext);
	}

	//5、尾删
	void pop_back()
	{
		//两种写法
		//erase(iterator(_head->_prev));
		erase(--end());
	}
	
	//6、头删
	void pop_front()
	{
		erase(begin());
	}

	//7、判空empty()
	bool empty()
	{
		return begin() == end();
	}

	//8、求链表的节点个数
	size_t size()
	{
		size_t count = 0;
		iterator it = begin();
		while (it != end())
		{
			++it;
			++count;
		}

		return count;
	}
	
private:
	node* _head;
};

//1、链表的尾插以及初步实现链表的迭代器
void test_list01()
{
	MyList<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

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

struct Date
{
	int _year = 0;
	int _month = 1;
	int _day = 1;
};

//2、->测试
void test_list02()
{
	MyList<Date>lt;
	lt.push_back(Date());
	lt.push_back(Date());

	MyList<Date>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
		++it;
	}
	cout << endl;
}

//3、const迭代器测试
void print_list(const MyList<int>& lt)
{
	MyList<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		//*it = 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

//4、尾插、尾删、头插、头删测试
void test_list03()
{
	MyList<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	print_list(lt);

	lt.pop_back();
	lt.pop_front();
	print_list(lt);

	lt.clear();
	lt.push_back(10);
	print_list(lt);
}

//5、拷贝构造、赋值测试
void test_list04()
{
	MyList<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	MyList<int> lt2(lt1);
	print_list(lt2);

	MyList<int> lt3;
	lt3 = lt2;
	print_list(lt3);

	lt1.erase(lt3.begin());
	print_list(lt3);

	cout << lt3.empty() << endl;
	cout << lt3.size() << endl;
}


int main()
{
	//test_list01();
	//test_list02();
	//test_list03();
	test_list04();
	

	return 0;
}