#define _CRT_SECURE_NO_WARNINGS 1

#pragma once

namespace stl
{
template<class T>
struct ListNode
{
	ListNode(const T& x = T())
		:_data(x)
		, _next(nullptr)
		, _prev(nullptr)
	{}

	T _data;
	ListNode<T>* _next;
	ListNode<T>* _prev;

};

template<class T, class Ref, class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	Ref operator*()
	{
		return _node->_data;
	}

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

	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==(Self& s)
	{
		return _node == s._node;
	}

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

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

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

	ListIterator(Node* node)
		:_node(node)
	{}
	Node* _node;
};

template<class T>
class List
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, T& , T*> iterator;
	typedef ListIterator<T, const T& , const T*> const_iterator;
public:
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator cbegin()
	{
		return const_iterator(_head->_next);
	}
	const_iterator cend()
	{
		return const_iterator(_head);
	}
	
	List()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Clear()
	{
		Node* cur = _head->_next;
		while (cur != _head)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_head->_next = _head;
		_head->_prev = _head;
	}

	List(const List<T>& l)
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;

		const_iterator it = l.begin();
		while (it != l.end())
		{
			PushBack(*it);
			++it;
		}
	}

	List<T>& operator=(List<T> l)
	{
		if (this != &l)
		{
			swap(_head, l._head);
		}
		return *this;
	}
	~List()
	{
		Clear();
		delete _head;
		_head = nullptr;
	}

	bool Empty()
	{
		return begin() == end();
	}
	void PushBack(const T& x)
	{
		Insert(end(), x);
	}
	void PopBack()
	{
		Erase(--end());
	}
	void PushFront(const T& x)
	{
		Insert(begin(), x);
	}

	void PopFront()
	{
		Erase(begin());
	}
	void Insert(iterator pos, const T& x)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(x);
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
	}
	iterator Erase(iterator pos)
	{
		if (pos._node == _head)
			return _head;
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		return iterator(next);
	}

private:
	Node* _head;
};
}