Background In many applications the composition of a collect

Background:

In many applications, the composition of a collection of data items changes over time. Not only are new data items added and existing ones removed, but data items may be duplicated. A list data structure is a member of the general category of abstract data types called containers, whose purpose is to hold other objects. In C++, lists are provided in the Standard Template Library. However, for this assignment you will design and write your own linked list implementation to support the ADT operations specified below.

Objective:

Design and implement the specifications for a List Abstract Data Type where the items in the list are unsorted.

Requirements:

Define a list and develop a set of operations for creating and manipulating a list that satisfies the list ADT specification.

List ADT Specification

Structure: The list elements are of ItemType. The list has a property called the current position which designates the position of the last element accessed by GetNextItem during an iteration through the list. Only ResetList and GetNextItem alter the current position.

Definitions (provided by the user):

MAX_ITEMS:       A constant specifying the maximum capacity of items allowed on the list

Item Type:             Class encapsulating the type of items in the list

RelationType:       An enumeration type that consists of LESS, GREATER, EQUAL

Member function of ItemType that must be included:

RelationType ComparedTo(ItemType Item)

Function:               Determines the ordering of two ItemType objects based on their keys

Precondition:       Self and item have their key members initialized

Postcondition:      

   Function value = LESS if the key of self is less than the key of item

                                = GREATER if the key of self is greater than the key of item

                                = EQUAL if the keys are equal

Operations (provided by Unsorted List ADT)

Make Empty

Function:               Initializes list to empty state

Preconditions:      None

Postcondition:      List is empty

Boolean IsFull

Function:               Determines whether list is full

Preconditions:      List has been initialized

Postcondition:      Function value = (list is full)

int GetLength

Function:               Determines the number of elements in list

Preconditions:      List has been initialized

Postcondition:      Function value = number of elements in list

ItemType GetItem(Item Typeitem, Boolean& found)

Function:               Get list element whose key matches item’s key (if present)

Preconditions:      List has been initialized

                                Key member of item is initialized

Postcondition:      If there is an element someItem whose keymatches item’s key, then found = true and copy of  someItemis returned; otherwise found = false and item is returned

                                List is unchanged

PutItem(ItemType item)

Function:               Puts item into list

Preconditions:      List has been initialized

                                List is not full

                                Item is not in list

Postcondition:      Item is in the list

DeleteItem(ItemType item)

Function:               Deletes the element whose key matches item’s key

Preconditions:      List has been initialized

Postcondition:      One and only one element in list has a key matching item’s key

ResetList

Function:               Initializes current position for an iteration through the list

Preconditions:      List has been initialized

Postcondition:      Current position is prior to list

ItemType GetNextItem()

Function:               Gets the next element in list

Preconditions:      List has been initialized

                                Current position is defined

                                Element at current position is not last in list

Postcondition:      Current position is updated to next position

                                Returns a copy of element at current position

UML

The UML diagrams for the linked class UnsortedList are included as an attachment.

Test Run Requirements: Only submit one run that shows a sample client that instantiates a list object, reads in test data from the listData test file and writes the test results to the a3testFirstnameLastname file (for FirstnameLastname your Firstname and Lastname).

Grading Criteria:

ItemType class is correctly defined and implemented.

UnsortedType class is correctly defined and implemented.  

Program compiles and runs.

Implementation supports the operations given in the ADT functional requirements.

A test driver is included to satisfy the test run demonstration.

A copy of your test run output display is included in an output file named a3testFirstnameLastname

Be sure to include 6 separate files:

ItemType.h

ItemType.cpp

unsorted.h

unsorted.cpp

listDr.cpp

Solution

//---------------------------ItemType.cpp-----------------------------------------------------------------------------

#include <iostream>
#include <string>
#include \"ch03-ItemType.h\"
using namespace std;

ItemType::ItemType()
{ value = 0;
}

RelationType ItemType::ComparedTo(ItemType otherItem) const
{
if (value < otherItem.value)
    return LESS;
else if (value > otherItem.value)
    return GREATER;
else return EQUAL;
}

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

void ItemType::Print() const
{
cout << value;
}

//---------------------------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

//---------------------------Unsorted.h-----------------------------------------------------------------------------
#include \"ch03-ItemType.h\"
using namespace std;

#ifndef UNSORTEDTYPE_H
#define UNSORTEDTYPE_H

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

    NodeType* listData;
    int length;         
    NodeType* currentPos;

public:
UnsortedType();       
~UnsortedType();      
void MakeEmpty();     
bool IsFull() const;  
int GetLength() const;

ItemType GetItem(ItemType& item, bool& found);
                        
void PutItem(ItemType item);   
void DeleteItem(ItemType item);

void ResetList();     
ItemType GetNextItem();
void SplitList(ItemType item, UnsortedType &list1, UnsortedType &list2);
};
#endif

//---------------------------Unsorted.cpp-----------------------------------------------------------------------------
#include \"hw2-UnsortedType.h\"
#include <iostream>
using namespace std;

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

UnsortedType::~UnsortedType()
{
NodeType* tempPtr;

while(listData != NULL)
{
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
}
}

void UnsortedType::MakeEmpty()
{
NodeType* tempPtr;
while(listData != NULL)
{
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
}

length = 0;
}

bool UnsortedType::IsFull() const
{
NodeType* location;
try
{
    location = new NodeType;
    delete location;
    return false;
}
catch(bad_alloc)
{
    return true;
}
}

int UnsortedType::GetLength() const
{
return length;
}

void UnsortedType::PutItem(ItemType item)
{
NodeType* location = new NodeType;
location->info = item;
location->next = listData;
listData = location;

length++;          
}

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;
}

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--;
}

void UnsortedType::ResetList()
{
currentPos = NULL;
}

ItemType UnsortedType::GetNextItem()
{
if (currentPos == NULL)
    currentPos = listData;
else
    currentPos = currentPos->next;

return currentPos->info;
}

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;
    };
};
}

//------------------------------------------------listDr.cpp---------------------------------------------------------
#include <iostream>
#include <fstream>
#include <string>

#include \"ListDr-UnsortedType.h\"
using namespace std;

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

int main()
{

ifstream inFile;     
string command;      

int number;
ItemType item;
UnsortedType list;
bool found;
int numCommands;

inFile.open(\"listhw.txt\");
if (!inFile)
{
    cout << \"Unable to open input file - ending program.\" << endl;
    exit(1);
}

inFile >> command;
numCommands = 0;
while (command != \"Quit\")
{
    numCommands++;
    cout << \"Command \" << numCommands << \": \" << command << \"   \";

    if (command == \"PutItem\")
    {
      inFile >> number;
      item.Initialize(number);
      list.PutItem(item);
      item.Print();
      cout << \" added to list\" << endl;
    }
    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;
    }
    else if (command == \"DeleteItem\")
    {
      inFile >> number;
      item.Initialize(number);
      list.DeleteItem(item);
      item.Print();
      cout << \" deleted from list\" << endl;
    }
    else if (command == \"GetLength\")
   {
      cout << \"Length of list = \" << list.GetLength() << endl;
    }
    else if (command == \"IsFull\")
   {
      if (list.IsFull())
        cout << \"List is full.\" << endl;
      else
        cout << \"List is not full.\" << endl;
   }
    else if (command == \"MakeEmpty\")
    { list.MakeEmpty();
       cout << \"List is empty.\" << endl;
    }
    else if (command == \"PrintList\")
    {
      cout << \"\ \ List values\" << endl;
      PrintList(list);
    }
   else if (command == \"SplitList\")
   {
      inFile >> number;
      item.Initialize(number);
      SplitList(list,item);
   }
    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);
}