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

template <class T, class TRef, class TPtr>
struct myListIterator { 
  _LP* _M_node;
  myListIterator(_LNode<T> * it) : _M_node(it) {}
  myListIterator( ) {;}
  void _M_incr() { _M_node = _M_node->next; }
  void _M_decr() { _M_node = _M_node->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--( ) {
    this->_M_decr( );  return *this;
  }
  myListIterator<T, TRef, TPtr> & operator--(int) {  // for it--;
    myListIterator<T, TRef, TPtr> tmp= *this; 
    this->_M_decr(); return tmp;
  }
  TRef operator*() const { return ((_LNode<T> *) _M_node)->data; }
  bool operator==(const myListIterator<T, TRef, TPtr> & bp) const {
    return _M_node == bp._M_node;
  }
  bool operator!=(const myListIterator<T, TRef, TPtr> & bp) const {
    return _M_node != bp._M_node;
  }// operator!=
};
//////
template <class T> 
class list {    // Linked List
   _LNode<T> * head;   // the head Node
  public:
    typedef myListIterator<T, T&, T*>  iterator;
    list( ){head=new _LNode<T>( ); head->next = head->prev = head; }
    int size( ) const {  int ans = 0;
       for(iterator i=begin() ; i != end(); ++i) ++ans;
       return ans;
    }//size(
  //////////////
    iterator begin( ) const { return (_LNode<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); }
    void insert(iterator it, const T& x ) {
       // to do
    }// insert(
    void sort( ) {
       // not implement yet 
    }// sort(
};  // class list
#endif