// 双向线性链表容器
#include <cstring>
#include <iostream>
#include <stdexcept>
using namespace std;

// 链表类模板
template<typename T>
class List
{
public:
	// 构造、析构、支持深拷贝的拷贝构造和拷贝赋值
	List(void) : m_head(NULL), m_tail(NULL) {}
	~List(void)
	{
		clear();
	}

	List(List const& that) : m_head(NULL), m_tail(NULL)
	{
		for (Node* node = that.m_head; node != NULL;
					node = node->m_next)
			push_back(node->m_data);
	}

	List& operator = (List const& rhs) 
	{
		if (&rhs != this)
		{
			List list(rhs);
			swap(m_head, list.m_head);
			swap(m_tail, list.m_tail);
		}
		return *this;
	}

	// 获取首元素
	T& front(void) 
	{
		if (empty())
			throw underflow_error("链表下溢！
");	//下溢异常
		return m_head->m_data;
	}

	T const& front(void) const 
	{
		return const_cast<List*>(this)->front();
	}

	// 向首部压入
	void push_front(T const& data) 
	{
		m_head = new Node(data, NULL, m_head);
		if (m_head->m_next != NULL)
			m_head->m_next->m_prev = m_head;
		else
			m_tail = m_head;
	}

	// 从首部弹出
	void pop_front(void) 
	{
		if (empty())
			throw underflow_error("链表下溢！
");
		Node* next = m_head->m_next;
		delete m_head;
		m_head = next;
		if (m_head)
			m_head->m_prev = NULL;
		else
			m_tail = NULL;
	}

	// 获取尾元素
	T& back(void)
	{
		if (empty())
			throw underflow_error("链表下溢！");
		return m_tail->m_data;
	}

	T const& back(void) const 
	{
		return const_cast<List*>(this)->back();
	}
	
	// 向尾部压入
	void push_back(T const& data) 
	{
		m_tail = new Node(data, m_tail);
		if (m_tail->m_prev != NULL)
			m_tail->m_prev->m_next = m_tail;
		else
			m_head = m_tail;
	}

	// 从尾部弹出
	void pop_back(void) 
	{
		if (empty())
			throw underflow_error("链表下溢！
");
		Node* prev = m_tail->m_prev;
		delete m_tail;
		m_tail = prev;
		if (m_tail != NULL)
			m_tail->m_next = NULL;
		else
			m_head = NULL;
	}

	// 删除全部匹配元素
	void remove(T const& data) 
	{
		for (Node* node = m_head, *next; node != NULL; 
				node = next)
		{
			next = node->m_next;
			if (equal(data, node->m_data))
			{
				if (node->m_prev != NULL)
					node->m_prev->m_next = node->m_next;
				else
					m_head = node->m_next;

				if (node->m_next)
					node->m_next->m_prev = node->m_prev;
				else
					m_tail = node->m_prev;

				delete node;
			}
		}
	}

	// 清空
	void clear(void) 
	{
		while (!empty())
			pop_back();
	}

	// 判空
	bool empty(void) const 
	{
		return NULL == m_head &&  NULL == m_tail;
	}

	// 大小
	size_t size(void) const 
	{
		size_t nodes = 0;
		for (Node* node = m_head; node != NULL;
				node = node->m_next)
			++nodes;
		return nodes;
	}

	// 下标运算符————SHIT!
	T& operator[] (size_t i)
	{
		for (Node* node = m_head; node != NULL;
				node = node->m_next)
			if (0 == i--)
				return node->m_data;
		throw out_of_range("下标越界！");
	}

	T const& operator[] (size_t i) const
	{
		return const_cast<List&>(*this)[i];
	}

	// 插入输出流
	friend ostream& operator << (ostream& os, 
				List const& list) 
	{
		for (Node* node = list.m_head; node != NULL;
				node = node->m_next)
			os << *node;
		return os;
	}

private:
	// 节点类模板
	class Node
	{
	public:
		Node(T const& data, Node* prev = NULL, Node* next = NULL)
			: m_data(data), m_prev(prev), m_next(next) {}
		friend ostream& operator << (ostream& os, Node const& node)
		{
			return os << ‘[‘ << node.m_data << ‘]‘;
		}
		T	  m_data;	// 数据
		Node* m_prev;	// 前指针
		Node* m_next;	// 后指针
	};

	// 推断元素是否相等
	bool equal(T const & a, T const& b) const
	{
		return a == b;
	}

	Node* m_head;	// 头指针
	Node* m_tail;	// 尾指针
public:
	// 正向迭代器
	class Iterator
	{
	public:
		Iterator(Node* head = NULL, Node* tail = NULL, Node* node = NULL) 
			: m_head(head), m_tail(tail), m_node(node) {}
		bool operator == (Iterator const& rhs) const
		{
			return m_node == rhs.m_node;
		}

		bool operator != (Iterator const& rhs) const
		{
			return ! (*this == rhs);
		}

		Iterator& operator++ (void)
		{
			if (m_node)
				m_node = m_node->m_next;
			else
				m_node = m_head;
			return *this;
		}
		
		Iterator const operator++ (int)
		{
			Iterator old = *this;
			++*this;
			return old;
		}

		Iterator& operator-- (void)
		{
			if (m_node)
				m_node = m_node->m_prev;
			else
				m_node = m_tail;
			return *this;
		}
		
		Iterator const operator-- (int)
		{
			Iterator old = *this;
			--*this;
			return old;
		}

		T& operator* (void) const
		{
			return m_node->m_data;
		}

		T* operator->(void) const
		{
			return &**this;
		}
	private:
		Node* m_head;
		Node* m_tail;
		Node* m_node;
		friend class List;
	};

	// 获取起始正向迭代器————指向第一个元素
	Iterator begin(void)
	{
		return Iterator(m_head, m_tail, m_head);
	}

	// 获取终止正向迭代器————指向最后一个元素的下一个位置
	Iterator end(void)
	{
		return Iterator(m_head, m_tail);
	}

	// 在正向迭代器前插入，返回指向新插入元素的迭代器
	Iterator insert(Iterator loc, T const& data)
	{
		if (loc == end())
		{
			push_back(data);
			return Iterator(m_head, m_tail, m_tail);
		}
		else
		{
			Node* node = new Node(data, loc.m_node->m_prev, loc.m_node);
			if (node->m_prev)
				node->m_prev->m_next = node;
			else
				m_head = node;
			node->m_next->m_prev = node;
			return Iterator(m_head, m_tail, node);
		}
	}

	// 删除迭代器所指向的元素。并返回该元素之后的迭代器
	Iterator erase(Iterator loc)
	{
		if (loc == end())
			throw invalid_argument("无效參数！");
		if (loc.m_node->m_prev)
			loc.m_node->m_prev->m_next = loc.m_node->m_next;
		else
			m_head = loc.m_node->m_next;
		if (loc.m_node->m_next)
			loc.m_node->m_next->m_prev = loc.m_node->m_prev;
		else
			m_tail = loc.m_node->m_prev;
		Node* next = loc.m_node->m_next;
		delete loc.m_node;
		return Iterator(m_head, m_tail, next);
	}

	// 常正向迭代器
	// 反向迭代器
	// 常反向迭代器

};

// 针对char const* 类型的成员特化版本号
template<>
bool List<char const*>::equal(char const* const& a, char const* const& b) const
{
	return (0 == strcmp(a, b));
}