Book: Data Structures and Algorithm Analysis in C++ Chapter: 1 Exercise: 1.14 De
ID: 3648638 • Letter: B
Question
Book: Data Structures and Algorithm Analysis in C++Chapter: 1
Exercise: 1.14
Design a class template, OrderedCollection, that stores a collection of Comparables (in an array), along with the current size of the collection. Provide public functions isEmpty, makeEmpty, insert, remove, findMin, and findMax. findMin and findMax return references to the smallest and largest, respectively, Comparable in the collection. Explain what can be done if these operations are performed on an empty collection.
Explanation / Answer
Given below is the code for OrderedCollection.
To handle cases where the list is empty and the functions like findMin() findMax() or remove() are called, we can use either an assert() to make sure the list is not emtpy or we can throw exception when the list is empty.
Please rate the answer if it helped. Thank you.
#include <iostream>
using namespace std;
template <typename T>
class OrderedCollection
{
private:
T *elements;
int capacity;
int size;
void shiftLeft(int idx)
{
for(int i = idx; i < size - 1; i++)
elements[i] = elements[i+1];
}
void shiftRight(int idx)
{
for(int i = size; i > idx; i--)
elements[i] = elements[i-1];
}
public:
OrderedCollection(int capacity = 10) //default capacity of 10
{
this->capacity = capacity;
elements = new T[capacity];
size = 0;
}
bool isEmpty()
{
return size == 0;
}
void makeEmpty()
{
delete []elements;
elements = new T[capacity];
size = 0;
}
bool isFull()
{
return size == capacity;
}
bool insert(T val)
{
if(isFull())
return false;
int i;
for(i = 0; i < size; i++)
{
if(val < elements[i])
break;
}
shiftRight(i);
elements[i] = val;
size++;
return true;
}
bool remove(T val)
{
if(isEmpty())
return false;
int i;
for(i = 0; i < size; i++)
{
if(elements[i] == val)
break;
}
if(i < size)
{
shiftLeft(i);
size--;
return true;
}
else
return false;
}
T& findMin()
{
int minIdx = 0;
for(int i = 1; i < size; i++)
if(elements[i] < elements[minIdx])
minIdx = i;
return elements[minIdx];
}
T& findMax()
{
int maxIdx = 0;
for(int i = 1; i < size; i++)
if(elements[i] > elements[maxIdx])
maxIdx = i;
return elements[maxIdx];
}
void display(string separator)
{
for(int i = 0; i < size; i++)
{
cout << elements[i] << separator;
}
cout << endl;
}
~OrderedCollection()
{
delete []elements;
}
};
int main()
{
OrderedCollection<int> numbers;
numbers.insert(2);
numbers.insert(1);
numbers.insert(5);
numbers.insert(3);
numbers.insert(6);
cout << "Inserted numbers 2 1 5 3 6 . The list contains : " ;
numbers.display(" ");
cout << "Min: " << numbers.findMin() << endl;
cout << "Max: " << numbers.findMax() << endl;
cout << "Removing 1 3 6" << endl;
numbers.remove(1);
numbers.remove(3);
numbers.remove(6);
cout << "The list contains: " ;
numbers.display(" ");
cout << "Min: " << numbers.findMin() << endl;
cout << "Max: " << numbers.findMax() << endl;
cout << boolalpha << "Is numbers list empty ? " << numbers.isEmpty() << endl;
cout << "Making the numbers list empty...." << endl;
numbers.makeEmpty();
cout << "Is numbers list empty ? " << numbers.isEmpty() << endl;
}
output
Inserted numbers 2 1 5 3 6 .
The list contains : 1 2 3 5 6
Min: 1
Max: 6
Removing 1 3 6
The list contains: 2 5
Min: 2
Max: 5
Is numbers list empty ? false
Making the numbers list empty....
Is numbers list empty ? true