ch03-ItemType.cpp

//------------------------------------------------------
//                      ItemType
// Class Implementation File
// Ch. 3, C++ Plus Data Structures, Dale 5e, p. 155
// Filename: ch03-ItemType.cpp
//------------------------------------------------------
#include <iostream>
#include <string>
#include "ch03-ItemType.h"
using namespace std;

//------------------------------
//         ItemType 
//     default constructor
//------------------------------
ItemType::ItemType()
{ value = 0; }

//------------------------------
//         ComparedTo
// Compares one ItemType object to another.  Returns
//   LESS, if self "comes before" item  
//   GREATER, if self "comes after" item 
//   EQUAL, if self and item are the same
//------------------------------
RelationType ItemType::ComparedTo(ItemType otherItem) const 
{
  if (value < otherItem.value)
    return LESS;
  else if (value > otherItem.value)
    return GREATER;
  else return EQUAL;
}

//------------------------------
//         Initialize
//------------------------------
void ItemType::Initialize(int number) 
{ value = number; }

//------------------------------
//           Print
// Adds ItemType value to output stream
//------------------------------
void ItemType::Print() const 
// pre:  out has been opened.
// post: value has been sent to the stream cout.
{ cout << value; }

ch03-ItemType.h

//------------------------------------------------------
//                       ItemType 
// Class Specification File
// Encapsulates type of items in list
// Ch. 3, C++ Plus Data Structures, Dale 5e, p. 154, 155
// same as code from Ch. 4 ItemType.h
// Filename: ch03-ItemType.h
//------------------------------------------------------
#include <string>
using namespace std;

#ifndef ITEMTYPE_H
#define ITEMTYPE_H

const int MAX_ITEMS = 25;
enum RelationType  {LESS, GREATER, EQUAL};

class ItemType 
{ 
  private:
    int value;
  public:
    ItemType();
    RelationType ComparedTo(ItemType) const;
    void Print() const;
    void Initialize(int number);
};
#endif

hw2-UnsortedType.cpp

//------------------------------------------------------
//                       UnsortedType
//         Linked List - Class Implementation File
// Your name                      
// Your class  CS3350 classtime
// Due date:   Thursday, September 13, 2012
//------------------------------------------------------
#include "hw2-UnsortedType.h"
#include <iostream>
using namespace std;

//---------------------------------------------
//           Constructor
//---------------------------------------------
UnsortedType::UnsortedType()
{
  length = 0;
  listData = NULL;
}

//---------------------------------------------
//           Destructor
// Deallocates all items in list
// Post: List is empty
//       All items have been deallocated
//---------------------------------------------
UnsortedType::~UnsortedType()
{
  NodeType* tempPtr;

  // Loop removes all nodes from list
  // deallocating space for each one
  while(listData != NULL)
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
}

//---------------------------------------------
//              MakeEmpty
// Returns the list to the empty state
// Post:  List is empty
//---------------------------------------------
void UnsortedType::MakeEmpty()
// Post: List is empty
{
  NodeType* tempPtr;

  // Loop removes all nodes from list
  // deallocating space for each one
  while(listData != NULL)
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
 
  length = 0;
}

//---------------------------------------------
//              IsFull
// Function:  Determines whether list is full.
// Pre:  List has been initialized.
// Post: Function value = (list is full)
// Returns: true if there is no room for another  
// ItemType on the free store; false otherwise.
//---------------------------------------------
bool UnsortedType::IsFull() const
{
  NodeType* location;
  // Try adding a new node, if successful, there
  // is room for more nodes so list is NOT full
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  // If adding a new node was unsuccessful,
  // the list is full
  catch(bad_alloc)
  {
    return true;
  }
}

//---------------------------------------------
//              GetLength
// Determines number of elements in list
// Pre:  List has been initialized
// Post: Number of items in the list is returned
//---------------------------------------------
int UnsortedType::GetLength() const
{
  return length;
}

//---------------------------------------------
//              PutItem
// Adds item to list
// Pre:  List has been initialized
//       List is not full
//       item is not in list
// Post: item is in list; length has been incremented
//---------------------------------------------
void UnsortedType::PutItem(ItemType item)
{
  NodeType* location = new NodeType;
  location->info = item;
  location->next = listData;
  listData = location;

  length++;			// Increment length of list
}

