Here is the requirement.
Your program will consist of 3 modules (files): main.cpp, Bucket.h, and BucketSort.h. Use the definitions that appear below. Your main should thoroughly test your code.
Once you have the general framework working, graduate students should also do the following. Add code to BucketSort.h to allocate, initialize, update, print, and free the mCounter array. This array of counts contains the number of buckets in each chain. Also complete the getCount andgetLoadFactor functions.
For extra credit, implement a more efficient version of the get function called get2. Clearly describe in the comment for get2 your approach and why and how it is better.
#pragma once
// file : Bucket.h
// author: ...
// desc. : this file contains the Bucket class definition.
using namespace std;
class Bucket {
public:
double mData = -1; //data value for bucket
Bucket* mNext = nullptr; //ptr to next bucket
//bucket dtor.
// note that this cascades destruction to the next element in the list.
// that way, the entire list is dtor's automagically.
~Bucket ( void ) {
cout << "in ~Bucket() dtor" << endl;
if (mNext != nullptr) {
delete mNext;
mNext = nullptr;
}
}
//-----------------------------------------------------------------------
//allow one to pretty print the contents of a bucket to an output stream.
// note that this cascades printing to the next element in the list.
// that way, the entire list is printed automagically.
friend ostream& operator<< ( ostream& os, const Bucket& b ) {
if (b.mNext != nullptr) os << " mData=" << b.mData << " mNext="
<< *b.mNext;
else os << " mData=" << b.mData << "
mNext=null";
return os;
}
};
#pragma once
// file : BucketSort.h
// author: ...
// desc. : this file contains the BucketSort class definition.
#include
#include
#include
#include "Bucket.h"
using namespace std;
class BucketSort {
private:
int mSize = 0; //# of buckets
Bucket** mBucketList = nullptr; //buckets = list (array) of pointers to
entries in a particular bucket
#ifdef GRAD
int* mCounter = nullptr; //number of buckets in each chain
#endif
public:
//bucket sort ctor. default size is 10.
BucketSort ( int size = 10 ) {
cout << "in BucketSort() ctor" << endl;
assert( size > 0 );
if (size < 1) return;
mSize = size;
//create the bucket list array of the appropriate size.
mBucketList = new Bucket*[ size ];
if (mBucketList == nullptr) return;
//each entry in the list (array) is a pointer to a bucket.
// init each to null.
for (int i = 0; i < size; i++)
mBucketList[ i ] = nullptr;
}
//-----------------------------------------------------------------------
//bucket sort dtor.
// note that this also cascades destruction to the bucket list elements
// as well.
~BucketSort ( void ) {
cout << "in ~BucketSort() dtor" << endl;
//if there is no list, there's nothing to do.
if (mBucketList == nullptr) return;
//delete each bucket in the bucket list.
for (int i = 0; i < mSize; i++) {
if (mBucketList[ i ] != nullptr) {
delete mBucketList[ i ];
mBucketList[ i ] = nullptr;
}
}
//finally, delete the bucket list itself
delete[] mBucketList;
mBucketList = nullptr;
}
//-----------------------------------------------------------------------
// \TODO this function should add a new element to the appropriate list
// _in the correct order_.
void add ( double value ) {
// \TODO
...
}
//-----------------------------------------------------------------------
// \TODO return the ith value in the list.
// if there is no such entry, then return NAN.
//
// NAN is Not-A-Number. one cannot do comparisons (or arithmetic) with
// NAN so only use isnan. for example, assuming that 12 does not exist,
// the first, third, and fifth will print for the following:
// if (isnan( bs->get( 12 ) )) cout << "NAN1" << endl;
// if (bs->get( 12 ) == NAN) cout << "NAN2" << endl;
// if (NAN == NAN) cout << "NAN3" << endl;
/*
if (isnan( bs->get( 12 ) )) cout << "NAN1" << endl;
if (bs->get( 12 ) == NAN) cout << "NAN2" << endl;
if (bs->get( 12 ) != NAN) cout << "NAN3" << endl;
if (NAN == NAN) cout << "NAN4" << endl;
if (NAN != NAN) cout << "NAN5" << endl;
*/
// vc++ supports NAN, but not all compilers do.
// see me if your compiler doesn't support NAN.
double get ( const int i ) {
// \TODO
...
return NAN;
}
//-----------------------------------------------------------------------
#if defined(GRAD) && defined(EXTRA_CREDIT)
// \TODO
double get2 ( const int i ) {
...
return NAN;
}
#endif
//-----------------------------------------------------------------------
#ifdef GRAD
//this function returns the number of buckets in a particular bucket
list.
int getCount ( int which ) {
// \TODO
...
}
#endif
//-----------------------------------------------------------------------
#ifdef GRAD
//this function calculates and returns the load factor (LF). the LF is
// the average chain length (# of data values added / total # of bucket
// lists).
double getLoadFactor ( void ) {
// \TODO
...
}
#endif
//-----------------------------------------------------------------------
//allow one to pretty print the contents of the bucket list to an output
stream.
friend ostream& operator<< ( ostream& os, const BucketSort& bs ) {
os << " mSize=" << bs.mSize;
os << " mBucketList=0x" << hex << (unsigned long) (bs.mBucketList)
<< dec << endl;
for (int i = 0; i < bs.mSize; i++) {
if (bs.mBucketList[ i ] == nullptr) os << " null";
else os << *bs.mBucketList[ i
];
os << endl;
}
return os;
}
};
// file : main.cpp
// author: ...
// desc. : this file contains the main program entry point.
#include
#include
#include "BucketSort.h"
using namespace std;
int main ( int argc, char* argv[] ) {
// \TODO "exercise your coder here. for example:
/*
BucketSort* bs = new BucketSort(); //dtor never called (must call
explicitly below)
cout << *bs << endl;
bs->add( 0.65 );
bs->add( 0.60 );
bs->add( 0.25 );
bs->add( 0.98 );
cout << *bs << endl;
cout << "search yields " << bs->get( 2 ) << endl;
delete bs;
bs = nullptr;
*/
return 0;
}