SortedArray Container class Elements in the SortedArray should be always in the non decreasing order Unlike basic arrays that burden the programmer with the task of keeping track of its capacity and utilization, the SortedArray must also provide an interface to the programmer to allow for retrieval of information about the number of elements inside it as well as the maximum number of elements it can store Requirements SortedArray MUST store elements internally in an array Please refer to the vector implementation example in the lecture slides 2 1 SortedArray MUST be able to store elements of any comparable type that provides operator Interface The interface of SortedArray is provided in the attached SortedArray h file It provides for the following public functionality, all of which can be achieved using an internal array representation for the data SortedArray() no argument constructor Initializes the internal array to some pre specified size SortedArray() destructor SortedArray(const SortedArray ) copy constructor SortedArray operator invoked by the copy constructor const Object operator (int)const returns the ith element stored in this SortedArray, where the 1st element is the element in the front bool equals (const SortedArray rhs) returns true if this array and the rhs array have the same elements, in the same order (The capacity of the containers may be different, only the actual number of elements in each must be the same for the call to return true ) void clear() removes all the elements of the container This SortedArray should still be useful after a call to this function Note, should not delete the array, just set the size properly bool empty() returns true if the SortedArray contains no elements, and false otherwise void print(ostream os, char delimiter ',') const print all elements of SortedArray to ostream os Each element is followed by a delimiter except the last element int size() returns the number of elements stored in this SortedArray, which may be less than its capacity int capacity() returns the current capacity of this SortedArray void reserve(int newCapacity) sets the new capacity MUST report an error current size is already larger than the requested capacity MAY do nothing if the existing capacity (but not the size) is larger than the requested capacity void insert(const Object ) insert new elements into the correct position in the array, sliding elements over the position to right, as needed void deleteMin( ) remove the element in position 0, and slide over all the other item void deleteMax( ) remove the last element const Object findMin( ) const find the minimum element const Object findMax( ) const find the maximum element int binarySearch (const Object x) Performs the standard binary search using two comparisons per level, see the lecture slides 3 Returns index where item is found or 1 if not found Note 1, three additional files are provided SortedArray h is the header file You should not modify it SortedArray cpp is simply a skeleton You will need to complete it and implement each member function inside it program1Test cpp is a simple test program You should only add SortedArray h and program1Test cpp, but not SortedArray cpp (which is already included in SortedArray h file) File 1 program1Test cpp Desecription A Test Program for Program 1 include include include SortedArray h using namespace std const int N 1787 const int M 2357 int main( ) SortedArray q SortedArray animals string str1 zebra , tiger , lion , dog , monkey , snake , turkey , cat , duck , alligator int minVal1, maxVal1 int i, j int index for( i N i 0 i ( i N ) M ) q insert( i ) cout while ( q empty( )) cout 0) cout 0) cout animalsCopy (animals) if (animalsCopy equals(animals)) cout File 2 SortedArray cpp skeleton ifndef SORTEDARRAY CPP define SORTEDARRAY CPP include SortedArray h Default constructor template SortedArray SortedArray() Copy constructor template SortedArray SortedArray(const SortedArray from) destructor template SortedArray SortedArray() overloaded assignment operator template const SortedArray SortedArray operator (const SortedArray from) Accessor Operator template const Object SortedArray operator (int idx) const check if two sorted arrays are the same template bool SortedArray equals(const SortedArray rhs) check if the array is empty template bool SortedArray empty() const get the size template int SortedArray size() const get the capacity template int SortedArray capacity() const reserve template void SortedArray reserve(int newCapacity) print elements of the array template void SortedArray print(ostream out, char delimiter) const clear array of elements template void SortedArray clear () insert element into sorted array template void SortedArray insert(const Object obj) remove the first element template void SortedArray deleteMin() delete the maximum element from the sorted array template void SortedArray deleteMax() find the minimum element in the sorted array template const Object SortedArray findMin() const find the max element in the sorted array template const Object SortedArray findMax() const binary search the array template int SortedArray binarySearch(const Object obj) endif File 3 File SortedArray h Description Definition of the class template SortedArray Date Created Last Modified ifndef SortedArray H define SortedArray H INCLUDES include using namespace std SortedArray template class SortedArray public LIFECYCLE Default constructor SortedArray() Copy constructor param from The oject to copy to this object SortedArray(const SortedArray from) Destructor SortedArray() OPERATORS Assignment operator param from The value to assign to this object return A reference to this object const SortedArray operator (const SortedArray from) Accessor Operator param idx return a constant reference to the object at index idx in the array, with no bounds checking const Object operator (int idx) const equals param rhs return true if this array and the rhs array have the same elements, in the same order (The capacity of the containers may be different, only the actual number of elements in each must be the same for the call to return true ) bool equals(const SortedArray rhs) empty return true if the array contains no elments, and false otherwise bool empty() const size return the number of elements in the container int size() const capacity return the internal capacity of the array int capacity() const reserve param capacity Description sets the new capacity MAY do nothing if the existing capacity (but not the size) is larger than the requested capacity void reserve(int) DISPLAY METHODS void print(ostream out, char delimiter ',') const SORTED ARRAY PROTOCOTLS clear Description removes all the elements of the sorted array void clear () insert param obj Description insert new elements into the correct position in the sorted array, sliding elements over the position to right, as needed void insert(const Object obj) Description remove the element in position 0, and slide over all other item void deleteMin() Description remove the last element in the sorted array void deleteMax() Description find the minimum element in the sorted array const Object findMin() const Description find the maximum element in the sorted array const Object findMax() const binarySearch param obj the item to be searched return index where item is found or 1 if not found Description performs the standard binary search using two comparisons per level int binarySearch (const Object obj) enum SPARE CAPACITY 16 private int theSize int theCapacity Object objects include SortedArray cpp endif Sample Output Completed first round of insertions Completed first round of deletions Completed second round of insertions 1177 1180 1178 1179 Completed the Integer Array test Animal list alligator cat dog duck lion monkey snake tiger turkey zebra lion is found in the list Bear is not found in the list Correct The two animal lists are the same Animal list after the deletion cat dog duck lion monkey snake tiger turkey Completed the String Array test

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Oct 15, 2024

