Sorted Arrays Buffers with and Without Duplicates This assignment assumes you have a mastered assignment 2.

In this assignment, we will create two variants of the classes from Assignment 2; SortedArrayBufferNoDups and SortedArrayBufferWithDups. As the name implies, the first class is a sorted array and does not allow the insertion of duplicate values, while the second one does. The SortedArrayBufferNoDups class should look like the ArrayBufferNoDups class in Assignment 2. Only the insert operation has to change. Insert has to insert in order. Here there is only one remove function which is stableRemove that has to be slightly altered so that you dont have to go until the end of the array to find the integer. You can stop when you have reached a value greater than the value being passed in. For example if your array contains integers [1,3,5,7,9] and you are asked to remove integer 4, you can stop once you reach 5 as you know 4 cannot be found now.

The ArrayBufferWithDups class should also look like the class in ArrayBufferWithDups class in Assignment 2. This time, change the insert function that allows duplicates but needed to be inserted in order, and implement one remove function which is stableRemove as for the NoDups case. Now modify the findAll and stableRemoveAll. The findAll function should return an int with the number of elements that have the same value as the target value, while the stableRemoveAll function should remove all copies of the target value. Have the stableRemoveAll function return an int with the number of values that were actually removed. Here stableRemoveAll becomes easier as you know the number of occurrences and now if you find the locationOf the first one you can stop looking and remove starting from that index to the number of occurrences. So for example if you have an integer array [1,3,5,5,5,7,9] and you are asked to remove 5, location of first 5 is 2 and number of occurrences for 5 is 3. So you need to remove from index 2 to 4(3 occurrences). For this assignment, like assignment 2 have the constructor take an integer argument for the size.

SortedArrayBufferWithDups.h:

#pragma once

#include

using namespace std;

class SortedArrayBufferWithDups

{

public:

SortedArrayBufferWithDups(int size);

bool insert(int value)

{

cout << "Testing insert to insert " << value << endl;

if (numberOfElements < BUFFER_SIZE) //compares numOfElements to BufferSize

{

intArray[numberOfElements++] = value; //adds value to end of array

cout << value << " is inserted" << endl;

return true;

}

else

cout << "Insertion failed" << endl;

return false;//if no room in array returns false

}

bool fastRemove(int value)

{

cout << "Testing fast remove to remove" << value << endl;

int index = locationOf(value);

if (index != -1)

{

intArray[index] = intArray[numberOfElements - 1];

numberOfElements--;

cout << "Removed " << value << endl;

return true;

}

else

cout << "Fast remove failed" << endl;

return false;

}

int fastRemoveAll(int value)

{

cout << "Testing fast remove all to remove all " << value << endl;

int index;

int count = 0;

do

{

index = locationOf(value);

if (index == -1) //element not found

{

cout << "Fast remove all failed" << endl;

return count;

}

else

{

count++;

intArray[index] = intArray[numberOfElements - 1];

numberOfElements--;

cout << "Removed all " << value << " " << count << " times " << endl;

}

} while (1);

}

bool find(int target)

{

cout << "Test find to find " << target << endl;

if (locationOf(target) != -1)

{

cout << "Found " << target << endl;

return true;

}

else

{

cout << target << " not found" << endl;

return false;

}

}

int findAll(int target) //finds the number of dups in the array of the target num

{

cout << "Testing find all to find all " << target << endl;

int count = 0; //counter of dups

for (int i = 0; i < numberOfElements; i++) // loops through array

{

if (intArray[i] == target)

{

count++; //if element = target num, add 1 to counter

cout << "Found " << target << " " << count << " times" << endl;

}

else

cout << target << " not found" << endl;

}

return count; //returns number of dups

}

void display()

{

cout << "Testing display " << endl;

for (int i = 0; i < numberOfElements; i++)//loop through array

{

if (i == numberOfElements - 1)

cout << intArray[i];

else

cout << intArray[i] << " , ";

}

cout << endl;

}

bool stableRemove(int value)

{

cout << "Testing stable remove to remove " << value << endl;

int index = locationOf(value);

if (index != -1)

{

for (int i = index; i < numberOfElements - 1; i++)

intArray[i] = intArray[i + 1];

numberOfElements--;

cout << "Stable removed " << value << endl;

return true;

}

else

{

cout << "Stable remove failed" << endl;

return false;

}

}

int stableRemoveAll(int value)

{

cout << "Testing stable remove all to remove " << value << endl;

int index;

int count = 0;

do

{

index = locationOf(value);

if (index == -1)

{

cout << "Stable remove all failed" << endl;

return count;

}

else

{

count++;

for (int i = index; i < numberOfElements - 1; i++)

intArray[i] = intArray[i + 1];

numberOfElements--;

cout << "Stable removed all " << value << " " << count << " times " << endl;

}

} while (1);

}

~SortedArrayBufferWithDups();

private:

int BUFFER_SIZE;//interger constant

int *intArray=new int[BUFFER_SIZE]; //array of ints that can hold the BUFFER_SIZE

int numberOfElements; //record of how many values are stored in the array

int locationOf(int target)

{

for (int i = 0; i < numberOfElements; i++)

if (intArray[i] == target)

return i;

return -1;

}

};

