SortedLinkedList.h

#include "ItemType.h"

template<class ItemType>
struct NodeType;

template<class ItemType> 
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)

  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(); 

 private:
  NodeType<ItemType>* listData;
  int length;
  NodeType<ItemType>* currentPos;
};
 
template<class ItemType>
struct NodeType
{
  ItemType info;
  NodeType* next;
};

template<class ItemType>
SortedType<ItemType>::SortedType()  // Class constructor
{
  length = 0;
  listData = NULL;
}

template<class ItemType>
SortedType<ItemType>::~SortedType()
// Post: List is empty; all items have been deallocated.
{
  MakeEmpty();
}

template<class ItemType>
SortedType<ItemType>::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<ItemType>* fromPtr;  // Pointer into list being copied from
    NodeType<ItemType>* toPtr;    // Pointer into new list being built
    if(otherList.listData == NULL)
    {
        listData = NULL;
        return;
    }
    // Copy first node
    fromPtr = otherList.listData;
    listData = new NodeType<ItemType>;
    listData->info = fromPtr->info;

    // Copy remaining nodes

    toPtr = listData;
    fromPtr = fromPtr->next;
    while (fromPtr != NULL)
    {
        toPtr->next = new NodeType<ItemType>;
        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;
  }
} */

template<class ItemType>
bool SortedType<ItemType>::IsFull() const
// Returns true if there is no room for another ItemType
// object on the free store; false otherwise.
{
  NodeType<ItemType>* ptr;

  ptr = new NodeType<ItemType>;
  if (ptr == NULL)
    return true;
  else
  {
    delete ptr;
    return false;
  }
}

template<class ItemType>
int SortedType<ItemType>::LengthIs() const
// Post: Number of items in the list is returned.
{
  return length;
}

template<class ItemType>
void SortedType<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
  NodeType<ItemType>*
  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
}

template<class ItemType>
void SortedType<ItemType>::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<ItemType>* location = listData;
  NodeType<ItemType>* tempLocation;

  // Locate node to be deleted.
  if (item == listData->info)  {
    tempLocation = location;
    listData = listData->next;          // Delete first node.
  }
  else
  {
    while (!(item==(location->next)->info))
      location = location->next;

    // Delete node at location->next
    tempLocation = location->next;
    location->next = (location->next)->next;
  }
  delete tempLocation;
  length--;
}

template<class ItemType>
void SortedType<ItemType>::ResetList()
// Post: Current position has been initialized to AtEnd
{
  currentPos = NULL;
}

template<class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
  bool moreToSearch;
  NodeType<ItemType>* location;

  location = listData;
  found = false;
  moreToSearch = (location != NULL);

  while (moreToSearch && !found)
  {
    if (location->info < item)
    {
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else if (item == location->info)
    {
      found = true;
      item = location->info;
    }
    else
      moreToSearch = false;
  }
}

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
  NodeType<ItemType>* newNode;  // pointer to node being inserted
  NodeType<ItemType>* predLoc;  // trailing pointer
  NodeType<ItemType>* location; // traveling pointer
  bool moreToSearch;

  location = listData;
  predLoc = NULL;
  moreToSearch = (location != NULL);

  // Find insertion point.
  while (moreToSearch)
  {
    if (location->info < item)
    {
      predLoc = location;
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else
      moreToSearch = false;
 }
  // Prepare node for insertion
  newNode = new NodeType<ItemType>;
  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++;
}

template<class ItemType>
void SortedType<ItemType>::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;
}

template<class ItemType>
void SortedType<ItemType>::Print()
{
   currentPos = listData;

   while(currentPos != NULL)
   {
       cout << currentPos->info << " ";
       currentPos = currentPos->next;
   }
}

runSortedLinkedList.cxx
#include "SortedLinkedList.h"
#include <fstream>

using namespace std;
template<class ItemType>
void FileToList(SortedType<ItemType>& intList, ifstream& inFile, ofstream&
outFile);
// PURPOSE: To take an item from the GetItemFromFile function, and to add
// it if addOrDelete was 'A' or delete it if addOrDelete was 'D'. Also to
// print error messages accordingly.
// INPUT: intList, inFile
// PRE: intList is declared, inFile is OK, outFile is OK
// OUTPUT: outFile
// POST: An item(s) were written to intList with an error message if
// according
// NOTE: none

template <class ItemType>
void ListToFile(SortedType<ItemType>& intList, ofstream& outFile);
// PURPOSE: To print the list to a file as long as data exists in the list
// INPUT: intList
// PRE: intList is declared and OK, outFile is OK
// OUTPUT: outFile
// POST: All items are written to the outFile
// NOTE: none

int main()
{
   ifstream inFile;
   ofstream outFile;
   SortedType<int> intList;

   FileToList(intList, inFile, outFile);
   ListToFile(intList, outFile);

   return 0;
}


void FileToList(SortedType<ItemType>& intList, ifstream& inFile, ofstream&
outFile)
{
   ItemType item;
   char addOrDelete;

   inFile.open("in.data");
   intList.MakeEmpty();
   addOrDelete = item.GetItemFromFile(inFile);
   while (inFile)
   {
      if (addOrDelete == 'A')
      {
         if (!intList.IsFull())
            intList.InsertItem(item);
         else{
            ListToFile(intList, outFile);
            item.PrintLstFullErr(outFile);
         }
         addOrDelete = item.GetItemFromFile(inFile);
      }
      else if (addOrDelete == 'D')
      {
         if(intList.LengthIs() == 0){
            ListToFile(intList, outFile);
            item.PrintEmptyLstErr(outFile);
         }
         else
         {
            intList.DeleteItem(item);
         }
         addOrDelete = item.GetItemFromFile(inFile);
      }
   }
}

void ListToFile(SortedType<ItemType>& intList, ofstream& outFile)
{
   ItemType item;
   int length;

   outFile.open("out.data");
   intList.ResetList();
   length = intList.LengthIs();

   outFile << "STUDENT ID" << setw(6) << "EXAM1" << setw(10) << "EXAM2"
           << setw(9) << "FINAL" << setw(9) << "PROG" << setw(14)
           << "QUIZZES" << endl;
   for (int count = 1; count <= length; count++)
   {
      intList.GetNextItem(item);
      item.WriteItemToFile(outFile);
   }
}

int a;
a.somefunction();

SomeClass *c;
c.someFunction() //where is should be c->someFunction();

SortedType<int> intList;

addOrDelete = item.GetItemFromFile(inFile);

ItemType item;

int.GetItemFromFile(inFile);