The array in arrayListType is being used as a partially filled array which means

Question

The array in arrayListType is being used as a partially filled array which means that items are stored from the beginning to the end of the array with no gaps in between them. This restriction becomes part of the class invariant for the arrayListType and unorderedArrayListType classes as follows:

Items can be stored in the array in any order.

The length private instance variable keeps track of the number of items currently in the list.

New items are added at the location represented by length.

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.

Also note that the instance variables in the arrayList class are specified with the access type protected, meaning that they can be used without going through the public access functions by classes derived from this class. The public accessor functions must still be used by entities outside of the class and its derived classes.

Take the files for the arrayListType and unorderedArrayListType classes that are in the Chapter 12/Source Code From Textbook/arrayList ADT folder on the Blackboard, create a project and make the following modifications:

The function retrieveAt of the class arrayListType is written as a void function. Rewrite this function so that it is written as a value returning function, returning the required item. If location of the item to be returned is out of range, use the assert function (part of the <cassert> library) to terminate the program. Use the class unorderedArrayListType to test your function.

The function removeAt of the class arrayListType removes an element from the list by shifting the elements of the list. However, if the element to be removed is at the beginning of the list and the list is fairly large it could take a lot of computer time. Because the list elements are in no particular order, you could simply remove the element by swapping the last element of the list with the item to be removed and reducing the length of the list. Rewrite the definition of the function removeAt using this technique. Use the class unorderedArrayListType to test your function.

The function remove of the class arrayListType removes only the first occurrence of an element. Add the function removeAll as a pure virtual function in the class arrayListType, which would remove all occurrences of a given element. Also, write the definition of the function removeAll in the class unorderedArrayListType.

Write one or more programs to test your modifications. Turn in all your header files, all your implementation files, and all your test programs. Also turn in one or more screen shots showing the results of your testing.

Upon completion of this project you will demonstrate that you can:

Define the term partially filled array and explain how it is used to maintain the class invariant.

Utilize the class invariant to simplify the processing of member functions.

Modify and build member functions that maintain the class invariant.

Apply the assert function to terminate processing from inside a class.

Add a pure virtual function to an abstract class

Construct a pure virtual function in a derived class.

Design a program that utilizes a class derived from an abstract base class.

Utilize protected variables in a derived class.

Explanation / Answer

// 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

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.