Many of the functions implemented in the abstract base class arrayListType apply
ID: 3587557 • Letter: M
Question
Many of the functions implemented in the abstract base class arrayListType apply to all lists, whether ordered or unordered. However, the pure virtual fnctions in the abstract base class will be implemented differently depending on whether or not the list is ordered (sorted). Here is the class invariant for the orderedArrayList type with the differences highlighted:
Items must be stored in ascending order
The length private instance variable keeps track of the number of items currently in the list.
New items are added so that the ascending order between items is maintained.
No gaps are allowed between items.
It doesn't matter what values are stored in locations beyond length.
The number of items in the array cannot exceed the value stored in the maxSize private instance variable.
Notice that some of the pure virtual functions really only apply to an unordered list. The problem is that they must still be implemented in the orderedArrayList class. Write the definition of the functions of the orderedArrayListType that are not provided in the source files found in the Chapter 12/Source Code from Textbook/arrayList ADT folder for the orderedArrayListType. The insert function that stores an item in the proper location is provided. You must implement the other functions. Note that seqSearch can be modified to be more efficient because the list is ordered.
Turn in all your header and implementation files and your test program. Also turn in one or more screen shots showing the results of your testing.
After completing this assignment you will be able to:
Utilize the class invariant to simplify the processing of member functions.
Modify and build member functions that maintain the class invariant.
Modify and build functions that enforce the interface provided by an abstract base class.
Explanation / Answer
// contains 5 cpp files
// arrayListType.h
#ifndef H_arrayListType
#define H_arrayListType
#include <iostream>
/* virtual functions are implemented when you have two different objects
that need to access the same function, but with different meanings. This
is an abstract class, no objects can be created of this class.*/
class arrayListType
{
public:
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int,int) const;
virtual void insertAt(int,int) = 0;
virtual void insertEnd(int) = 0;
virtual void removeAt(int);
int retrieveAt(int) const;
virtual void replaceAt(int,int) = 0;
void clearList();
virtual int seqSearch(int) const = 0;
virtual void remove(int);
virtual void remove_All(int) = 0;
arrayListType(int size = 100);
arrayListType(const arrayListType& otherList);
virtual ~arrayListType();
protected:
int *list;
int length;
int maxSize;
};
#endif
// arrayListType.cpp
#include "arrayListType.h"
#include <bits/stdc++.h>
using namespace std;
bool arrayListType::isEmpty() const
{
return (length == 0);
}
bool arrayListType::isFull() const
{
return (length == maxSize);
}
int arrayListType::listSize() const
{
return length;
}
int arrayListType::maxListSize() const
{
return maxSize;
}
void arrayListType::print() const
{
for(int i = 0; i < length; i++)
cout<<list[i]<<" ";
cout<<endl;
}
bool arrayListType::isItemAtEqual(int location, int item) const
{
if(location < 0 || location >= length)
{
cout<<"The location is out of range."
<<"This is an error, you shouldn't be here!"<<endl;
return false;
}
else
return (list[location] == item);
}
void arrayListType::remove(int item)
{
int loc;
if(length == 0)
cout<<"The list is empty."<<endl;
else
{
loc = seqSearch(item);
if(loc != -1)
removeAt(loc);
else
cout<<"The item is not in the list."<<endl;
}
}
void arrayListType::removeAt(int location)
{
if(location < 0 || location >= length)
cout<<"The location is out of range."
<<"This is an error, you shouldn't be here!"<<endl;
else
{
for(int i = location; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
}
int arrayListType::retrieveAt(int location) const
{
assert(location < length);
/*
if(location < 0 || location >= length)
cout<<"The location is out of range."
<<"This is an error, you shouldn't be here!"<<endl;*/
return list[location];
}
void arrayListType::clearList()
{
length = 0;
}
arrayListType::arrayListType(int size)
{
if(size <= 0)
{
cout<<"The array size must be positive. Creating "
<<"an array with default size of 100."<<endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new int[maxSize];
}
arrayListType::~arrayListType()
{
delete [] list;
}
arrayListType::arrayListType(const arrayListType &otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new int[maxSize];
for(int j = 0; j < length; j++)
list[j] = otherList.list[j];
}
/// unorderedListType.h
#ifndef H_unorderedListType
#define H_unorderedListType
#include <iostream>
#include "arrayListType.h"
class unorderedListType: public arrayListType
{
public:
void insertAt(int,int);
void insertEnd(int);
void replaceAt(int,int);
int seqSearch(int) const;
void remove(int);
void removeAt(int);
void remove_All(int);
unorderedListType(int size = 100);
};
#endif
// unorderedListType.cpp
#include <iostream>
#include "unorderedListType.h"
#include <bits/stdc++.h>
using namespace std;
void unorderedListType::insertAt(int location, int item)
{
if(location < 0 || location >= maxSize)
cout<<"The index is out of range."<<endl;
else if(length >= maxSize)
cout<<"The list is full."<<endl;
else
{
for(int i = length; i > location; i--)
list[i] = list[i - 1];
list[location] = item;
length++;
}
}
void unorderedListType::insertEnd(int item)
{
if(length >= maxSize)
cout<<"The list is full."<<endl;
else
{
list[length] = item;
length++;
}
}
int unorderedListType::seqSearch(int item) const
{
int loc = 0;
bool found = false;
for(loc = 0; loc < length; loc++)
if(list[loc] == item)
{
found = true;
break;
}
if(found)
return loc;
else
return -1;
}
void unorderedListType::removeAt(int location)
{
if(location < 0 || location >= length)
cout<<"The location is out of range."
<<"This is an error, you shouldn't be here!"<<endl;
else
{
list[location] = list[length-1];
length--;
}
}
void unorderedListType::remove(int item)
{
int loc;
if(length == 0)
cout<<"The list is empty."<<endl;
else
{
loc = seqSearch(item);
if(loc != -1)
removeAt(loc);
else
cout<<"The item is not in the list."<<endl;
}
}
void unorderedListType::remove_All(int item)
{
int loc;
if(length == 0)
cout<<"The list is empty."<<endl;
else
{
loc = seqSearch(item);
while(loc != -1)
{
removeAt(loc);
if(length == 0)
cout<<"The list has become empty empty."<<endl;
loc = seqSearch(item);
}
}
}
void unorderedListType::replaceAt(int location, int item)
{
if(location < 0 || location >= length)
cout<<"The location is out of range."<<endl;
else
list[location] = item;
}
unorderedListType::unorderedListType(int size):arrayListType(size)
{
}
// main.cpp
#include <iostream>
#include "unorderedListType.h"
#include <bits/stdc++.h>
using namespace std;
int main()
{
int xxx;
unorderedListType myList(25);
int num;
cout<<"Enter 8 integers: ";
for(int i = 0; i < 8; i++)
{
cin>>num;
myList.insertEnd(num);
}
cout<<" myList values :"<<endl;
myList.print();
unorderedListType yourList(myList); // test copy constructor
cout<<" yourList values: "<<endl;
yourList.print();
cout<<" Enter a number to be deleted: ";
cin>>num;
myList.remove(num);
cout<<" After removing "<<num<<" myList: ";
myList.print();
cout<<" Enter a number to be found: ";
cin>>num;
cout<<endl;
if(myList.seqSearch(num) != -1)
cout<<num<<" found in myList."<<endl;
else
cout<<num<<" is not in myList."<<endl;
cout<<" Enter a number to remove all its instances: ";
cin>>num;
myList.remove_All(num);
myList.print();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.