/* 
 * UnderC Development Project
 * A simplified implementation of a list container class
 * S.J. Donovan, December 1999.
 */
#ifndef _LISTX_H
#define _LISTX_H
#define NULL 0
namespace std {

template <class T>
    class list
  {
   struct ListEntry {
       T m_val;
       ListEntry *m_last,*m_next;
   };
   typedef ListEntry *PEntry;
   PEntry m_front, m_back;
   int m_size;
  public:
     class iterator {
      PEntry m_cursor;
    public:
    //  typedef T value_type;
      iterator(PEntry pe) { m_cursor = pe; }
      iterator() { m_cursor = NULL; }
      iterator(const iterator& it) { m_cursor = it.m_cursor; }
      bool operator == (const iterator& it) { return m_cursor == it.m_cursor; }
      bool operator != (const iterator& it) { return m_cursor != it.m_cursor; }
      void cursor(PEntry pe) { m_cursor = pe; }
      PEntry cursor() { return m_cursor; }
      void next() { m_cursor = m_cursor->m_next; }
      void prior(){
              m_cursor = m_cursor->m_last;
          }
      T& operator*()  { return m_cursor->m_val; }
      T *operator->() { return &m_cursor->m_val; }
      iterator& operator++()
       { next(); return *this; }
      iterator& operator--()
       { prior(); return *this; }
       iterator& operator++(int)
       { next(); return *this; }
      iterator& operator--(int)
       { prior(); return *this; }
     };

     typedef T value_type;
     
     int size() const { return m_size; }

     iterator begin() const 
      { 
        PEntry pe = m_front;
        return iterator(pe);
      }
     iterator end()    const { return iterator(NULL);    }
     iterator rbegin() const { return iterator(m_back);  }
     iterator rend()   const { return iterator(NULL);    }

     iterator iter(PEntry pe) { return iterator(pe); }

     private:

     PEntry _alloc(const T& val) {
       PEntry pe = new ListEntry;
       pe->m_val = val;
       pe->m_next = pe->m_last = NULL;
       return pe;
     }
     void _init()  { m_front = m_back = NULL; m_size = 0; }

     void _insert(PEntry p1, PEntry p2, PEntry p, int sz) { // low-level insert
       if (! p2) p2 = p1;
       m_size += sz;
       if (!p) { // adding at end....
             if (!m_front) { m_front = p1; m_back = p2; }
         else {
            m_back->m_next = p1;  p1->m_last = m_back;
        m_back = p2;
         }
       } else { // insert before cursor!
         PEntry last = p->m_last;
         p2->m_next = p;
             p1->m_last = last; // cd be NULL...
             p->m_last = p2;
         if (last) last->m_next = p1; else m_front = p1;
       }
     }  

     void _erase(PEntry cursor) {
         if (cursor->m_last) cursor->m_last->m_next = cursor->m_next;
                       else  m_front = cursor->m_next;
         if (cursor->m_next) cursor->m_next->m_last = cursor->m_last;
                       else  m_back  = cursor->m_last;
             // if (m_front == m_back) m_back = m_front = NULL;  // empty the list!
             m_size--;
      }     

     void _swap(PEntry p1, PEntry p2) {
      _erase(p1);  _insert(p1,NULL,p2,1);
     }

    public:

     void swap(list& ls) {
      // swap(ls.m_front,m_front);  swap(ls.m_back,m_front); swap(ls.m_size,m_size);
     }

     void reverse() {
      // for(PEntry le = m_first; le != NULL; le=le->m_next) swap(le->m_last,le->m_next);
      // swap(m_front,m_back);
     } 
     
     void insert(iterator _at, const T& _val) {
       PEntry np = _alloc(_val);
       _insert(np,NULL,_at.cursor(),1);
     }

     void splice(iterator _at, list& _ls) {
       if (_ls.size() != 0) { 
        _insert(_ls.m_front, _ls.m_back, _at.cursor(), _ls.size());
        _ls._init();
       }
     }

     void splice(iterator _at, list& _ls, iterator _p) {
       PEntry cp = _p.cursor();
       _insert(cp,cp,_at.cursor(),1);  //*NOT sure about this '1'!!
       _ls._erase(cp);
     }

     void erase(iterator _at) {
         if (_at != end()) { _erase(_at.cursor()); delete _at.cursor(); }
     }

    void remove(const T& val);
    void unique(); 

    void push_back(const T& val)    { insert(end(),val); }
    void push_front(const T& val)   { insert(begin(),val); }
    void pop_back()                 { erase(rbegin()); }  //????
    void pop_front()                { erase(begin()); }
    T& front()                      { return m_front->m_val; }
    T& back()                       { return m_back->m_val; }

    void clear() {
        PEntry _P,_Q = m_front;
        while (_Q) { _P = _Q->m_next; delete _Q; _Q = _P; }
            _init();
     }

     void _copy(PEntry start, PEntry finis) {
       for(; start != NULL; start = start->m_next)
          push_back(start->m_val);
     }

     list()             { _init(); }
     ~list()            { clear();  }

     list(const list& ls) { _init(); _copy(ls.m_front,ls.m_back); }

     list& operator = (const list& ls) {
       _copy(ls.m_front,ls.m_back);
       return *this;
     }

     bool operator== (const list& ls) const;

     bool operator != (const list& ls) const
      { return ! (*this == ls); }

  };

  template <class T>
   void list<T>::remove(const T& val)
     { // *fix 1.0.0 used to access cursor after it was destroyed!
        PEntry _P,_Q = m_front;
        while (_Q) {
               _P = _Q->m_next;
               if (_Q->m_val == val) {
                   _erase(_Q);
                   delete _Q;
               } 
               _Q = _P;
            }
    }

  template<class T>
    void list<T>::unique() { // removes consecutive _repeated values_
       if (size() < 2) return;
       iterator p = begin(), q = begin();
       ++q;
       while (q != end()) {
         if (*p == *q) { erase(q); q = p; }
         p = q;
         ++q;
       }
     }

  template<class T>
    bool list<T>::operator== (const list<T>& ls) const
    {
       PEntry p1 = m_front, p2 = ls.m_front;
       for(; p1 != NULL && p2 != NULL && p1->m_val == p2->m_val; p1=p1->m_next) {  
          p2=p2->m_next;
       }
       return p1 == NULL && p2 == NULL;
     }

} // namespace std


#endif