#include <iostream>
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
 
struct ItemType
{
  int id;
  float gpa;
  char major[2];
 
};
 
struct NodeType
{
  ItemType info;
  NodeType* next;
};
 
class SortedType
{
 public:
  SortedType();
  // Constructor
  // Postcondition: Empty list is created
 
  ~SortedType();
  // Destructor
  // Postcondition: List is destroyed
 
  SortedType(const SortedType& otherList);
  // Copy-constructor
  // Postcondition: List is created as a duplicate of otherList
 
  bool IsFull() const;
  // Determines whether list is full.
  // Post: Function value = (list is full)
 
 
 bool invalidItem(ItemType item) const;
 
 
  int  LengthIs() const;
  // Determines the number of elements in list.
  // Post: Function value = number of elements in list.
 
  void MakeEmpty();
  // Initializes list to empty state.
  // Post:  List is empty.
 
  void RetrieveItem(ItemType& item, bool& found);
  // Retrieves list element whose key matches item's key
  // (if present).
  // Pre:  Key member of item is initialized.
  // Post: If there is an element someItem whose key matches
  //       item's key, then found = true and item is a copy
  //       of someItem; otherwise found = false and item is
  //       unchanged.
  //       List is unchanged.
 
  void InsertItem(ItemType item);
  // Adds item to list.
  // Pre:  List is not full.
  //       item is not in list.
  // Post: item is in list
  // (added)  //       list order is preserved
 
  void DeleteItem(ItemType item);
  // Deletes the element whose key matches item's key.
  // Pre:  Key member of item is initialized.
  //       One and only one element in list has a key matching
  //       item's key.
  // Post: No element in list has a key matching item's key.
 
 void ResetList();
  // Initializes current position to end of list for iteration
  // through list.
  // Post: Current position is at end of list.
 
  void GetNextItem(ItemType& item);
  // Gets the next element in list.
  // Pre:
  // Post: If Current position is at end,  currentPos points to head of list,
  //       else item is  copy  of  element at current position.
  //       Advance current position.
 
 void Print(ofstream&);
 
 private:
  NodeType* listData;
  int length;
  NodeType* currentPos;
};
 
 void GetNextItem(ItemType& item);
  // Gets the next element in list.
  // Pre:
  // Post: If Current position is at end,  currentPos points to head of list,
  //       else item is  copy  of  element at current position.
  //       Advance current position.
 
 void Print(ofstream&);
 
 private:
  NodeType* listData;
  int length;
  NodeType* currentPos;
};
 
// SortedType.cxx
 
SortedType::SortedType()  // Class constructor
{
  length = 0;
  listData = NULL;
}
 
SortedType::~SortedType()
// Post: List is empty; all items have been deallocated.
{
  MakeEmpty();
}
 
SortedType::SortedType(const SortedType& otherList)
// Copy-constructor
// Postcondition:
//     IF otherList.listData == NULL
//         listData == NULL
//     ELSE
//         listData points to a new linked list that is a copy of
//         the linked list pointed to by otherList.listData
{
    NodeType* fromPtr;  // Pointer into list being copied from
    NodeType* toPtr;    // Pointer into new list being built
    if(otherList.listData == NULL)
    {
        listData = NULL;
        return;
    }
    // Copy first node
    fromPtr = otherList.listData;
    listData = new NodeType;
    listData->info = fromPtr->info;
 
    // Copy remaining nodes
 
    toPtr = listData;
    fromPtr = fromPtr->next;
    while (fromPtr != NULL)
    {
        toPtr->next = new NodeType;
        toPtr = toPtr->next;
        toPtr->info = fromPtr->info;
        fromPtr = fromPtr->next;
    }
    toPtr->next = NULL;
}
 
/* bool SortedType::IsFull() const
// Returns true if there is no room for another ItemType
//  on the free store; false otherwise.
{
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(bad_alloc exception)
  {
    return true;
  }
} */
 
bool SortedType::invalidItem(ItemType item) const
//**********************************************************************
//Purpose: Determines whether the data assigned is valid given the parameters
//Input: item.id, gpa, major
//Pre: Variables must be set and have valid numbers
//output: bool, true or false
//post: so long as function runs, the data will be processed and determined
//        as invalid or valid data
//note: None
//**********************************************************************
{
               return(item.id >= 111 && item.id <= 999 &&
               item.gpa >= 0.0 && item.gpa <= 4.0 &&
               item.major[0] == 'C' || item.major[0] == 'I' &&
               item.major[1] == 'S');
}
 
 
 
