Write the program that is already given you just need to write a given function prototype below and to test each function more than once (more details are given below). And the given program is all the way down start from or as "Given Program" include (main.cpp,SortedType.cpp,SortedType.h,ItemType.cpp,ItemType.h).

Below are the function prototypes that you must implement. Also, each function must be tested more than once (ex. in your testIsThere, test for more than one number to insure it works (one you know is there and one you dont at a minimum)).

SortedType createTestList(int numbers[], int count); //Used to create lists for your tests

...or if you prefer

void createTestList(SortedType &list, int numbers[], int count); //This would just populate your list

These functions should return true if the tests passed (which should be the case)

bool testIsThere();

bool testMergeLists();

bool testSplitLists();

Use the following data sets for Merge Lists:

List1 -> 0,3,1,5,9

List2 -> 7,4,6,10,8

...and for isThere and Split:

List -> 0,3,1,5,9,7,4,6,10,8

All code must be commented including the functions themselves. After you write the function prototype, if you type /** in the line above it followed by enter, it will automatically create the following for you (using creatTestList):

/**

*

* @param numbers

* @param count

* @return

*/

Finally, some well-formatted output would be nice (actually required) with the results from each test using the functions return value (true for pass), these printouts must not be in the functions themselves.

Put in logical debugging code (that prints out in each function what is happening) that can be turned on or off using a define statement.

Given Program starts

main.cpp

// Test driver

#include

#include

#include

#include

#include

#include "SortedType.h"

using namespace std;

void PrintList(ofstream& outFile, SortedType list);

int main()

{

ifstream inFile; // file containing operations

ofstream outFile; // file containing output

string inFileName; // input file external name

string outFileName; // output file external name

string outputLabel;

string command; // operation to be executed

int number;

ItemType item;

SortedType list;

bool found;

int numCommands;

// Prompt for file names, read file names, and prepare files

cout << "Enter name of input command file; press return." << endl;

cin >> inFileName;

inFile.open(inFileName.c_str());

cout << "Enter name of output file; press return." << endl;

cin >> outFileName;

outFile.open(outFileName.c_str());

cout << "Enter name of test run; press return." << endl;

cin >> outputLabel;

outFile << outputLabel << endl;

inFile >> command;

numCommands = 0;

while (command != "Quit")

{

outFile << command;

if (command == "PutItem")

{

inFile >> number;

item.Initialize(number);

list.PutItem(item);

item.Print(outFile);

outFile << " is inserted" << endl;

}

else if (command == "DeleteItem")

{

inFile >> number;

item.Initialize(number);

list.DeleteItem(item);

item.Print(outFile);

outFile << " is deleted" << endl;

}

else if (command == "GetItem")

{

inFile >> number;

item.Initialize(number);

list.GetItem(item, found);

if (found)

outFile << number << " found in list." << endl;

else outFile << number << " not in list." << endl;

}

else if (command == "GetLength")

outFile << " Length is " << list.GetLength() << endl;

else if (command == "IsFull")

if (list.IsFull())

outFile << "List is full." << endl;

else outFile << "List is not full." << endl;

else if (command == "MakeEmpty")

list.MakeEmpty();

else if (command == "PrintList")

PrintList(outFile, list);

else cout << " Command not recognized." << endl;

numCommands++;

cout << " Command number " << numCommands << " completed."

<< endl;

inFile >> command;

};

cout << "Quit" << endl << "Testing completed." << endl;

inFile.close();

outFile.close();

return 0;

}

void PrintList(ofstream& dataFile, SortedType list)

// Pre: list has been initialized.

// dataFile is open for writing.

// Post: Each component in list has been written to dataFile.

// dataFile is still open.

{

int length;

ItemType item;

list.ResetList();

length = list.GetLength();

for (int counter = 1; counter <= length; counter++)

{

ItemType item;

item = list.GetNextItem();

item.Print(dataFile);

}

dataFile << endl;

}

void MergeLists(SortedType list1, SortedType list2,SortedType& result)

{

int length1;

int length2;

int counter1 = 1;

int counter2 = 1;

ItemType item1;

ItemType item2;

length1 = list1.GetLength();

length2 = list2.GetLength();

list1.ResetList();

list2.ResetList();

item1 = list1.GetNextItem();

item2 = list2.GetNextItem();

result.MakeEmpty();

while (counter1 <= length1 && counter2 <= length2)

switch (item1.ComparedTo(item2))

{

case LESS : result.PutItem(item1);

item1 = list1.GetNextItem();

counter1++;

break;

case EQUAL : result.PutItem(item1);

counter1++;

counter2++;

item1 = list1.GetNextItem();

item2 = list2.GetNextItem();

break;

case GREATER: result.PutItem(item2);

counter2++;item2 = list2.GetNextItem();

break;

}

if (counter1 <= length1)result.PutItem(item1);

for (counter1; counter1 < length1;counter1++)

{

item1 = list1.GetNextItem();

result.PutItem(item1)

;

}

if (counter2 <= length2)result.PutItem(item2);

for (counter2; counter2 < length2; counter2++)

{

result.PutItem(item2);

item2 = list2.GetNextItem();

}

}

void SplitLists(SortedType& list, ItemType item,SortedType& list1, SortedType& list2)