SortedArray Container class. Elements in the SortedArray should be always in the non-decreasing order. Unlike basic arrays that burden the programmer with the task of

SortedArray Container class. Elements in the SortedArray should be always in the non-decreasing order. Unlike basic arrays that burden the programmer with the task of keeping track of its capacity and utilization, the SortedArray must also provide an interface to the programmer to allow for retrieval of information about the number of elements inside it as well as the maximum number of elements it can store. Requirements ? SortedArray MUST store elements internally in an array. Please refer to the vector implementation example in the lecture slides 2-1. ? SortedArray MUST be able to store elements of any comparable type that provides operator

Interface The interface of SortedArray is provided in the attached SortedArray.h file. It provides for the following public functionality, all of which can be achieved using an internal array representation for the data. ? SortedArray(): no-argument constructor. Initializes the internal array to some pre- specified size. ? ~SortedArray(): destructor. ? SortedArray(const SortedArray

? const Object & findMin( ) const: find the minimum element. ? const Object & findMax( ) const: find the maximum element. ? int binarySearch (const Object & x): Performs the standard binary search using two comparisons per level, see the lecture slides 3. Returns index where item is found or -1 if not found.

Note 1, three additional files are provided. SortedArray.h is the header file. You should not modify it. SortedArray.cpp is simply a skeleton. You will need to complete it and implement each member function inside it. program1Test.cpp is a simple test program. You should only add SortedArray.h and program1Test.cpp, but not SortedArray.cpp (which is already included in SortedArray.h file).

File 1:

/** program1Test.cpp * * Desecription: A Test Program for Program 1 */ #include #include #include "SortedArray.h" using namespace std; const int N = 1787; const int M = 2357; int main( ) { SortedArray q; SortedArray animals; string str1[] = {"zebra", "tiger", "lion", "dog", "monkey", "snake", "turkey", "cat", "duck", "alligator"}; int minVal1, maxVal1; int i, j; int index; for( i = N; i != 0; i = ( i + N ) % M ) q.insert( i ); cout

while (!q.empty( )) { cout = 0) { cout = 0) { cout animalsCopy (animals); if (animalsCopy.equals(animals)) { cout

File 2:

/* SortedArray.cpp skeleton */ #ifndef SORTEDARRAY_CPP #define SORTEDARRAY_CPP #include "SortedArray.h" // Default constructor template SortedArray

} //get the capacity template int SortedArray

const Object & SortedArray

File 3:

/** * File: SortedArray.h * * Description: Definition of the class template SortedArray

/** equals * * @param rhs * * @return true if this array and the rhs array have * the same elements, in the same order. (The capacity of the containers * may be different, only the actual number of elements in each * must be the same for the call to return true.) */ bool equals(const SortedArray

* Description: remove the element in position 0, and slide over all * other item */ void deleteMin(); /** * Description: remove the last element in the sorted array */ void deleteMax(); /** * Description: find the minimum element in the sorted array */ const Object & findMin() const; /** * Description: find the maximum element in the sorted array */ const Object & findMax() const; /**binarySearch * * @param obj: the item to be searched * * @return index where item is found or -1 if not found. * * Description: performs the standard binary search using two comparisons * per level. */ int binarySearch (const Object &obj); enum { SPARE_CAPACITY = 16 }; private: int theSize; int theCapacity; Object *objects; }; #include "SortedArray.cpp" #endif

Sample Output:

Completed first round of insertions Completed first round of deletions Completed second round of insertions 1177 1180 1178 1179 Completed the Integer Array test Animal list: alligator cat dog duck lion monkey snake tiger turkey zebra lion is found in the list. Bear is not found in the list. Correct! The two animal lists are the same. Animal list after the deletion: cat dog duck lion monkey snake tiger turkey Completed the String Array test