#pragma once

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


template<class T>
struct __ListNode
{
    __ListNode<T>* _prev;
    __ListNode<T>* _next;
    T _data;

    __ListNode(const T&x)
        :_data(x)
        , _prev(NULL)
        , _next(NULL)
    {}
};

template<class T,class Ref,class Ptr>
struct __ListIterator
{
    typedef __ListNode<T> Node;
    typedef __ListIterator<T, Ref, Ptr> Self;
    
    __ListIterator(Node* node)
        :_node(node)
    {}

    __ListIterator()
    {}

        Node* _node;

        Ref operator*()
        {
            return _node->_data;
        }
        
        Ptr operator->()
        {
            return &_node->_data;
        }
        
        bool operator==(const Self&s)const
        {
            return _node == s._node;
        }

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

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

        Self& operator++(int)
        {
            Self temp(_node);
            _node = _node->_next;
            return *this;
        }

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

        Self& operator--(int)
        {
            Self tmp(_node);
            _node = _node->_prev;
            return *this;
        }
};

template<class T>
class List
{
    typedef __ListNode<T> Node;
public:
    typedef __ListIterator<T, T&, T*> Iterator;   //迭代器
    typedef __ListIterator<T, const T&, const T*> ConstIterator;   //const迭代器

    Node* Buynode(const T&x)
    {
        Node* node = new Node(x);
        return node;
    }

    List()
    {
        _head = Buynode(T());
        _head->_next = _head;
        _head->_prev = _head;
    }

    //void PushBack(const T&x)
    //{
    //    Node* tail = _head->_prev;
    //    Node* tmp = Buynode(x);

    //    tail->_next = tmp->_next;
    //    tmp->_prev = tail;

    //    tmp->_prev = tail;
    //    tmp->_next = _head;
    //    //    //    tail->_next = tmp;
    //    //    //    tmp->_prev = tail;
    //    //
    //    //    //    tmp->_next = _head;
    //    //    //    _head->_prev = tmp;
    //}

    void PushBack(const T&x)
    {
        Insert(End(),x);
    }

    void PushFront(const T&x)
    {
        Insert(Begin(), x);
    }

    void Pop()
    {
        Erase(--End());
    }

    void PopFront()
    {
        Erase(Begin());
    }

    void Insert(Iterator pos,const T&x)   //在pos前面插入
    {
        Node* cur = pos._node;
        Node* prev = cur->_prev;  //在prev后面插入

        Node* tmp = Buynode(x);
        prev->_next = tmp->_next;
        tmp->_prev = prev;

        prev->_next = tmp;
        tmp->_next = cur;
        //        tmp->_next = cur;
        //        cur->_prev = tmp;
        //
        //        prev->_next = tmp;
        //        tmp->_prev = prev;
    }

    void Erase(Iterator pos)  //在pos前面删除
    {
        assert(pos != End());
        Node* cur = pos._node->_prev;  //要删除的元素
        Node* prev = cur->_prev;
        
        prev->_next = cur->_next;
        prev->_next = prev;
        delete cur;
    }

    Iterator Begin()
    {
        return Iterator(_head->_next);
    }

    Iterator End()
    {
        return Iterator(_head);
    }
private:
    Node* _head;
};


void main()
{
    //TestList();
    List<int> l;

    l.PushBack(1);
    l.PushBack(2);
    l.PushBack(3);
    l.PushBack(4);

    List<int>::Iterator it = l.Begin();
    while (it != l.End())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

模拟实现STL中的list