#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

private: int length; ItemType info[MAX_ITEMS]; int currentPos; };

Add a function to the SortedType class with the following signature:

bool IsThere(ItemType item) const;

Since this is an array backed data structure, a binary search algorithm

would work well here (

so

use one). Also, in the comments for this function, describe the

function in terms og BigO.

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; }; SortedType.h

How to write a function to merge two lists in sorted arrays?