#ifndef LIST_H
#define LIST_H

template<class T> class List;

template<class T> class ListNode {
  friend class List<T>;

private:
  ListNode<T> *next;
  T   data;

  // constructor
  ListNode(const ListNode<T> *n, T e) : next((ListNode<T> *)n), data(e) {}

  // default constructor
  // (should not be available, so do not define this function)
  ListNode(void);

  // destructor
  ~ListNode(void) {}
};


template<class T> class List {

private:
  ListNode<T> *head;
  ListNode<T> *curr;

public:
  // constructor
  List() : head(0), curr(0) {}
  // destructor
  ~List(void)
  {
    while ( !empty() )
      remove();
  }

  void insert_after(T elem)
  {
    if ( head )
    {
      curr->next = new ListNode<T>(curr->next, elem);
      curr = curr->next;
    }
    else
      head = curr = new ListNode<T>((ListNode<T> *) 0, elem);
  }

  void insert_before(T elem)
  {
    ListNode<T> *p;
    if ( curr == head )
      head = curr = new ListNode<T>(head, elem);
    else
    {
      for (p = head; p->next != curr; p = p->next)
        ;
      curr = p;
      insert_after(elem);
    }
  }

  void remove(void) 
  {
    ListNode<T> *p;
    if ( curr != head )
    {
      for (p = head; p->next != curr; p = p->next)
        ;
      p->next = curr->next;
    }
    else
      head = head->next;
    delete curr;
    curr = head;
  }

  T retrieve(void) const {return curr->data;}

  // bool find_first(void) . . .
  int find_first(void) {return !(curr = head);}

  // bool find_prior(void) . . .
  int find_prior(void)
  {
    ListNode<T> *p;
    int fail = (curr == head);

    if ( !fail )
    {
      for (p = head; p->next != curr; p = p->next)
        ;
      curr = p;
    }
    return fail;
  }

  // bool find_next(void) . . .
  int find_next(void)
  {
    int fail = (curr->next == (ListNode<T> *) 0);

    if ( !fail )
      curr = curr->next;
    return fail;
  }

  // bool empty(void) . . .
  int empty(void) const {return (head == (ListNode<T> *) 0);}
};


#endif /* LIST_H */