// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "LinkedList.h"     // header file
#include <cstddef>     // for NULL

ListReferenceBased::ListReferenceBased() : numItems(0), head(NULL)
{}  // end default constructor

ListReferenceBased::~ListReferenceBased()
{
  removeAll();
} // end destructor

bool ListReferenceBased::isEmpty() const
{
   return numItems == 0;
}  // end isEmpty

int ListReferenceBased::size() const
{
   return numItems;
}  // end size

ListReferenceBased::Node *ListReferenceBased::find(int index) const
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the
// desired node.
// Postcondition: Returns a pointer to the desired
// node.
// --------------------------------------------------
{
   // count from the beginning of the list
   Node *curr = head;
   for (int skip = 1; skip < index; skip++)
      curr = curr->getNext();
    return curr;
}  // end find

Object* ListReferenceBased::get(int index)
  throw(ListIndexOutOfRangeException)
{
   if (index < 1 || index > numItems)
      throw ListIndexOutOfRangeException(
              "ListIndexOutOfRangeException: retrieve index out of range");
   else
   {  // get pointer to node, then data in node
      Node *curr = find(index);
      Object* dataItem = curr->getItem();
      return dataItem;
   }  // end if
} // end retrieve

void ListReferenceBased::add(int index, Object* item) 
  throw(ListIndexOutOfRangeException)
{
   if (index < 1 || index > numItems+1)
      throw ListIndexOutOfRangeException(
              "ListIndexOutOfRangeException: insert index out of range");
   else
   {
      // attach new node to list
      if (index == 1) {  
         // insert new node at beginning of list
         Node *newNode = new Node(item, head);
         head = newNode;
      }
      else {  
         Node *prev = find(index-1);
         // insert new node after node
         // to which prev points
         Node *newNode = new Node(item, prev->getNext());
         prev->setNext(newNode);
      }  // end if
      numItems++;
   } // end if
} // end insert

void ListReferenceBased::remove(int index) 
  throw(ListIndexOutOfRangeException)
{
   if (index < 1 || index > numItems)
      throw ListIndexOutOfRangeException(
               "ListIndexOutOfRangeException: remove index out of range");
   else {
      Node *toBeDeleted;
      // in C++ we have to take care of realising the memory
      
      if (index == 1)
      {  // delete the first node from the list
         toBeDeleted = head;  // save pointer to node
         head = head->getNext();
      }
      else {  
         Node *prev = find(index-1);
         // delete the node after the
         // node to which prev points
         toBeDeleted = prev->getNext();  // save pointer to node
         prev->setNext(toBeDeleted->getNext());
      }  // end if

      // return node to system
      delete toBeDeleted->getItem();
      delete toBeDeleted;
      numItems--;
   } // end if
}  // end remove

void ListReferenceBased::removeAll() 
{
   while (!isEmpty())
      remove(1);
   // NOTE: in C++ we have to take care of releasing all allocated memory!!!
}  // end removeAll