C++ HAVING PROBLEM WITH "LIST". Need to find the problem. ONLY ONE PROBLEM WITH CODE. LINES 334, 346, 363 all have the same issue with list.....

#include #include #include #include #include #include #include #include

//To prevent those using g++ from trying to use a library //they don't have #ifndef __GNUC__ #include #else #include #endif

using std::cout; using std::endl; using std::vector; using std::unique_ptr; using std::string;

//*** Prototypes *** void recQuickSort(vector& arr, int first, int last); void pressAnyKeyToContinue(); class ManyBuckets;

//***GLOBAL VARIABLES*** unsigned long *list; int listSize; int numBuckets; int numThreads; ManyBuckets *globalBuckets; //Global buckets object

const unsigned long ULONGMAX = 4294967295;

class ManyBuckets { public: ManyBuckets(int bucketCapacity, int numBuckets); ~ManyBuckets() {} ~ManyBuckets(); void addItem(int bucket, unsigned long item); int getNumBuckets(); int getNumItemsInABucket(int bucket); unsigned long * getBucket(int bucket); //vector& getBucket(const unsigned int bucket); void copyManyBucketsToManyBuckets(int bucket, unsigned long * destinationArray, int destinationArrayOffsetIndex); //Used for Multithread void appendSmallBucketIntoBiggerBucket(int bucketNumber, ManyBuckets& smallBucket); //Used for Multithread void printAllBuckets() const;

private: vector< vector > arr; unsigned int buckets;

unsigned long **buckets; int *itemCounter; int bucketSize; int numBuckets; };

//*** Provide methods for the bucket class *** ManyBuckets::ManyBuckets(int bucketCapacity, int numBuckets) { //Each bucket should be as bg as roughly the size of the list divided by number of buckets. //But some buckets will be bigger than others, so give an extra room. this->numBuckets = numBuckets; //Worst case scenario is that every value falls into one bucket. Assume the worst case could //happen and make sure each bucket could handle that much data.

buckets = new unsigned long*[numBuckets]; for (int i = 0; i < numBuckets; i++) { //printf("Requsting %d items for this bucket ", listSize); buckets[i] = new unsigned long[bucketCapacity]; }

itemCounter = new int[numBuckets]; for (int i = 0; i < numBuckets; i++) { itemCounter[i] = 0; }

}

ManyBuckets::~ManyBuckets() {

for (int i = 0; i < numBuckets; i++) { delete[] buckets[i]; } delete[] buckets; delete[] itemCounter;

}

void ManyBuckets::addItem(int bucket, unsigned long item) { //Pass in a bucket #, and the data, and it assigns that data to the bucket.

buckets[bucket][itemCounter[bucket]] = item; itemCounter[bucket]++; }

int ManyBuckets::getNumBuckets() { return numBuckets; }

int ManyBuckets::getNumItemsInABucket(int bucket) {

return itemCounter[bucket]; }

void ManyBuckets::printAllBuckets() const { //Displays the contents of all buckets to the screen.

// just uncomment this code when you have arr properly declared as a data member printf("****** "); for (int i = 0; i < numBuckets; i++) { printf("bucket number %d ", i); for (unsigned int j = 0; j < arr[i].size(); j++) { printf("%08x ", arr[i][j]);

} printf(" "); } printf(" "); }

/*vector& ManyBuckets::getBucket(const unsigned int bucket) { return arr[bucket];

//ARR == BUCKETS }*/

unsigned long * ManyBuckets::getBucket(int bucket) { //You pass in the bucket #, it returns the array that contains the bucket's data.

return buckets[bucket]; }

void ManyBuckets::copyManyBucketsToManyBuckets(int bucket, unsigned long * destinationArray, int destinationArrayOffsetIndex) { //Copies all items in all buckets from one ManyBuckets object into another ManyBuckets object. //Not for the first part of the homework assignment, only the multithreaded part.

for (int j = 0; j < itemCounter[bucket]; j++) { destinationArray[destinationArrayOffsetIndex + j] = buckets[bucket][j]; } }

void ManyBuckets::appendSmallBucketIntoBiggerBucket(int bucket, ManyBuckets& smallBucket) {

unsigned long * smallBucketArray = smallBucket.getBucket(bucket); for (int i = 0; i < smallBucket.getNumItemsInABucket(bucket); i++) { addItem(bucket, smallBucketArray[i]); }

}

//***Functions that help our bucket sort work.*** void printList() { for (int i = 0; i < listSize; i++) { //cout << list[i] << " "; printf("%08x ", list[i]); } }

void createList() { // list = std::make_unique(listSize); list = new unsigned long[listSize]; std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(0, ULONGMAX);

for (int i = 0; i < listSize; i++) { list[i] = dis(gen); } } void placeIntoBuckets() {

//TODO: Put the values into the appropriate buckets. //globalBuckets->

}

