#ifndef __LISTS_H

#define __LISTS_H



template <class Items>
class ListNodes {
public:
  ListNodes *next;
  Items     item;
};

template <class Items> class ListIterators;

template <class Items>
class Lists {
public:
  
  class EmptyError{};

  Lists();
  Lists (const Lists<Items>&);
  virtual ~Lists();	

  virtual const Items& head() const;
  virtual int isElement (const Items&) const;
  virtual int isEmpty() const;
  virtual unsigned int length() const;

  virtual void append (const Items&);
  virtual void append (const Lists<Items>&);
  virtual void clear();
  virtual void insertAtHead (const Items&);
  virtual void insertAtTail (const Items&);
  virtual void prepend (const Items&);
  virtual void remove (const Items&);
  virtual void removeHead();
  virtual void removeHead (Items&);
  virtual void removeTail();
  virtual void traverse (int (*)(const Items&));				

  virtual const Lists<Items>& operator = (const Lists<Items>&);
  virtual int operator == (const Lists<Items>&) const;
  virtual int operator != (const Lists<Items>&) const;
  
  friend class ListIterators<Items>;

protected:

  ListNodes<Items> *theList;
};

// ABSTRACT:

//

//   The List class provides basic list data structure functionality.

//

// METHODS:

//

//   Self Explanatory.

//

// EXCEPTIONS:

//

//  head() throws EmptyError on attempts to access the head item from 

//     an empty list.

//  removeHead() throws EmptyError on attempts to remove the head item

//     from an empty list.

//  removeTail() throws EmptyError on attempts to remove the tail item

//     from an empty list.

//


template <class Items> 
Lists<Items>::Lists() 
{
  theList = 0;
}

template <class Items> 
Lists<Items>::Lists (const Lists<Items>& list)
{
ListNodes<Items> *node = list.theList;

  theList = 0;
  while (node)
    {
    insertAtTail (node->item);
    node = node-> next;
    }
}

template <class Items> 
Lists<Items>::~Lists() 
{
  clear();
}

template <class Items>
const Items& Lists<Items>::head() const
{
  if (isEmpty())
    throw EmptyError();
  return theList->item;
}

template <class Items>
int Lists<Items>::isElement(const Items& item) const
{
ListNodes<Items> *node = theList;
int found = 0;

  while (node)
    {
    if (node->item == item)
      {
      found = 1;
      break;
      }
    node = node->next;
    }
  return found;
}

template <class Items>
int Lists<Items>::isEmpty() const
{
  return (theList == 0);
}

template <class Items>
unsigned int Lists<Items>::length() const
{
ListNodes<Items> *node = theList;
unsigned int length = 0;

  while (node)
  {
  length++;
  node = node->next;
  }
  return length;
}

template <class Items>
void Lists<Items>::append (const Items& item) 
{
  insertAtTail (item);
}

template <class Items>
void Lists<Items>::append (const Lists<Items>& list) 
{
ListNodes<Items> *node = list.theList;

  while (node)
  {
  insertAtTail (node->item);
  node = node->next;
  }
}

template <class Items>
void Lists<Items>::clear()
{
ListNodes<Items> *node = theList;

  while (node)
    {
    theList = theList->next;
    delete node;
    node = theList;
    }
}

template <class Items> 
void Lists<Items>::insertAtHead (const Items& item) 
{
ListNodes<Items> *node;
 
  node = new (ListNodes<Items>);
  node->item = item;
  node->next = theList;
  theList = node;
}

template <class Items> 
void Lists<Items>::insertAtTail (const Items& item) 
{
ListNodes<Items> *node;
ListNodes<Items> *temp = theList;
 
  node = new (ListNodes<Items>);
  node->item = item;
  node-> next = 0;

  if (theList == 0)
    theList = node;
  else
    {
    while (temp->next)
      temp = temp->next;
    temp->next = node;
    }
}

template <class Items>
void Lists<Items>::prepend (const Items& item) 
{
  insertAtHead (item);
}

template <class Items>
void Lists<Items>::remove (const Items& item)
{ 
ListNodes<Items> *node = theList;
ListNodes<Items> *trailer = theList;

  if (!isEmpty())
    {
    if (node->item == item)
      {
      theList = theList->next;
      delete node;
      }
    else
      {
      node = node->next;
      while (node)
        {
        if (node->item == item)
          {
          trailer->next = node->next;
          delete node;
          break; // find first occuring and break out of while loop

          }
        else
          {
          node = node->next;
          trailer = trailer->next;
          }
        }
      }
    }
}

template <class Items>
void Lists<Items>::removeHead()
{
ListNodes<Items> *node = theList;

  if (isEmpty())
    throw EmptyError();
  else
    {
    theList = theList->next;
    delete node;
    }
}

template <class Items>
void Lists<Items>::removeHead (Items& item)
{
  if (isEmpty())
    throw EmptyError();
  else
  {
    item = theList->item;
    removeHead();
  } 
}

template <class Items>
void Lists<Items>::removeTail()
{
ListNodes<Items> *node = theList;
ListNodes<Items> *tailGate = theList;

  if (isEmpty())
    throw EmptyError();
  else
  {
    node = node->next;
    if (!node)
    {
      delete theList;
      theList = 0;
    }
    else
    {
      while (node->next)
      { 
        node = node->next;
        tailGate = tailGate->next;
      }
      tailGate->next = 0;
      delete node;
    }
  }
}

template <class Items>
void Lists<Items>::traverse (int (*apply)(const Items&))
{
ListNodes<Items> *node = theList;

  while (node)
    {
    if (apply (node->item) == 0)
      break;
    node = node->next;
    }
}

template <class Items>
const Lists<Items>& Lists<Items>::operator = (const Lists<Items>& list)
{
ListNodes<Items> *node = list.theList;

  if (this != &list)
  {
    clear();
    while (node)
    {
      insertAtTail (node->item);
      node = node-> next;
    }
  }
  return *this;
}


template <class Items>
int Lists<Items>::operator == (const Lists<Items>& list) const
{
ListNodes<Items> *inner, *outer;
int equal = 1;

  inner = theList;
  outer = list.theList;
  
  while (inner != 0 && outer != 0)
  {
    if (!(inner->item == outer->item))
    {
      equal = 0;
      break;
    }
    inner = inner->next;
    outer = outer->next;
  }
  if (equal)
   equal = (inner == outer);
  
  return equal;
}

template <class Items>
int Lists<Items>::operator != (const Lists<Items>& list) const
{
  return !(*this == list);
}


#endif



// Copyright (c) 1995-1996 D J Supel and ISX Corporation