/* The SimpleVector class template (see source code below) has been enhanced to
ID: 3576686 • Letter: #
Question
/* The SimpleVector class template (see source code below) has been enhanced to include SortableVector class
template which sorts an array of objects in ascending order.
Additionally, SearchableVector class template which performs a binary search has been developed to enhanced
the SortableVector class template .
A driver program has also been provided to test both enhancements.
***********************************
Your assignments:
1. Complete/fix the missing parts of both the SortableVector and SearchableVector class templates such that the output
from the driver program should look like the following:
Before calling SortAndSearch(), these values are in intTable:
54321
Before calling SortAndSearch() these values are in doubleTable:
Have A Happy And Safe Holiday
After calling SortAndSearch(). these values are in intTable:
12345
After calling SortAndSearch().these values are in doubleTable:
A And Safe Happy Have Holiday
The value 5 was found in vector position 5
The value Happy was found in vector position 3
*************************************
Other than where noted; modifications should be properly commented
such as :
// ******************changed****************
The driver (main ()) program in general does not need any modification
*************************************
*/
// Inheritance Modification
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <new> // Needed for bad_alloc exception
#include <cstdlib> // Needed for the exit function
#include <string>
using namespace std;
template <typename T>
class SimpleVector
{
private:
T *aptr; // To point to the allocated array
int arraySize; // Number of elements in the array
void memError(); // Handles memory allocation errors
void subError(); // Handles subscripts out of range
public:
// Default constructor
SimpleVector()
{ aptr = 0; arraySize = 0;}
// Constructor declaration
SimpleVector(int);
// Copy constructor declaration
SimpleVector(const SimpleVector &);
// Destructor declaration
~SimpleVector();
// Accessor to return the array size
int size() const
{ return arraySize; }
// Accessor to return a specific element
T getElementAt(int position);
// Overloaded [] operator declaration
T &operator[](const int &);
void push_back(T); // New push_back member
T pop_back(); // New pop_back member
};
//***********************************************************
// Constructor for SimpleVector class. Sets the size of the *
// array and allocates memory for it. *
//***********************************************************
template <typename T>
SimpleVector<T>::SimpleVector(int s)
{
arraySize = s;
// Allocate memory for the array.
try
{
aptr = new T [s];
}
catch (bad_alloc)
{
memError();
}
}
//*******************************************
// Copy Constructor for SimpleVector class. *
//*******************************************
template <typename T>
SimpleVector<T>::SimpleVector(const SimpleVector &obj)
{
// Copy the array size.
arraySize = obj.arraySize;
// Allocate memory for the array.
aptr = new T [arraySize];
if (aptr == 0)
memError();
// Copy the elements of obj's array.
for(int count = 0; count < arraySize; count++)
*(aptr + count) = *(obj.aptr + count);
}
//**************************************
// Destructor for SimpleVector class. *
//**************************************
template <typename T>
SimpleVector<T>::~SimpleVector()
{
if (arraySize > 0)
delete [] aptr;
}
//*******************************************************
// memError function. Displays an error message and *
// terminates the program when memory allocation fails. *
//*******************************************************
template <typename T>
void SimpleVector<T>::memError()
{
cout << "ERROR:Cannot allocate memory. ";
exit(EXIT_FAILURE);
}
//***********************************************************
// subError function. Displays an error message and *
// terminates the program when a subscript is out of range. *
//***********************************************************
template <typenameT>
void SimpleVector<T>::subError()
{
cout << "ERROR: Subscript out of range. ";
exit(EXIT_FAILURE);
}
//*******************************************************
// getElementAt function. The argument is a subscript. *
// This function returns the value stored at the sub- *
// cript in the array. *
//*******************************************************
template <typename T>
T SimpleVector<T>::getElementAt(int sub)
{
if (sub < 0 || sub >= arraySize)
subError();
return aptr[sub];
}
//*******************************************************
// Overloaded [] operator. The argument is a subscript. *
// This function returns a reference to the element *
// in the array indexed by the subscript. *
//*******************************************************
template <typename T>
T &SimpleVector<T>::operator[](const int &sub)
{
if (sub < 0 || sub >= arraySize)
subError();
return aptr[sub];
}
//***********************************************************
// The push_back function pushes its argument onto the back *
// of the vector. *
//***********************************************************
template <typename T>
void SimpleVector<T>::push_back(T val)
{
// Allocate a new array 1 element larger than the current one.
T *tempPtr = new T [arraySize + 1];
// Copy the current array contents to the new array
for(int count = 0; count < arraySize; count++)
*(tempPtr + count) = *(aptr + count);
// Copy the argument value to the end of the array
*(tempPtr + arraySize) = val;
// Get rid of the old array
if (arraySize > 0)
delete [] aptr;
// Make aptr point to the new array
aptr = tempPtr;
// Adjust arraySize
arraySize++;
}
//***********************************************************
// The pop_back function removes the last element *
// of the vector. It also returns that value. *
//***********************************************************
template <typename T>
T SimpleVector<T>::pop_back()
{
if (arraySize == 0)
throw "ERROR: vector contains no values. ";
else
{
// Save the last value in the array
T lastValue = aptr[arraySize - 1];
// Allocate a new array 1 element smaller than the current one.
T *tempPtr = new T [arraySize - 1];
// Copy the current array contents (except the last element)
// to the new array
for(int count = 0; count < (arraySize - 1); count++)
*(tempPtr + count) = *(aptr + count);
// Get rid of the old array
delete [] aptr;
// Make aptr point to the new array
aptr = tempPtr;
// Adjust arraySize
arraySize--;
return lastValue;
}
}
//************************************
//SortableVector
//
//************************************
template <typename T>
class SortableVector : public SimpleVector<T>
{
public:
SortableVector(int s) : SimpleVector<T>(s)// *************************5%
// Constructor
SortableVector(SortableVector &); // Copy constructor //**************20%
SortableVector(SimpleVector<T> &Obj): SimpleVector<T>(Obj) //****** 5%
void Sort();
};
template <typename T> // selection sort
void SortableVector<T>::Sort()
{
int startScan, minIndex;
T minValue;
for (startScan = 0; startScan < (this->size() - 1); startScan++)
{
minIndex = startScan;
minValue = this->operator[](startScan);
for(int Index = startScan + 1; Index < this->size(); Index++)
{
if (this->operator[](Index) < minValue)
{
minValue = this->operator[](Index);
minIndex = Index;
}
}
this->operator[](minIndex) = this->operator[](startScan);
this->operator[](startScan) = minValue;
}
}
//*********************************
//SearchableVector
//*********************************
template <typename T>
class SearchableVector : public SortableVector<T>
{
public:
SearchableVector(int s) : SortableVector<T>(s) // Constructor
//****************************************************************5%
SearchableVector(SearchableVector &); // Copy constructor//*************20%
SearchableVector(SimpleVector<T> &obj): SortableVector<T>(obj)
//****************************************************************5%
int findItem(T);
int sortAndSearch(T);
};
template <typename T>
int SearchableVector<T>::findItem(T item)
{
// find item within Array and return the index otherwise returns -1 //*********10%
}
template <typename T> // selection sort and binary search
int SearchableVector<T>::sortAndSearch(T item)
{
// find item after sorting array and return the index otherwise returns -1//********30%
}
using namespace std;
int main()
{
int SIZE = 5; // arbitrary array size of 5
SearchableVector<int> intTable(SIZE);
SearchableVector<string> doubleTable(SIZE);
int x, result1, result2;
doubleTable[0]="Have";
doubleTable[1]="A";
doubleTable[2]="Happy";
doubleTable[3]="And Safe";
doubleTable[4]="Holiday";
// Place values into the arrays in descending order
for (x = 0; x < SIZE ; x++)
{
intTable[x] = SIZE - x;
}
// Display the values in the arrays.
cout << " Before calling SortAndSearch(), these values are in intTable: ";
for (x = 0; x < SIZE; x++)
cout << intTable[x] << " ";
cout << endl;
cout << "Before calling SortAndSearch(),these values are in doubleTable: ";
for (x = 0; x < SIZE; x++)
cout << doubleTable[x] << " ";
cout << endl;
// call the function -- search for 5 and 3.0
result1 = intTable.sortAndSearch(5);
result2 = doubleTable.sortAndSearch("Happy");
// Display results of sort
cout << " After calling SortAndSearch(), these values are in intTable: ";
for (x = 0; x < SIZE; x++)
cout << intTable[x] << " ";
cout << endl;
cout << "After calling SortAndSearch(),these values are in doubleTable: ";
for (x = 0; x < SIZE; x++)
cout << doubleTable[x] << " ";
cout << endl;
// Display results of search
cout << " The value 5 was found in vector position " << result1 +1<< endl;
cout << " The value Happy was found in vector position " << result2 +1<< endl << endl;
return 0;
}
Explanation / Answer
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
T bin(T a[20],T n,T t)
{
int l,r,mid;
l=0;
r=n-1;
while(l<=r)
{
mid=(l+r)/2;
if(t==a[mid])
return mid;
else
if(t<a[mid])
r=mid-1;
else
l=mid+1;
}
return -1;
}
int main()
{
int a[20],n,t,p,i;
cout<<" Enter number of elements :";
cin>>n;
cout<<" As binary search algorithm works in sorted array!";
cout<<" Enter "<< n <<" values in ascending order : ";
for(i=0;i<n;i++)
cin>>a[i];
cout<<" Enter the element to find : ";
cin>>t;
p=bin(a,n,t);
if(p!=-1)
cout<<" The element is found at "<<p+1<<" position";
else
cout<<" Element Not Found!!";
system("pause");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.