/* Filename:  list1.cpp

   Programmer:  Br. David Carlson
                Br. Isidore Minerd

   Date:  January 7, 2000

   Modified:  June 26, 2000; November 30, 2001; July 16, 2009

   Modified:  Jan 2, 2018 to use the modern version of dynamic memory
              allocation with new inside of a try...catch.

   This program inserts some integers into a list and then removes
   them from the front of the list, one by one, printing each item
   as it is removed.
*/

#include <iostream>
using namespace std;

typedef int ItemType;


class ListNodeClass
   {
   private:
      ItemType Info;
      ListNodeClass * Next;
   public:
      ListNodeClass(const ItemType & Item, ListNodeClass * NextPtr = NULL):
         Info(Item), Next(NextPtr)
            {
            };
   friend class ListClass;
   };


typedef ListNodeClass * ListNodePtr;


class ListClass
   {
   private:
      ListNodePtr GetNode(const ItemType & Item, ListNodePtr NextPtr = NULL);
      void FreeNode(ListNodePtr NodePtr);
      void ClearList(void);
      ListNodePtr Front, Rear;
      int Count;
   public:
      ListClass(void);
      ~ListClass(void);
      int NumItems(void) const;
      bool Empty(void) const;
      void InsertFront(const ItemType & Item);
      void InsertRear(const ItemType & Item);
      ItemType RemoveFront(void);
   };


/* Given:  Nothing.
   Task:   This is the constructor to initialize a list to be empty
           (with a dummy node).
   Return: Nothing directly, but the implicit object is created.
*/
ListClass::ListClass(void)
   {
   ItemType Item;

   Front = GetNode(Item, NULL);
   Rear = Front;
   Count = 0;
   }


/* Given:  Nothing.
   Task:   This is the destructor for ListClass.  It's job is to recover
           the space for all nodes remaining on the list.
   Return: Nothing directly, but the implicit object is destroyed.
*/
ListClass::~ListClass(void)
   {
   ClearList();
   FreeNode(Front);  // get rid of the dummy node, too
   }


/* Given:  Nothing.
   Task:   Clear out all nodes on the list except the dummy.
           The list is thus set to an empty list.
   Return: Nothing directly, but the implicit ListClass object is modified.
*/
void ListClass::ClearList(void)
   {
   ListNodePtr Current, Temp;

   Current = Front->Next;
   while (Current != NULL)
      {
      Temp = Current;
      Current = Current->Next;
      FreeNode(Temp);
      }

   Front->Next = NULL;
   Rear = Front;
   Count = 0;
   }


/* Given:  Item     A data item to place in the Info field of a new node.
           NextPtr  The pointer to place in the Next field of the new node.
   Task:   To allocate a new node and place Item and NextPtr in it.
   Return: A pointer to the new node is returned in the function name.
*/
ListNodePtr ListClass::GetNode(const ItemType & Item, ListNodePtr NextPtr)
   {
   ListNodePtr NodePtr;
   string junk;

   try
      {
      NodePtr = new ListNodeClass(Item, NextPtr);
      }
   catch (bad_alloc)
      {
      // Some people might prefer to take a less drastic action in this case.
      // Here we give up on the list and on the entire program.
      cerr << "Memory allocation error!  Calling the destructor and exiting the program." << endl;
      this->~ListClass();
      cerr << "Press Enter" << endl;
      getline(cin, junk, '\n');
      exit(1);
      }

   return NodePtr;
   }


/* Given:  NodePtr   A pointer to a ListNodeClass node.
   Task:   To reclaim the space used by this node.
   Return: Nothing.
*/
void ListClass::FreeNode(ListNodePtr NodePtr)
   {
   delete NodePtr;
   }


/* Given:  Nothing (other than the implicit list object).
   Task:   To look up the number of items in this object.
   Return: This number in the function name.
*/
int ListClass::NumItems(void) const
   {
   return Count;
   }


/* Given:  Nothing (other than the implicit ListClass object).
   Task:   To check whether this object is empty.
   Return: true if this object is empty, false otherwise.
*/
bool ListClass::Empty(void) const
   {
   if (Count > 0)
      return false;
   else
      return true;
   }


/* Given:  Item   A data item.
   Task:   To insert a new node containing Item at the front of the implicit
           ListClass object.
   Return: Nothing directly, but the implicit object is modified.
*/
void ListClass::InsertFront(const ItemType & Item)
   {
   ListNodePtr NodePtr;

   NodePtr = GetNode(Item, Front->Next);
   Front->Next = NodePtr;

   if (Count == 0)
      Rear = NodePtr;
   Count++;
   }


/* Given:  Item   A data item.
   Task:   To insert Item into a new node added to the rear of the implicit
           ListClass object.
   Return: Nothing directly, but the implicit object is modified.
*/
void ListClass::InsertRear(const ItemType & Item)
   {
   ListNodePtr NodePtr;

   NodePtr = GetNode(Item);
   Rear->Next = NodePtr;
   Rear = NodePtr;
   Count++;
   }


/* Given:  Nothing (other than the implicit ListClass object).
   Task:   To remove the data item at the front of this list.
   Return: This data item gets returned in the function name.  The implicit
           object is modified.
*/
ItemType ListClass::RemoveFront(void)
   {
   ListNodePtr NodePtr;
   ItemType Item;

   if (Count == 0)
      {
      cerr << "ERROR: there is no item to remove in the list!" << endl;
      exit(1);
      }

   NodePtr = Front->Next;
   Item = NodePtr->Info;
   Front->Next = NodePtr->Next;
   Count--;
   if (Count == 0)
      Rear = Front;
   FreeNode(NodePtr);
   return Item;
   }


int main(void)
   {
   ListClass ListA;
   int Result;

   ListA.InsertFront(40);
   ListA.InsertFront(5);
   ListA.InsertRear(72);
   ListA.InsertRear(100);

   cout << "Number of items in ListA: " << ListA.NumItems() << endl << endl;

   while (! ListA.Empty())
      {
      Result = ListA.RemoveFront();
      cout << "Removed from front of ListA " << Result << endl;
      }

   return 0;
   }