///////////////////////////////////////////////////////////////////////////////
// $Id: LinkedList.hxx,v 1.2 1996/01/03 20:14:56 bwmott Exp $
///////////////////////////////////////////////////////////////////////////////
//
// LinkedList.hxx - Template to handle singly linked list
//
//
// Bradford W. Mott
// Copyright (C) 1994
// November 11,1994
//
///////////////////////////////////////////////////////////////////////////////
// $Log: LinkedList.hxx,v $
// Revision 1.2  1996/01/03 20:14:56  bwmott
// Fixed for scope problem caused by new C++ standards
//
// Revision 1.1  1995/01/08 06:49:35  bmott
// Initial revision
//
///////////////////////////////////////////////////////////////////////////////

#ifndef LINKEDLIST_HXX
#define LINKEDLIST_HXX

template<class T> class LinkedList {
  private:

    // Class for each link in the linked list
    class Node {
      public:
        T* data;
        Node* next;
        Node(T* a) : data(a), next( (Node*)0 ) {};
        Node(T* a, Node* n) : data(a), next(n) {};
    };

    // Head, Tail, and Current pointers for my list
    Node* Head;
    Node* Tail;
    Node* Current;

    // Number of items in the list
    int Size;

  public:
    ///////////////////////////////////////////////////////////////////////////
    // Constructor
    ///////////////////////////////////////////////////////////////////////////
    LinkedList()
    { 
      Head = Tail = Current = (Node*)0;
      Size = 0;
    }

    ///////////////////////////////////////////////////////////////////////////
    // Destructor
    ///////////////////////////////////////////////////////////////////////////
    ~LinkedList()
    {
      T* p;

      // Free all of the objects I hold
      while((p = removeHead()) != (T*)0)
      {
        delete p;
      } 
    }

    ///////////////////////////////////////////////////////////////////////////
    // Prepend object 
    ///////////////////////////////////////////////////////////////////////////
    void prepend(T* object)
    {
      Head = new Node(object, Head);
      
      if(Tail == (Node*)0)
        Tail = Head;  

      ++Size;
    }

    ///////////////////////////////////////////////////////////////////////////
    // Append object
    ///////////////////////////////////////////////////////////////////////////
    void append(T* object)
    {
      if(Tail == (Node*)0)
      {
        Head = Tail = new Node(object);
      }
      else
      {
        Tail->next = new Node(object);
        Tail = Tail->next;
      }

      ++Size;
    }

    ///////////////////////////////////////////////////////////////////////////
    // Remove the object at the head of my list
    ///////////////////////////////////////////////////////////////////////////
    T* removeHead()
    {
      if(Head != (Node*)0)
      {
        --Size;

        Node* p = Head;
        Head = p->next;

        if(Current == p)
          Current = p->next;

        if(Head == (Node*)0)
          Tail = (Node*)0;

        T* data = p->data;
        delete p; 
        return(data);
      }
      else
      {
        return (T*)0;
      }
    }

    ///////////////////////////////////////////////////////////////////////////
    // Remove the object at the tail of my list
    ///////////////////////////////////////////////////////////////////////////
    T* remove()
    {
      if(Head != (Node*)0)
      {
        --Size;

        Node* q;
        Node* p;
        for(q = 0, p = Head; p != Tail; q = p, p = p->next);

        if(q == (Node*)0)
        {
          Head = Tail = Current = (Node*)0;
          T* data = p->data;
          delete p; 
          return(data);
        }
        else
        {
          q->next = (Node*)0;
          Tail = q;
          if(Current == p)
            Current = (Node*)0;

          T* data = p->data;
          delete p; 
          return(data);
        }
      }
      else
      {
        return (T*)0;
      }
    }

    ///////////////////////////////////////////////////////////////////////////
    // Remove the given object from my list
    ///////////////////////////////////////////////////////////////////////////
    T* remove(T* object)
    {
      if(Head != (Node*)0)
      {
        Node* q;
        Node* p;
        for(q = 0, p = Head; (p != (Node*)0) && (p->data != object);
            q = p, p = p->next);

        if((q == (Node*)0) && (p != (Node*)0))
        {
          --Size;

          Head = p->next;
          if(Tail == p)
            Tail = p->next;
          if(Current == p)
            Current = p->next;

          T* data = p->data;
          delete p; 
          return(data);
        }
        else if((q == (Node*)0) && (p == (Node*)0))
        {
          return((T*)0);
        }
        else if((q != (Node*)0) && (p != (Node*)0))
        {
          --Size;

          q->next = p->next;
          if(Current == p)
            Current = p->next;

          if(p == Tail)
            Tail = q;

          T* data = p->data;
          delete p; 
          return(data);
        }
        else
        {
          return((T*)0);
        }
      }
      else
      {
        return((T*)0);
      }
    }

    ///////////////////////////////////////////////////////////////////////////
    // Answer the object at my head if one exists
    ///////////////////////////////////////////////////////////////////////////
    T* head()
    {
      if(Head != (Node*)0)
        return(Head->data);
      else
        return((T*)0);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Answer the object at my tail if one exists
    ///////////////////////////////////////////////////////////////////////////
    T* tail()
    {
      if(Tail != (Node*)0)
        return(Tail->data);
      else
        return((T*)0);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Answer the first object if one exists and reset Current
    ///////////////////////////////////////////////////////////////////////////
    T* first()
    {
      Current = Head;
      if(Current != (Node*)0)
        return(Current->data);
      else
        return((T*)0);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Answer the next object in my list or (T*)0 if one doesn't exist
    ///////////////////////////////////////////////////////////////////////////
    T* next()
    {
      if(Current != (Node*)0)
        Current = Current->next;

      if(Current != (Node*)0)
        return(Current->data);
      else
        return((T*)0);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Answer the number of items in the list
    ///////////////////////////////////////////////////////////////////////////
    int size()
    {
      return(Size);
    } 
};
#endif