//---------------------------------------------
//              GetItem
// Retrieves list element whose key matches item's key (if present)
// Pre:  List has been initialized.
//       Key member of item is initialized.
// Post: If there is an element someItem whose key matches
//       item's key, then found = true and someItem is returned;
//       otherwise found = false and item is returned unchanged.
//       List is unchanged.
//---------------------------------------------
ItemType UnsortedType::GetItem(ItemType& item, bool& found)
{
  bool moreToSearch;
  NodeType* location;

  location = listData;
  found = false;

  moreToSearch = (location != NULL);

  while (moreToSearch && !found) 
  {
    switch (item.ComparedTo(location->info))
    {
      case LESS    : 
      case GREATER : location = location->next;
                     moreToSearch = (location != NULL);
                     break;
      case EQUAL   : found = true;
                     item = location->info;
                     break;
    }
  }
  return item;
}

//---------------------------------------------
//              DeleteItem
// Deletes the element whose key matches item's key.
// Pre:  List has been initialized.
//       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 UnsortedType::DeleteItem(ItemType item)
{
  NodeType* location;
  NodeType* tempLocation;

  location = listData;

  if (item.ComparedTo(location->info) == EQUAL)
  {
    tempLocation = location;
    listData = listData->next;
  }
  else
  {
    while (!((item.ComparedTo((location->next)->info) == EQUAL)))
      location = location->next;

    tempLocation = location->next;
    location->next = (location->next)->next;
  }

  delete tempLocation;
  length--;
}

//---------------------------------------------
//              ResetList
// Initializes current position for an iteration through the list
// Pre:  List has been initialized
// Post: Current position has been initialized
//       and is prior to list
//---------------------------------------------
void UnsortedType::ResetList()
{
  currentPos = NULL;
}

//---------------------------------------------
//              GetNextItem
// Gets next element in list
// Pre:  ResetList was called to initialize iteration
//       No transformer has been executed since last call
//       Current position is defined.
// Post: item is copy of element at current position
//       Current position is updated to next position
// Returns: copy of next item in list
//---------------------------------------------
ItemType UnsortedType::GetNextItem()
{
  if (currentPos == NULL)
    currentPos = listData;
  else
    currentPos = currentPos->next;

  return currentPos->info;
}

//---------------------------------------------
//              SplitList
// Splits a list into two lists
// Pre:  List has been initialized and is not empty
// Post: list1 contains all items of list whose keys are less than or equal to item's key
//       list2 contains all items of list whose keys are greater than item's key
//---------------------------------------------
void UnsortedType::SplitList(ItemType item, UnsortedType &list1, UnsortedType &list2)
{
  ItemType location;
  ResetList();
  for (int counter = 1, length = GetLength(); counter <= length; counter++)
  {
    location = GetNextItem();
	
	cout << "Parsing Item: ";
	location.Print();
	cout << endl;
	
    switch (location.ComparedTo(item))
    {
      case LESS    : 
      case EQUAL   : list1.PutItem(location);
                     break;
      case GREATER : list2.PutItem(location);
                     break;
    };
  };
}

hw2-UnsortedType.h

//------------------------------------------------------
//                    UnsortedType
//       Linked List - Class Specification File
// Your name                                
// Your class  CS3350 classtime
// Due date:   Thursday, September 13, 2012
//
// Defines an unsorted list type whose elements are of ItemType
// Ch. 3, C++ Plus Data Structures, Dale 5e, p. 183-185
// Filename: hw2-UnsortedType.h
// File ch03-ItemType.h must be provided by the user of this class. 
//  It must contain the following definitions: 
//  MAX_ITEMS:     the maximum number of items on the list 
//  RelationType:  {LESS, GREATER, EQUAL}, an enumerated type
//  ItemType:      class with definition of the objects in the list 
//------------------------------------------------------
#include "ch03-ItemType.h" 
using namespace std;

#ifndef UNSORTEDTYPE_H
#define UNSORTEDTYPE_H

class UnsortedType 
{
  private:
    struct NodeType
    {
      ItemType info;
      NodeType* next;
    };

    NodeType* listData;   // Pointer to head of list
    int length;           // # of items (nodes) in list
    NodeType* currentPos;

public:
  UnsortedType();         // Constructor
  ~UnsortedType();        // Destructor
  void MakeEmpty();       // Returns the list to the empty state
  bool IsFull() const;    // Determines whether list is full
  int  GetLength() const; // Determines the number of elements in list

  ItemType GetItem(ItemType& item, bool& found);
                          // Retrieves list element whose key 
                          // matches item's key (if present)
  void PutItem(ItemType item);     // Adds item to list
  void DeleteItem(ItemType item);  // Deletes element whose key 
                                   // matches item's key.

  void ResetList();       // Initializes current position for 
                          // an iteration through the list
  ItemType GetNextItem(); // Gets the next element in list
  void SplitList(ItemType item, UnsortedType &list1, UnsortedType &list2);
						  // Splits a list into two based on the item
};
#endif