{

int length;ItemType tempItem;

int counter = 1;

bool inList1;

list1.MakeEmpty();

list2.MakeEmpty();

length = list.GetLength();

//list.ResetList();

tempItem = list.GetNextItem();

inList1 = (tempItem.ComparedTo(item) == LESS ||tempItem.ComparedTo(item) == GREATER);

while (inList1 && counter <= length)

{

list1.PutItem(tempItem);

if (counter < length)

{

tempItem = list.GetNextItem();

inList1 = (tempItem.ComparedTo(item) == LESS ||tempItem.ComparedTo(item) == GREATER);

counter++;

}

}

for (int count = counter; count <= length; count++)

{

list2.PutItem(tempItem);

if (count < length)tempItem = list.GetNextItem();

}

}

SortedType.cpp

// Implementation file for sorted.h

#include "SortedType.h" using namespace std;

SortedType::SortedType() { length = 0; }

void SortedType::MakeEmpty() { length = 0; }

bool SortedType::IsFull() const { return (length == MAX_ITEMS); }

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

ItemType SortedType::GetItem(ItemType item, bool& found) { int midPoint; int first = 0; int last = length - 1;

bool moreToSearch = first <= last; found = false; while (moreToSearch && !found) { midPoint = ( first + last) / 2; switch (item.ComparedTo(info[midPoint])) { case LESS : last = midPoint - 1; moreToSearch = first <= last; break; case GREATER : first = midPoint + 1; moreToSearch = first <= last; break; case EQUAL : found = true; item = info[midPoint]; break; } } return item; }

void SortedType::DeleteItem(ItemType item) { int location = 0;

while (item.ComparedTo(info[location]) != EQUAL) location++; for (int index = location + 1; index < length; index++) info[index - 1] = info[index]; length--; }

void SortedType::PutItem(ItemType item) { bool moreToSearch; int location = 0;

moreToSearch = (location < length); while (moreToSearch) { switch (item.ComparedTo(info[location])) { case LESS : moreToSearch = false; break; case GREATER : location++; moreToSearch = (location < length); break; } } for (int index = length; index > location; index--) info[index] = info[index - 1]; info[location] = item; length++; }

void SortedType::ResetList() // Post: currentPos has been initialized. { currentPos = -1; }

ItemType SortedType::GetNextItem() // Post: item is current item. // Current position has been updated. { currentPos++; return info[currentPos]; }

bool SortedType::IsThere(ItemType item) { int midPoint; int first = 0; int last = length - 1; bool moreToSearch = first <= last; bool found = false; while (moreToSearch && !found) { midPoint = (first + last) / 2; switch (item.ComparedTo(info[midPoint])) { case LESS : last = midPoint - 1; moreToSearch = first <= last; break; case GREATER : first = midPoint + 1; moreToSearch = first <= last; break; case EQUAL : found = true; break; } } return found; }

void SortedType::SplitLists(ItemType item, SortedType& list1, SortedType& list2) { int counter = 0; list1.MakeEmpty(); list2.MakeEmpty(); while (info[counter].ComparedTo(item) == LESS||info[counter].ComparedTo(item) == EQUAL) { list1.PutItem(info[counter]); counter++; } for (counter; counter < length; counter++) { list2.PutItem(info[counter]); } }

SortedType.h

#include "ItemType.h"

// File ItemType.h must be provided by the user of this class.

// ItemType.h must contain the following definitions:

// MAX_ITEMS: the maximum number of items on the list

// ItemType: the definition of the objects on the list

// RelationType: {LESS, GREATER, EQUAL}

// Member function ComparedTo(ItemType item) which returns

// LESS, if self "comes before" item

// GREATER, if self "comes after" item

// EQUAL, if self and item are the same

class SortedType

{

public:

SortedType();

void MakeEmtpy();

// Function: Returns list to the empty state

// Post: List is empty.

bool IsFull() const;

// Function: Determines whether list is full.

// Pre: List has been initialized.

// Post: Function value = (list is full)

int GetLength() const;

// Function: Determines the number of elements in list.

// Pre: List has been initialized.

// Post: Function value = number of elements in list

ItemType GetItem(ItemType item, bool& found);

// Function: 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 item is returned;

// someItem; otherwise found = false and item is returned.

// List is unchanged.

void PutItem(ItemType item);

// Function: Adds item to list.

// Pre: List has been initialized.

// List is not full.

// item is not in list.

// List is sorted.

// Post: item is in list.

// List is sorted

void DeleteItem(ItemType item);

// Function: 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.

// List is sorted.

void ResetList();

// Function: Initializes current position for an iteration through the list.

// Pre: List has been initialized.

// Post: Current position is prior to list.

ItemType GetNextItem();

// Function: Gets the next element in list.

// Pre: List has been initialized and has not been changed since last call.

// Current position is defined.

// Element at current position is not last in list.

//

// Post: Current position is updated to next position.

// Returns a copy of element at current position.

void MakeEmpty();

// Function: Make the list empty

// Pre: List has been initialized.

// Post: The list is empty

bool IsThere(ItemType item);

// Function: Searches the sorted list of an item.

// Precondition: list is initialized and is sorted according to the ComparedTo

// function.

// Postcondition: Returns true if the key is found else returns false.

void SplitLists(ItemType, SortedType&, SortedType&);

private:

int length;

ItemType info[MAX_ITEMS];

int currentPos;

};

ItemType.cpp

// The following definitions go into file ItemType.cpp. #include #include #include "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(std::ostream& out) const // pre: out has been opened. // post: value has been sent to the stream out. { out << value; }

ItemType.h

// The following declarations and definitions go into file // ItemType.h.

#include const int MAX_ITEMS = 5; enum RelationType {LESS, GREATER, EQUAL};

class ItemType { public: ItemType(); RelationType ComparedTo(ItemType) const; void Print(std::ostream&) const; void Initialize(int number); private: int value; };