// Chap 4, pp 165 -170
// Change the name of this file to ListP.cpp

// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ListP.h"   // header file
#include <stddef.h>  // for NULL
#include <assert.h>  // fo assert()

struct listNode    // a node on the list
{  listItemType Item;  // a data item on the list
   ptrType      Next;  // pointer to next node
};  // end struct

listClass::listClass(): Size(0), Head(NULL)
{
}  // end default constructor

listClass::listClass(const listClass& L): Size(L.Size)
{
   if (L.Head == NULL)
      Head = NULL;  // original list is empty

   else
   {  // copy first node
      Head = new listNode;
      assert(Head != NULL);  // check allocation
      Head->Item = L.Head->Item;

      // copy rest of list
      ptrType NewPrev = Head;  // new list pointer
      for (ptrType OrigCur = L.Head->Next; 
                   OrigCur != NULL; 
                   OrigCur = OrigCur->Next)
      {  NewPrev->Next = new listNode;
         assert(NewPrev->Next != NULL);
         NewPrev = NewPrev->Next;
         NewPrev->Item = OrigCur->Item;
      }  // end for

      NewPrev->Next = NULL;
   }  // end if
}  // end copy constructor

listClass::~listClass()
{
   boolean Success;

   while (!ListIsEmpty())
      ListDelete(1, Success);
} // end destructor

boolean listClass::ListIsEmpty()
{
   return boolean(Size == 0);
}  // end ListIsEmpty

int listClass::ListLength()
{
   return Size;
}  // end ListLength

ptrType listClass::PtrTo(int Position)
// ---------------------------------------------------
// Locates a specified node on a list.
// Precondition: Position is the number of the 
// desired node.
// Postcondition: Returns a pointer to the node at 
// position Position. If Position < 1 or Position > 
// the number of nodes on the list, returns NULL.
// ---------------------------------------------------
{
   if ( (Position < 1) || (Position > ListLength()) )
     return NULL;

   else  // count from the beginning of the list
   {  ptrType Trav = Head;
      for (int Skip = 1; Skip < Position; ++Skip)
         Trav = Trav->Next;
      return Trav;
   }
}  // end PtrTo

void listClass::ListRetrieve(int Position,
                             listItemType& DataItem, 
                             boolean& Success)
{
   Success = boolean( (Position >= 1) &&
		      (Position <= ListLength()) );

   if (Success)
   {  // get pointer to node, then data in node
      ptrType Cur = PtrTo(Position);
      DataItem = Cur->Item;
   }
} // end ListRetrieve

void listClass::ListInsert(int NewPosition,
                           listItemType NewItem, 
                           boolean& Success)
{
   int NewLength = ListLength() + 1;

   Success = boolean( (NewPosition >= 1) &&
                      (NewPosition <= NewLength) );

   if (Success)
   {  Size = NewLength;

      // create new node and place NewItem in it
      ptrType NewPtr = new listNode;
      Success = boolean(NewPtr != NULL);
      if (Success)
      {  NewPtr->Item = NewItem;

         // attach new node to list
         if (NewPosition == 1)
	 {  // insert new node at beginning of list
            NewPtr->Next = Head;
            Head = NewPtr;
         }

         else
         {  ptrType Prev = PtrTo(NewPosition-1);
            // insert new node after node 
            // to which Prev points
            NewPtr->Next = Prev->Next;
	    Prev->Next = NewPtr;
         }  // end if
      }  // end if
   }  // end if
} // end ListInsert

void listClass::ListDelete(int Position,
                           boolean& Success)
{
   ptrType Cur;

   Success = boolean( (Position >= 1) && 
		      (Position <= ListLength()) );

   if (Success)
   {  --Size;
      if (Position == 1)
      {  // delete the first node from the list
         Cur = Head;  // save pointer to node
         Head = Head->Next;
      }

      else
      {  ptrType Prev = PtrTo(Position-1);
         // delete the node after the
         // node to which Prev points
         Cur = Prev->Next;  // save pointer to node
         Prev->Next = Cur->Next;
      }  // end if

      // return node to system
      Cur->Next = NULL;
      delete Cur;
      Cur = NULL;
   }  // end if
}  // end ListDelete