#include <iostream>
using namespace std;

template <class T> class Chain;

template <class T>
class ChainNode{
    friend class Chain <T>;
    public:
        ChainNode(T element, ChainNode<T>* next = NULL);
    private:
        T data;
        ChainNode<T>* link;
};

template <class T>
class Chain{
    public:
        Chain(): first(NULL){}  //empty constructor
        void insertAtBack(const T & value);
        void insertAtFront(const T & value);
        void deletefromBack();
        void deletefromFront();
        void printAll();
        T getFisrtValue(){
            return first->data;
        }
        class ChainIterator{
            public:
                // constructor
                ChainIterator(ChainNode<T>* startNode = 0){
                    current = startNode;
                }
                // dereference
                T& operator*()const
                    {return current->data;} // 取值,再取址
                T* operator->()const
                    {return &current->data;} // 取址,再取值
                T getValue(){
                    return current->data;
                }

                // equality verifying
                bool operator!=(const ChainIterator right)const
                    { return current != right.current; }
                bool operator==(const ChainIterator right)const
                    { return current == right.current; }

                // adding up
                ChainIterator operator++(){ // 放前面的
                    current = current->link;
                    return current; //回傳加之後的值
                }
                ChainIterator operator++(int){ // 放後面的
                    ChainIterator old = *this;
                    current = current-> link;
                    return old; //回傳加之前的值
                }

            private:
                ChainNode<T>* current;
        };
        ChainIterator begin(){
            return ChainIterator(first);
        }
        ChainIterator end(){
            return ChainIterator(0);
        }
        ~Chain();
    private:
        ChainNode<T>* first;
};

int main(){
    Chain<int> myChainInt;
    myChainInt.insertAtBack(10);
    myChainInt.insertAtBack(20);
    myChainInt.insertAtBack(20);
    myChainInt.insertAtBack(30);
    myChainInt.insertAtBack(40);

    cout << myChainInt.getFisrtValue() << endl;

    Chain<int>::ChainIterator it = myChainInt.begin();
    while (it != myChainInt.end()){
        //int tmpValue = *it;
        cout << it.getValue() << " ";
        it++;
    }
    cout << endl;

    it = myChainInt.begin();
    while (it != myChainInt.end()){
        cout << *it << " ";
        it++;
    }
    cout << endl;


}

template <class T>
ChainNode<T>::ChainNode( T element, ChainNode<T>* next): data(0), link(NULL)
{
    data = element;
    link = next;
}

template <class T>
void Chain<T>::insertAtBack(const T& value){
    if(first){
        ChainNode<T>* tmpPtr = new ChainNode<T>(value,0);
        ChainNode<T>* last = first;
        while(last->link != NULL)
            last = last->link;
        last->link = tmpPtr;
    }else{
        first  = new ChainNode<T>(value,0);
    }
}
template <class T>
void Chain<T>::insertAtFront(const T& value){
    ChainNode<T>* tmpPtr = new ChainNode<T>(value,0);
    if(first){
        tmpPtr->link = first;
        first = tmpPtr;
    }else{
        first  = tmpPtr;
    }
}
template <class T>
void Chain<T>::deletefromBack(){
    T value;
    // get the mry location of the last node
    if (first){
        ChainNode<T>* last = first;
        while(last->link != NULL){
            last = last->link;
        }// end while


        if(first == last){
            value = last->data;
            delete last;
            first = NULL;
            cout << value << " is removed" << " and nothing remained"<< endl;
        }else{
            ChainNode<T>* previous = first;
            while(previous->link != last){
                previous = previous->link;
            }

            previous->link = NULL;
            value = last->data;
            delete last;
            cout << value << " is removed" << endl;
        }// end inner if
    }else{
        cout << "remove unsuccessful: no nodes remained" << endl;
    }// end if
}
template <class T>
void Chain<T>::deletefromFront(){
    T value;
    // get the mry location of the last node

    if(first){
        ChainNode<T>* tmpPtr = first;
        first = first->link;
        value = tmpPtr->data;
        delete tmpPtr;
        cout << value << " is removed" << endl;
    }else{
        cout << "remove unsuccessful: no nodes remained" << endl;
    }
}
template <class T>
void Chain<T>::printAll(){
    if(first != NULL){
        ChainNode<T>* tmpPtr = first;
        while(tmpPtr != NULL){
            cout << tmpPtr->data << " ";
            tmpPtr = tmpPtr->link;
        }// end while
        cout << endl;
    }else{
        cout << "nothing" << endl;
    }// end if
}
template <class T>
Chain<T>::~Chain(){

    ChainNode<T>* tmpPtr = first;
    while(tmpPtr != NULL){
        first = first->link;
        delete tmpPtr;
        tmpPtr = first;
    }// end while
}