SortedArrayBufferWithDups.cpp:

#include "SortedArrayBufferWithDups.h"

SortedArrayBufferWithDups::SortedArrayBufferWithDups(int size)

{

BUFFER_SIZE = size;

numberOfElements = 0;

}

SortedArrayBufferWithDups::~SortedArrayBufferWithDups()

{

delete[] intArray;

}

SortedArrayBufferNoDups.h:

#pragma once

#include

using namespace std;

class SortedArrayBufferNoDups

{

public:

SortedArrayBufferNoDups(int size);

bool insert(int value) //insert in order function

{

cout << "Testing insert to insert " << value << endl;

int index = locationOf(value);

if (numberOfElements < BUFFER_SIZE && index == -1) //compares numOfElements to BufferSize and checks for dup in array

{

int i;

for (i = numberOfElements - 1; (i >= 0 && intArray[i] > value); i--)

{

intArray[i + 1] = intArray[i];

}

intArray[i + 1] = value;

numberOfElements++;

cout << value << " is inserted" << endl;

return true;

}

else

{

cout << "Insertion failed" << endl;

return false;//if no room in array returns false or if dup return false

}

}

/*bool fastRemove(int value)

{

cout << "Testing fast remove to remove" << value << endl;

int index = locationOf(value);

if (index != -1)

{

intArray[index] = intArray[numberOfElements - 1];

numberOfElements--;

cout << "Removed " << value << endl;

return true;

}

else

{

cout << "Fast remove failed" << endl;

return false;

}

}*/

bool find(int target)

{

cout << "Test find to find " << target << endl;

if (locationOf(target) != -1)

{

cout << "Found " << target << endl;

return true;

}

else

{

cout << target << " not found" << endl;

return false;

}

}

void display()

{

cout << "Testing display " << endl;

for (int i = 0; i < numberOfElements; i++)//loop through array

{

if (i == numberOfElements - 1)

cout << intArray[i];

else

cout << intArray[i] << " , ";

}

cout << endl;

}

bool stableRemove(int value) //needs to be edited

{

cout << "Testing stable remove to remove " << value << endl;

int index = locationOf(value);

if (index != -1)

{

for (int i = index; i < numberOfElements; i++)

if(value <= intArray[i + 1]) //if value is less than or equal to the next element

{

intArray[i] = intArray[i + 1];

}

numberOfElements--;

cout << "Stable removed " << value << endl;

return true;

}

else

{

cout << "Stable remove failed" << endl;

return false;

}

}

~SortedArrayBufferNoDups();

private:

int BUFFER_SIZE;//interger constant

int *intArray = new int[BUFFER_SIZE]; //array of ints that can hold the BUFFER_SIZE

int numberOfElements; //record of how many values are stored in the array

int locationOf(int target)

{

for (int i = 0; i < numberOfElements; i++)

if (intArray[i] == target)

return i;

return -1;

}

};

SortedArrayBufferNoDups.cpp:

#include "SortedArrayBufferNoDups.h"

SortedArrayBufferNoDups::SortedArrayBufferNoDups(int size)

{

BUFFER_SIZE = size;

numberOfElements = 0;

}

SortedArrayBufferNoDups::~SortedArrayBufferNoDups()

{

delete[] intArray;

}