void sortEachBucket() {

//TODO: Sort each individual bucket //vector &myBucket = blahblablah->getBucket(blah blah blah);

}

void combineBuckets() { //TODO: Copy each bucket back out to the original list[] array

//Loop for the amount of buckets //Get the individual bucket out of the globalBuckets //Copy all items from that individual bucket into the list array.

}

void bucketSort(bool displayOutput) {

//For the upcoming homeowork assignment, I think it will help you the most to split your work into these three functions. placeIntoBuckets();

if (displayOutput) { printf("Displaying each bucket's contents before sorting: "); globalBuckets->printAllBuckets(); }

sortEachBucket();

combineBuckets();

if (displayOutput) { printf("Displaying each bucket's contents after sorting: "); globalBuckets->printAllBuckets(); pressAnyKeyToContinue(); printf("Displaying what is hopefully a sorted array: "); printList(); //See if it's all sorted. } }

int partition(vector& arr, int first, int last) { unsigned long pivot; int index, smallIndex;

unsigned long temp;

//Take the middle value as the pivot. //swap(first, (first + last) / 2); pivot = arr[first]; smallIndex = first; for (index = first + 1; index < last; index++) { if (arr[index] < pivot) { smallIndex++; //swap the two temp = arr[smallIndex]; arr[smallIndex] = arr[index]; arr[index] = temp; } }

//Move pivot into the sorted location temp = arr[first]; arr[first] = arr[smallIndex]; arr[smallIndex] = temp;

//Tell where the pivot is return smallIndex;

}

void recQuickSort(vector& arr, int first, int last) { //first is the first index //last is the one past the last index (or the size of the array //if first is 0)

if (first < last) { //Get this sublist into two other sublists, one smaller and one bigger int pivotLocation = partition(arr, first, last); recQuickSort(arr, first, pivotLocation); recQuickSort(arr, pivotLocation + 1, last); } }

void verifySort(unique_ptr& arr, unsigned int arraySize, std::chrono::duration& diff, const string& sortTest) { double val = diff.count(); for (unsigned int i = 1; i < arraySize; i++) { if (arr[i] < arr[i - 1]) { printf(" "); printf("------------------------------------------------------ "); printf("SORT TEST %s ", sortTest.c_str());

if (val != 0.0) { printf("Finished bucket sort in %1.16lf milliseconds ", diff.count()); } printf("ERROR - This list was not sorted correctly. At index %d is value %08X. At index %d is value %08X ", sortTest.c_str(), i - 1, arr[i - 1], i, arr[i]); printf("------------------------------------------------------ ");

return; } } printf(" "); printf("------------------------------------------------------ "); printf("SORT TEST %s ", sortTest.c_str()); if (val != 0.0) { printf("Finished bucket sort in %1.16lf milliseconds ", diff.count()); } printf("PASSED SORT TEST - The list was sorted correctly ", sortTest.c_str()); printf("------------------------------------------------------ "); }

void pressAnyKeyToContinue() { printf("Press any key to continue ");

//Linux and Mac users with g++ don't need this //But everyone else will see this message. #ifndef __GNUC__ _getch(); #else int c; fflush(stdout); do c = getchar(); while ((c != ' ') && (c != EOF)); #endif

}

int main() {

std::chrono::duration diff{ 0 };

//Set the listSize, numBuckets, and numThreads global variables. listSize = 100;

numBuckets = 2; numThreads = 2; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); printf(" Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); // printf("Displaying the unsorted list array: "); // printList(); //useful for debugging small amounts of numbers. pressAnyKeyToContinue(); bucketSort(true); verifySort(list, listSize, diff, "2 buckets"); pressAnyKeyToContinue();

numBuckets = 4; numThreads = 4; createList(); printf(" Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); pressAnyKeyToContinue(); bucketSort(true); verifySort(list, listSize, diff, "4 buckets"); pressAnyKeyToContinue();

printf(" If you manually placed any printf statements, remove them from here on out "); pressAnyKeyToContinue();

listSize = 4000000; numBuckets = 1; numThreads = 1; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets);

//globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d, this is effectively a quick sort ", listSize, numBuckets, numThreads); auto start = std::chrono::high_resolution_clock::now(); bucketSort(false); auto end = std::chrono::high_resolution_clock::now(); verifySort(list, listSize, diff, "4000000 items in 1 bucket - BASELINE");

listSize = 4000000; numBuckets = 2; numThreads = 2; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); // printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 2 buckets");

numBuckets = 4; numThreads = 4; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 4 buckets");

numBuckets = 8; numThreads = 8; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 8 buckets");

numBuckets = 16; numThreads = 16; createList(); globalBuckets = new ManyBuckets(listSize, numBuckets); //globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 16 buckets");

pressAnyKeyToContinue(); return 0; }