// *********************************************************
// Header file ListP.h for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ListIndexOutOfRangeException.h"
typedef int ListItemType;

class List
{
public:
// constructors and destructor:
   List();                    // default constructor
   List(const List& aList);   // copy constructor
   ~List();                   // destructor

// list operations:
   bool isEmpty() const;
   int getLength() const;
   void insert(int index, ListItemType newItem)
         throw (ListIndexOutOfRangeException);
   void remove(int index)
         throw (ListIndexOutOfRangeException);
   void retrieve(int index, ListItemType& dataItem) const
         throw (ListIndexOutOfRangeException);
   void insertRec(ptr, ListItemType newItem);
      
   

private:
   struct ListNode            // a node on the list
   {
      ListItemType     item;  // a data item on the list
      ListNode        *next;  // pointer to next node
   };  // end struct

   int       size;  // number of items in list
   ListNode *head;  // pointer to linked list of items
   

   ListNode *find(int index) const;
   void linkedListInsert(ListNode *&head, ListItemType newItem);
    //Returns a pointer to the index-th node
    //in the linked list.
}; // end class
// End of header file.

include <stdexcept>
#include <string>
using namespace std;
class ListIndexOutOfRangeException: public out_of_range
{
public:
   ListIndexOutOfRangeException(const string & message = "")
                        : out_of_range(message.c_str())
   { }
};  // end ListIndexOutOfRangeException

// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include <iostream>
using namespace std;
#include "RListP.h"     // header file
#include <cstddef>     // for NULL
#include <cassert>     // for assert()




List::List(): size(0), head(NULL)
{
}  // end default constructor

List::List(const List& aList): size(aList.size)
{
   if (aList.head == NULL)
      head = NULL;  // original list is empty

   else
   {  // copy first node
      head = new ListNode;
      head->item = aList.head->item;

      // copy rest of list
      ListNode *newPtr = head;  // new list pointer
      // newPtr points to last node in new list
      // origPtr points to nodes in original list
      for (ListNode *origPtr = aList.head->next;
                   origPtr != NULL;
                   origPtr = origPtr->next)
      {  newPtr->next = new ListNode;
         newPtr = newPtr->next;
         newPtr->item = origPtr->item;
      }  // end for

      newPtr->next = NULL;
   }  // end if
}  // end copy constructor

List::~List()
{
   while (!isEmpty())
      remove(1);
} // end destructor

bool List::isEmpty() const
{
   return size == 0;

}  // end isEmpty

int List::getLength() const
{
   return size;
}  // end getLength

List::ListNode *List::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. If index < 1 or index > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
   if ( (index < 1) || (index > getLength()) )
      return NULL;

   else  // count from the beginning of the list
   {  ListNode *cur = head;
      for (int skip = 1; skip < index; ++skip)
         cur = cur->next;
      return cur;
   }  // end if
}  // end find

void List::retrieve(int index,
                    ListItemType& dataItem) const throw(ListIndexOutOfRangeException)
{
   if ((index < 1) || (index > getLength()))
      throw ListIndexOutOfRangeException(
              "ListIndexOutOfRangeException: retrieve index out of range");
   else
   {  // get pointer to node, then data in node
      ListNode *cur = find(index);
      dataItem = cur->item;
	  cout<<dataItem<<endl;
   }  // end if
} // end retrieve

void List::insert(int index, ListItemType newItem) throw(ListIndexOutOfRangeException)
{
   int newLength = getLength() + 1;

   if ((index < 1) || (index > newLength))
      throw ListIndexOutOfRangeException(
              "ListIndexOutOfRangeException: insert index out of range");

   else
   {  // create new node and place newItem in it
      ListNode *newPtr = new ListNode;
      size = newLength;
      newPtr->item = newItem;

      // attach new node to list
      if (index == 1)
      {  // insert new node at beginning of list
         newPtr->next = head;
         head = newPtr;
      }
      else
      {  ListNode *prev = find(index-1);
         // insert new node after node
         // to which prev points
         newPtr->next = prev->next;
         prev->next = newPtr;
      }  // end if
   } // end if
} // end insert

void List::remove(int index) throw(ListIndexOutOfRangeException)
{
   ListNode *cur;

   if ((index < 1) || (index > getLength()))
      throw ListIndexOutOfRangeException(
               "ListIndexOutOfRangeException: remove index out of range");
   else
   {  
	   --size;
      if (index == 1)
      {  // delete the first node from the list
         cur = head;  // save pointer to node
         head = head->next;
      }

      else
      {  ListNode *prev = find(index-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 remove

void List::linkedListInsert(ListNode *&head, ListItemType newItem)
{
   if ((head == NULL) || (newItem < head->item))
   {  // base case: insert newItem at beginning
      // of the linked list to which headPtr points
      ListNode *newPtr = new ListNode;
      newPtr->item = newItem;
      newPtr->next = head;
      head = newPtr;
   }
   else
      linkedListInsert(head->next, newItem);
}  // end linkedListInsert

void List::RecursiveInsert(ListNode *Ptr, ListItemType newItem)
{
}
int main()
{
	List aList;
	aList.linkedListInsert(5);
	aList.linkedListInsert(4);
	int a = 0;
	//a = aList.getLength();
	//cout<<a<<endl;
}