#include <iostream>
#include <cstdlib>
using namespace std;

template<class T>
class Node{
public:
    Node():next(NULL),prev(NULL){};
    Node(T d, Node<T>* p=NULL, Node<T>* n=NULL):data(d),prev(p),next(n){};
    
    T data;
    Node<T>* next;
    Node<T>* prev;
};

template<class T>
class LinkListIterator{
    typedef LinkListIterator<T>  self_type;
    typedef LinkListIterator<T>& self_ref_type;
    
    typedef Node<T>  data_type;
    typedef Node<T>* pointer_type;
    typedef Node<T>& referene_type;
    
    typedef T value_type;
public:
    LinkListIterator(pointer_type DN = NULL):directNode(DN){};
    
    value_type& operator*(){ return directNode -> data; };
    self_ref_type operator++();
    self_ref_type operator++(int){ return ++(*this);};
    
    self_ref_type operator--(){
        if(directNode != NULL){
            directNode = directNode -> prev;
            return *this;
        }
    };
    self_ref_type operator--(int){ return --(*this); };
    
    bool operator==(const self_type data) const{ return directNode == data.directNode; };
    bool operator!=(const self_type data) const{ return directNode != data.directNode; };
private:
    pointer_type directNode;
};

template<class T>
LinkListIterator<T>& LinkListIterator<T>::operator++(){
    if(directNode != NULL){
        directNode = directNode -> next;
        return *this;
    }
} 

template<class T>
class LinkList{
    friend class LinkListIterator<T>;
    typedef LinkListIterator<T> iterator_type;

    typedef Node<T>  data_type;
    typedef Node<T>* pointer_type;
    typedef Node<T>& referene_type;
    
    typedef T value_type;
    
public:
    typedef LinkListIterator<T> iterator;

    LinkList();
    LinkList(T data);
    LinkList(const LinkList<T>& rvalue);
    ~LinkList();
    const LinkList<T>& operator=(const LinkList<T>& rvalue);

    void addData(value_type data);
    void erase(value_type data);
    bool find(value_type data);
    void printData();

    iterator_type  begin(){ return iterator_type(_root); };
    iterator_type  end(){ return iterator_type(_end); };
private:
    inline void deleteAllNodes();
    inline void copyAllNodes(const LinkList<T>& rvalue);
    pointer_type _root, _end;
};

template<class T>
LinkList<T>::LinkList():_root(NULL){
    _end = new data_type;
}

template<class T>
LinkList<T>::LinkList(T data){
    _root = new data_type(data);
    _end = new data_type;
}

template<class T>
LinkList<T>::LinkList(const LinkList<T>& rvalue){
    copyAllNodes(rvalue);
}

template<class T>
const LinkList<T>&  LinkList<T>::operator=(const LinkList<T>& rvalue){
    deleteAllNodes();
    copyAllNodes(rvalue);
}

template<class T>
LinkList<T>::~LinkList(){
    pointer_type currentNode = _root, nextCurrentNode = _root;
    while(currentNode != NULL){
       nextCurrentNode = currentNode -> next;
       delete currentNode;
       currentNode = nextCurrentNode;
    }
}

template<class T>
void LinkList<T>::deleteAllNodes(){
    pointer_type currentNode = _root, nextCurrentNode = _root;
    while(currentNode != NULL){
       nextCurrentNode = currentNode -> next;
       delete currentNode;
       currentNode = nextCurrentNode;
    }
}

template<class T>
void LinkList<T>::copyAllNodes(const LinkList<T>& rvalue){
    pointer_type copyCurrentNode = rvalue._root;
    pointer_type currentNode = NULL;
    while(copyCurrentNode != NULL){
        if(currentNode!=NULL){
            pointer_type addNode = new data_type(copyCurrentNode -> data);
            currentNode -> next = addNode;
            currentNode = currentNode -> next;
        }
        else{
            currentNode = new data_type(copyCurrentNode -> data);
            _root = currentNode;
        }
        copyCurrentNode = copyCurrentNode->next;

    }
    _end = currentNode;
}


template<class T>
void LinkList<T>::addData(typename LinkList<T>::value_type data){
    if(_root==NULL){
        _root = new data_type(1);
        _root -> next = _end;
        _end -> prev = _root;
    }else{
        pointer_type addNode = new data_type(data, _end-> prev, _end);
        _end -> prev -> next = addNode;
        _end -> prev = addNode;
    }
}

template<class T>
void LinkList<T>::printData(){
    pointer_type currentNode = _root;
    while(currentNode != _end){
        cout << currentNode -> data << " ";
        currentNode = currentNode -> next;
    }
}

template<class T>
bool LinkList<T>::find(typename LinkList<T>::value_type data){
   pointer_type currentNode = _root;
   while(currentNode != _end){
       if(currentNode -> data == data) return true;
       currentNode = currentNode -> next;
   }
   return false;
}

template<class T>
void LinkList<T>::erase(typename LinkList<T>::value_type data){
    pointer_type currentNode = _root;
    while(currentNode != _end){
        if(currentNode -> data == data){
            if(currentNode != _root){
                currentNode -> prev -> next = currentNode -> next;
                currentNode -> next -> prev = currentNode -> prev;
            }
            else{
                currentNode -> prev = NULL;
                if(currentNode -> next != _end) _root = currentNode -> next;
                else _root = NULL;

            }
        }
        currentNode = currentNode -> next;
    }
}

void f(){
    LinkList<int> u;
    for(unsigned int i=0;i<10;i++) u.addData(i+1);
    
    if(u.find(10)) cout << "10 is find out!" << endl;
    else cout << "Not find" << endl;
    
    u.erase(1);

    u.erase(10);
    u.printData();
    cout << endl;

    LinkList<int> v;
    v=u;
    cout << endl;
    
    LinkList<int>::iterator iter(v.begin());
    for(;iter!=v.end();++iter){
        cout << *iter << endl;
    }
}

int main(){
    f();
    cout << endl;
    system("pause");
}