//list -- simple Double Linked List, by tsaiwn@csie.nctu.edu.tw
#ifndef __MYLIST_
#define __MYLIST_
class _LP {   // Linked pointer
  public:   _LP* prev;  _LP* next;   // left = previous, right
};
template <class T>
class _LKNode : public _LP { public:  T  data;  };

template <class T, class TRef, class TPtr>
struct myListIterator {    // public:
  _LP* myNode;
  myListIterator(_LKNode<T> * it) : myNode(it) {}
  myListIterator( ) { myNode = 0;}
  void _M_incr() { myNode = myNode->next; }
  void _M_decr() { myNode = myNode->prev; }
  myListIterator<T, TRef, TPtr> & operator++( ) {   // for ++it;
    this->_M_incr( );  return *this;
  }
  myListIterator<T, TRef, TPtr> & operator++(int) {  // for it++;
    myListIterator<T, TRef, TPtr> tmp= *this; 
    this->_M_incr(); return tmp;
  }
  myListIterator<T, TRef, TPtr> & operator--( ) {  // for  --it;
    this->_M_decr( );  return *this;
  }
  myListIterator<T, TRef, TPtr> & operator--(int) {  // for it--;
    myListIterator<T, TRef, TPtr> tmp= *this; 
    this->_M_decr(); return tmp;
  }
  bool operator==(const myListIterator<T, TRef, TPtr> & bp) const {
    return myNode == bp.myNode;
  }
  bool operator!=(const myListIterator<T, TRef, TPtr> & bp) const {
    return myNode != bp.myNode;
  }// operator!=
  TRef operator*() const { return ((_LKNode<T> *) myNode)->data; }
};  // struct myListIterator
////// ////// //////    ////// ////// //////
template <class T> 
class list {    // Linked List
   _LKNode<T> * head;   // the head Node    *********************
  public:
    typedef myListIterator<T, T&, T*>  iterator;
    list( ){head=new _LKNode<T>( ); head->next = head->prev = head; }
    int size( ) const {  int ans = 0;
       for(iterator i=begin(); i != end(); ++i) ++ans; return ans;
    }//size(
  ////////////// === there is NO capacity( ) for list
    iterator begin( ) const { return (_LKNode<T> *)(head->next);}
    iterator end( ) { return head; }
    iterator end( ) const { return head; }
    T& front( ) const { return *begin( ); }
    T& back( ) const {  return *(--end() ); }
    void push_front(const T& x) { insert(begin(), x); }
    void push_back(const T& x) { insert(end(), x); }
    iterator insert(iterator it, const T& x ) { // study these codes
       _LKNode<T> * tmp = new _LKNode<T>( );
       tmp->data = x;
       tmp->next = it.myNode;    // do "insert before it"
       tmp->prev = it.myNode->prev;
       it.myNode->prev->next = tmp;
       it.myNode->prev = tmp;
       return tmp;
    }// insert(
    iterator insert(int n, const T& x ) { // add to n-th position
        iterator it = begin( );    // this is 0-th position
        for(int k=0; k < n; ++k) ++it;  return insert(it, x);
    }
    void sort( ) {  // not implement yet 
    }// sort(
};  // class list
#endif