hw2.cpp

//--------------------------------------------------------------
//          Test driver for Linked List UnsortedType list
// Navarr Barnier
// Your class  CS3350 TTh 1:00
// Due date:   Thursday, September 13, 2012
//
// Compile command: g++ hw2.cpp ch03-UnsortedType.cpp ch03-ItemType.cpp 
// Input file name: hw2.txt  
//   Contains list of commands to add items to list, split original
//   list into two lists, print each list and get the length of
//   each list.
// Output: The result of each command is displayed on the screen.
// Filename: hw2.cpp
//--------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <string>

#include "hw2-UnsortedType.h"
using namespace std;

void PrintList(UnsortedType&);
void SplitList(UnsortedType&, ItemType);

int main()
{

  ifstream inFile;       // file containing operations
  string command;        // operation to be executed
  
  int number;
  ItemType item;
  UnsortedType list;
  bool found;
  int numCommands;

  //----------------------------------------
  // Open input file with commands for testing
  // list operations, check success of open
  //----------------------------------------
  inFile.open("hw2.txt");
  if (!inFile)
  {
    cout << "Unable to open input file - ending program." << endl;
    exit(1);
  }


  //----------------------------------------
  // Read in and process commands to apply to list
  //----------------------------------------
  inFile >> command;
  numCommands = 0;
  while (command != "Quit")
  { 
    numCommands++;
    cout << "Command " << numCommands << ": " << command << "   ";

    //----------------------------------------
    //             PutItem
    //----------------------------------------
    if (command == "PutItem")
    {
      inFile >> number; 
      item.Initialize(number);
      list.PutItem(item);
      item.Print();
      cout << " added to list" << endl;
    }
    //----------------------------------------
    //             GetItem
    //----------------------------------------
    else if (command == "GetItem")
    {
      inFile >> number;
      item.Initialize(number);
      item = list.GetItem(item, found);
      item.Print();
      if (found)
        cout << " found in list." << endl;
      else 
        cout <<  " not in list."  << endl;  
    } 
    //----------------------------------------
    //             DeleteItem
    //----------------------------------------
    else if (command == "DeleteItem")
    {
      inFile >> number;
      item.Initialize(number);
      list.DeleteItem(item);
      item.Print();
      cout << " deleted from list" << endl;
    }
    //----------------------------------------
    //             GetLength
    //----------------------------------------
    else if (command == "GetLength")  
      cout << "Length of list = " << list.GetLength() << endl;

    //----------------------------------------
    //             IsFull
    //----------------------------------------
    else if (command == "IsFull")
      if (list.IsFull())
        cout << "List is full." << endl;
      else 
        cout << "List is not full."  << endl;  

    //----------------------------------------
    //             MakeEmpty
    //----------------------------------------
    else if (command == "MakeEmpty")
    {  list.MakeEmpty();
       cout << "List is empty." << endl;
    }

    //----------------------------------------
    //             PrintList
    // Non-member function to print list of items
    //----------------------------------------
    else if (command == "PrintList")
    {
      cout << "\n\nList values" << endl;
      PrintList(list);
    }
	
	//----------------------------------------
	//             SplitList
	// Split the list
	//----------------------------------------
	else if (command == "SplitList")
	{
	  inFile >> number;
	  item.Initialize(number);
	  SplitList(list,item);
	}

    //----------------------------------------
    //             Invalid command
    //----------------------------------------
    else
      cout << command << " is not a valid command." << endl;

    inFile >> command;
  };
 
  cout << "Testing completed."  << endl;
  inFile.close();
  return 0;
}


//----------------------------------------
//             PrintList
// Non-member function to print all items in list
// Pre:  list has been initialized
// Post: Each component in list has been written to cout
//----------------------------------------
void PrintList(UnsortedType &list)
{
  int length;
  ItemType item;

  list.ResetList();
  length = list.GetLength();
  for (int counter = 1; counter <= length; counter++)
  {
    item = list.GetNextItem();
    item.Print();
    cout << endl;
  }
  cout << "Length of list = " << length << endl << endl;
}

void SplitList(UnsortedType &list, ItemType item)
{
  UnsortedType list1, list2;
  list.SplitList(item,list1,list2);
  
  cout << "The list has been split into two." << endl << endl;
  cout << "List 1:" << endl;
  PrintList(list1);
  cout << "List 2:" << endl;
  PrintList(list2);
}

hw2.txt

GetLength
PutItem 5
PutItem 2
PutItem 9
PutItem 4
PutItem 7
PrintList
SplitList 6
PrintList
Quit