bool SortedType::IsFull() const
// Returns true if there is no room for another ItemType
// object on the free store; false otherwise.
{
  NodeType* ptr;
 
  ptr = new NodeType;
  if (ptr == NULL)
    return true;
  else
  {
    delete ptr;
    return false;
  }
}
 
 
int SortedType::LengthIs() const
// Post: Number of items in the list is returned.
{
  return length;
}
 
 
void SortedType::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
  NodeType*
  tempPtr;
 
  while (listData != NULL) // traverse list, deallocating each node in turn
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
  length = 0; // to agree with the fact that all nodes are deallocated
}
 
 
void SortedType::DeleteItem(ItemType item)
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
  NodeType* location = listData;
  NodeType* tempLocation;
 
  // Locate node to be deleted.
  if (item.id == listData->info.id)
  {
    tempLocation = location;
    listData = listData->next;          // Delete first node.
  }
  else
  {
    while (!(item.id==(location->next)->info.id))
      location = location->next;
 
    // Delete node at location->next
    tempLocation = location->next;
    location->next = (location->next)->next;
  }
  delete tempLocation;
  length--;
}
 
 
void SortedType::ResetList()
// Post: Current position has been initialized to AtEnd
{
  currentPos = NULL;
}
 
void SortedType::RetrieveItem(ItemType& item, bool& found)
{
  bool moreToSearch;
  NodeType* location;
  location = listData;
  found = false;
  moreToSearch = (location != NULL);
  while (moreToSearch && !found)
  {
    if (location->info.id < item.id)
    {
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else if (item.id == location->info.id)
    {
      found = true;
      item = location->info;
    }
    else
moreToSearch = false;
  }
}
 
 
void SortedType::InsertItem(ItemType item)
{
  NodeType* newNode;  // pointer to node being inserted
  NodeType* predLoc;  // trailing pointer
  NodeType* location; // traveling pointer
  bool moreToSearch;
 
  location = listData;
  predLoc = NULL;
  moreToSearch = (location != NULL);
 
  // Find insertion point.
  while (moreToSearch)
  {
    if (location->info.id < item.id)
    {
      predLoc = location;
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else
      moreToSearch = false;
 // Prepare node for insertion
  newNode = new NodeType;
  newNode->info = item;
 
  // Insert node into list.
  if (predLoc == NULL)         // Insert as first
  {
    newNode->next = listData;
    listData = newNode;
  }
  else
  {
    newNode->next = location;
    predLoc->next = newNode;
  }
  length++;
}
 
 
 
void SortedType::GetNextItem(ItemType& item)
// Pre:  Current position is defined.
//       Element at current position is not last in list.
// Post: Current position has been updated; item is current item.
{
  if (currentPos == NULL) //Wrap at end of list
    currentPos = listData;
 
  item = currentPos->info;
  currentPos = currentPos->next;
}
 
void SortedType::Print(ofstream& outFile)
{
   currentPos = listData;
 
   while(currentPos != NULL)
   {
       outFile << currentPos->info.id << "  " << currentPos->info.gpa << currentPos->info.major[0] << currentPos->info.major[1]
       currentPos = currentPos->next;
   }
}

#include "SortedLinkedList.h"
 
int main()
{
        ifstream inFile;
        ofstream outFile;
        char lister;
        int length = 0;
 
        inFile.open("in.data");
        outFile.open("out.data");
        if(inFile.fail() || outFile.fail())
        {
                cout << "Input or output file opening failed" << endl;
        }
 
        SortedType ReadList;
        ItemType item;
 
        outFile << "<~~~~~~~ Grade Report ~~~~~~~>" << endl;
        ReadList.MakeEmpty();
        inFile >> lister;
 
       while(inFile)
        {
                if(lister == 'A')
                {
                       inFile >> item.id >> item.gpa >> item.major[0] >> item.major[1];
                       ReadList.InsertItem(item);
                }
                else if(lister == 'D')
                {
                       inFile >> item.id;
                       ReadList.DeleteItem(item);
                }
                inFile >> lister;
        }
ReadList.MakeEmpty();
        inFile >> lister;
 
       while(inFile)
        {
                if(lister == 'A')
                {
                       inFile >> item.id >> item.gpa >> item.major[0] >> item.major[1];
                       ReadList.InsertItem(item);
                }
                else if(lister == 'D')
                {
                       inFile >> item.id;
                       ReadList.DeleteItem(item);
                }
                inFile >> lister;
        }
 
      ReadList.ResetList();
      length = ReadList.LengthIs();
 
       for(int count = 1; count <= length; count++)
        {
              ReadList.GetNextItem(item);
 
              if(!ReadList.invalidItem(item))
                {
                      //ReadList.Print(outFile);
                      //outFile << item.id << setw(20) << item.gpa << setw(20) << item.major[0] << item.major[1];
                      outFile << "  **** invalid line" << endl << endl;
                      ReadList.DeleteItem(item);
                }
        }
 
        ReadList.ResetList();
        length = ReadList.LengthIs();
outFile << "student id" << setw(12) << "GPA" << setw(22) << "Major" << endl;
        outFile << "----------" << setw(12) << "---" << setw(22) <<
                   "-----" << endl;
        for(int count = 1; count <= length; count++)
        {
                ReadList.GetNextItem(item);
                ReadList.Print(outFile);
                //outFile << item.id << setw(20) << item.gpa << setw(20) << item.major[0] << item.major[1];
                //outFile << endl;
        }
   outFile << "> > > end < < <" << endl;
 
        return 0;
}