#ifndef _MATT_STL_LIST
#define _MATT_STL_LIST

#include "cstring"
#include <stdio.h>

namespace std {


template< class T >
class ListNode {
public:
   T data;
   ListNode * next;
   ListNode * prev;
   ListNode() { }
   ~ListNode() { }
};

template< class T >
class list_iterator {
public:
   ListNode< T > * p_node;

   list_iterator() {
      p_node = 0;
   }

   list_iterator(const list_iterator & cp) {
      p_node = cp.p_node;
   }

   list_iterator(ListNode< T > * n) {
      p_node = n;
   }

   ~list_iterator() {
   }

   T & operator*() {
      return p_node->data;
   }

   list_iterator & operator++() {
      p_node = p_node->next;
      return *this;
   }

   list_iterator & operator--() {
      p_node = p_node->prev;
      return *this;
   }

   list_iterator & operator++(int) {
      p_node = p_node->next;
      return *this;
   }

   list_iterator & operator--(int) {
      p_node = p_node->prev;
      return *this;
   }

   list_iterator & operator=(const list_iterator< T > & right) {
      p_node = right.p_node;
      return *this;
   }

   bool operator==(const list_iterator< T > & right) {
      if(p_node == right.p_node) {
         return true;
      }
      return false;
   }

   bool operator!=(const list_iterator< T > & right) {
      bool ret;
      if(p_node != right.p_node) 
         ret = true;
      else 
         ret = false;
      return ret;
   }

   T * operator->() {
      return &p_node->data;
   }
};

template< class T >
class list {
public:
    typedef list_iterator< T > iterator;
    typedef list_iterator< T > const_iterator;

private:
    ListNode< T > * head;
    size_t the_size;

public:
   list() { 
      head = new ListNode< T >(); 
      head->next = head; 
      head->prev = head;
      the_size = 0; 
   }

   void push_back(const T & a) {
      ListNode< T > *p_node = new ListNode< T >();
      p_node->data = a;
      p_node->next = head;
      p_node->prev = head->prev;
      p_node->prev->next = p_node;
      head->prev = p_node;
      the_size++;
   }

   list(const list & l) {
      the_size = 0;
      head = new ListNode< T >(); 
      head->next = head; 
      head->prev = head;
      if(l.the_size) {
         for(ListNode< T > * p_node = l.head->next; p_node != l.head; p_node = p_node->next) {
            push_back(p_node->data);
         }
      }
   }

   ~list() { 
      while(size()) {
         pop_front();
      }
      delete head;
   }
   size_t size() { return the_size; }
   void push_front(const T & a) { 
      ListNode< T > * p_node = new ListNode< T >();
      p_node->data = a;
      p_node->next = head->next;
      p_node->prev = head; 
      p_node->next->prev = head;
      head->next = p_node;
      the_size++;
   }
   void pop_front() { 
      ListNode< T > * p_node = head->next;
      head->next = head->next->next;
      p_node->next->prev = head;
      delete p_node;
      the_size--;
   }
   void pop_back() { 
      ListNode< T > * p_node = head->prev;
      head->prev = head->prev->prev;
      p_node->prev->next = head;
      delete p_node;
      the_size--;
   }
   T & front() { return head->next->data; }
   T & back() { return head->prev->data; }
   const_iterator begin() const { 
      const_iterator it(head->next); 
      return it; 
   }
   const_iterator end() const { 
      const_iterator it(head); 
      return it; 
   }
   iterator begin() { 
      iterator it(head->next); 
      return it; 
   }
   iterator end() { 
      iterator it(head); 
      return it; 
   }
   void insert(iterator & ptr, const T & t) {
      cout << "insert... in list..." << endl;
      exit(1);
   }
   void erase(iterator & ptr1, iterator & ptr2) {
      cout << "erase 1... in list..." << endl;
      exit(1);
   }
   void erase(iterator & ptr1) {
      cout << "erase 2... in list..." << endl;
      exit(1);
   }

   void clear() { 
      while(the_size)
         pop_front();
   }

   list & operator=(const list & l) {
      if(head == l.head) {
         return *this;
      }
      while(the_size) 
         pop_front();

      if(l.the_size) {
         for(ListNode< T > * p_node = l.head->next; p_node != l.head; p_node = p_node->next) {
            push_back(p_node->data);
         }
      }
      return *this;
   }

   void sort() {
      cout << "sort ... in list..." << endl;
      exit(1);
   }
};

}

#endif /* _MATT_STL_LIST */
