#pragma interface
#ifndef _LIST_H_
#define _LIST_H_


// list: internal building block
template<class T>
class list_node {
   public:
      list_node<T>* next;
      list_node<T>* prev;
      T element;
      list_node();
      list_node(const T&);
};


// list iterator is an interface to list node
// with the usual pointer syntax
template<class T>
class list_iterator {
  protected:
    list_node<T>* node;
    
  public:
    list_iterator(list_node<T>* = (list_node<T>*)0); 
    int has_more_elements();
    T& operator*();
    T* operator->();
    T& operator++();
    T& operator--();
    T& operator++(int);
    T& operator--(int);
    int operator==(const list_iterator<T>&);
    int operator!=(const list_iterator<T>&);
    T& operator[](int);
    list_iterator<T>  operator+(int);
    list_iterator<T>  operator-(int);
   
    list_node<T>* getNode();
    void invalidate();
};


// list class
// operations:
//     insert_before(iterator,element)
//     insert_before(iterator,list)
//     insert_after(iterator,element)
//     insert_after(iterator,list)
//     sort
// access:
//     iterator first
//     iterator last
//
template<class T>
class list {

  protected:

     list_node<T>* _first;
     list_node<T>* _last;
     int size;

     void destroy(list_node<T>*,list_node<T>*);
     void copy(list_node<T>*,list_node<T>*,list_node<T>*,
               list_node<T>*,const list<T>);
 
     bool (*less)(const T&,const T&); 

     void split(list<T>&,list<T>&,const T&);
  
  public: 
     void insert_before(list_iterator<T>,const T&);
     void insert_after(list_iterator<T>,const T&);
     void insert_before(list_iterator<T>,const list<T>&);
     void insert_after(list_iterator<T>,const list<T>&);
     void remove(list_iterator<T>&);
     list_iterator<T> first();
     list_iterator<T> last();
     int length() const;
   
     void set_comparison(bool (*)(const T&,const T&)); 
       
     list(bool (*)(const T&,const T&) = 0);
     list(const list<T>&);
     list<T>& operator=(const list<T>&);
     virtual ~list();
     
     void sort();  
};


#endif