// *********************************************************
// Header file LinkedList.h for the ADT list.
// Pointer(Reference)-based implementation.
// *********************************************************
#include "ListIndexOutOfRangeException.h"

class Object {
public:
  virtual ~Object() {} // make sure that appropriate destructor will be called
  virtual operator const char*() const { return "Object"; }
  // any object can be converted to a string which can be printed to stream
  // (see TestLinkedList.cpp for example)
};

// NOTE:
// The List can hold pointers to any object of a class derived from Object

class ListReferenceBased
{
public:
// constructors and destructor:
   ListReferenceBased();                    // default constructor
   ~ListReferenceBased();                   // destructor

// list operations:
   bool isEmpty() const;
   int size() const;
   Object* get(int index)
     throw(ListIndexOutOfRangeException);
   void add(int index, Object* newItem)
     throw(ListIndexOutOfRangeException);
   void remove(int index)
     throw(ListIndexOutOfRangeException);
   void removeAll();

private:
   class Node            // a node on the list
   {
   private:
      Object *item;  // a data item on the list
      Node   *next;  // pointer to next node
   public:
      Node(Object* newItem, Node* nextNode=NULL) {
        item = newItem;
        next = nextNode;
      }
      void setItem(Object* newItem) {
        item = newItem;
      }
      Object* getItem() {
        return item;
      }
      void setNext(Node* nextNode) {
        next = nextNode;
      }
      Node* getNext() {
        return next;
      }
   };  // end Node

   int numItems;  // number of items in list
   Node   *head;  // pointer to linked list of items

   Node *find(int index) const;
   // Returns a pointer to the index-th node
   // in the linked list.
}; // end class
// End of header file.