// CMSC 341 - Fall 2024 - Project 3 #include "mqueue.h" //Constructor…
- User
// CMSC 341 - Fall 2024 - Project 3 #include "mqueue.h"
//Constructor MQueue::MQueue(prifn_t priFn, HEAPTYPE heapType, STRUCTURE structure) { //skew-heap or leftist-heap based on input m_heapType = heapType; //min-heap or max-heap based on input m_structure = structure; //priority m_priorFunc = priFn; //no heap or heap elements exist yet m_heap = nullptr; m_size = 0; }
//Destructor MQueue::~MQueue() { clear(); }
void MQueue::clear() { if(m_heap != nullptr) { clearHelper(m_heap); m_heap = nullptr; m_size = 0; } }
//Copy Constructor MQueue::MQueue(const MQueue& rhs) { //skew or leftist heap m_heapType = rhs.m_heapType; //min or max heap m_structure = rhs.m_structure; //priority m_priorFunc = rhs.m_priorFunc; //copy size m_size = rhs.m_size;
//check if rhs is empty first if(rhs.m_heap == nullptr) { m_heap = nullptr; } else { //deep copy of rhs m_heap = copy(rhs.m_heap); }
} //Creates an exact copy of rhs MQueue& MQueue::operator=(const MQueue& rhs) { //Self assignment check & clearing currrent heap data if(this != &rhs) { clear();
m_size = rhs.m_size; m_priorFunc = rhs.m_priorFunc; m_heapType = rhs.m_heapType; m_structure = rhs.m_structure;
//deep copy the heap nodes m_heap = copy(rhs.m_heap); } return *this; }
void MQueue::mergeWithQueue(MQueue& rhs) { //checking if they are same queue //no self merging if(this == &rhs) { throw domain_error("No self merging!"); }
//compataiblity check if(m_priorFunc != rhs.m_priorFunc) { throw domain_error("Incompataible priority!"); } if(m_structure != rhs.m_structure) { throw domain_error("Incompataible structures!"); } //Merge depending on leftist or skew if(m_structure == LEFTIST){ m_heap = mergeLeft(m_heap, rhs.m_heap); } else { m_heap = mergeSkew(m_heap,rhs.m_heap); } //resetting rhs to empty state rhs.m_heap = nullptr; //updating size after merging m_size += rhs.m_size; rhs.m_size = 0;} bool MQueue::insertOrder(const Order& order) { //get priority using priority function given int prio = m_priorFunc(order);
//check if it's a valid order zero it's not valid //we dont insert. if(prio == 0) { return false; } //new node for the order Node* newNode = new Node(order); //Insert node depending on the heap/structure if(m_structure == LEFTIST) { //Initial NPL Value // newNode->setNPL(0); m_heap = mergeLeft(m_heap, newNode); } else if (m_structure == SKEW){ m_heap = mergeSkew(m_heap, newNode); } //Inc size of queue when inserting. m_size++; return true;} int MQueue::numOrders() const { return m_size; } prifn_t MQueue::getPriorityFn() const { return m_priorFunc; } Order MQueue::getNextOrder() { //heap is empty if (m_heap == nullptr){ throw out_of_range("Queue is empty!"); } //Holding highest prio order to return Order highestPrioOrder = m_heap->m_order;
//merge left & right sub-heaps to form a new root Node* oldRoot = m_heap; if ((m_heapType == MINHEAP || m_heapType == MAXHEAP) && m_structure == LEFTIST){ m_heap = mergeLeft(m_heap->m_left, m_heap->m_right); } else { m_heap = mergeSkew(m_heap->m_left,m_heap->m_right); } //Free memory of the old root. //Also updating the size since we're remmoving delete oldRoot; m_size--; return highestPrioOrder;} void MQueue::setPriorityFn(prifn_t priFn, HEAPTYPE heapType) {
//base case we dont make changes nothing to change if(m_priorFunc == priFn && m_heapType == heapType) { return; }int size = m_size; int i = 0; //extract nodes inmto array Node** nodes = new Node*[size]; extract(m_heap,nodes,i);
//clear(); //set the new prio func and heap m_priorFunc = priFn; m_heapType = heapType;
//new heap root Node* nHeap = nullptr;
//rebuild heap based on typ for(int j = 0; j < size; j++) { if(m_structure == LEFTIST) { nHeap = mergeLeft(nHeap, nodes[j]); } else { nHeap = mergeSkew(nHeap, nodes[j]); } } // assign new heap root to be our new root m_heap = nHeap; m_size = size; delete[] nodes; }
HEAPTYPE MQueue::getHeapType() const { return m_heapType; }
void MQueue::setStructure(STRUCTURE structure) { //check current structure if(m_structure == structure) { //dont need to do anything since already same return; } //need size since it will be cleared later int size = m_size; int i = 0; //allocate array of node pointers Node** nodes = new Node*[size]; //extract the nodes into our array extract(m_heap,nodes,i); //after extracting we clear our heap to ensure to remnants/frags clear();
//set new structure m_structure = structure; //best to start with an empty heap Node* nHeap = nullptr; //rebuild our structure for(int i =0; i < size; i++) { if(structure == LEFTIST) { nHeap = mergeLeft(nHeap,nodes[i]); } else { nHeap = mergeSkew(nHeap, nodes[i]); } } // free memory m_heap = nHeap; delete[] nodes;} STRUCTURE MQueue::getStructure() const { return m_structure; } void MQueue::printOrderQueue() const { cout <<"Contents of the queue: " << endl; preOrder(m_heap); } void MQueue::dump() const { if (m_size == 0) { cout << "Empty heap.\n" ; } else { dump(m_heap); } cout << endl; } void MQueue::dump(Node *pos) const { if ( pos != nullptr ) { cout << "("; dump(pos->m_left); if (m_structure == SKEW) cout << m_priorFunc(pos->m_order) << ":" << pos->m_order.m_customer; else cout << m_priorFunc(pos->m_order) << ":" << pos->m_order.m_customer << ":" << pos->m_npl; dump(pos->m_right); cout << ")"; } }
ostream& operator<<(ostream& sout, const Order& order) { sout << "Customer: " << order.getCustomer() << ", importance: " << order.getImportance() << ", quantity: " << order.getQuantity() << ", order placement time: " << order.getFIFO(); return sout; } ostream& operator<<(ostream& sout, const Node& node) { sout << node.m_order; return sout; }
Node *MQueue::copy(Node node) { //Base case if (node == nullptr){ return nullptr; } //New node with same data as our current node Node newNode = new Node(node->m_order);
//copy left and right children newNode->m_left = copy(node->m_left); newNode->m_right = copy(node-> m_right); //only do this if it's a leftist heap if(m_structure == LEFTIST){ newNode->m_npl = node->m_npl; } //return root of the copied tree return newNode;}
Node* MQueue::mergeLeft(Node* p1, Node* p2) { if (p1 == nullptr) return p2; if (p2 == nullptr) return p1;
// Ensure p1 has the higher priority if (comparePrio(p1->getOrder(), p2->getOrder()) < 0) { mySwap(p1, p2); } // Merge p2 into the right subtree of p1 p1->m_right = mergeLeft(p1->m_right, p2); // Get NPLs of children; NPL of null nodes is 0 int leftNPL = (p1->m_left) ? p1->m_left->getNPL() : -1; int rightNPL = (p1->m_right) ? p1->m_right->getNPL() : -1; // Swap children if necessary to maintain leftist property if (leftNPL < rightNPL) { mySwap(p1->m_left, p1->m_right); // Update NPLs after swap leftNPL = (p1->m_left) ? p1->m_left->getNPL() : -1; rightNPL = (p1->m_right) ? p1->m_right->getNPL() : -1; } // Update NPL of current node: NPL = min(NPL of children) + 1 p1->m_npl = myMin(leftNPL, rightNPL) + 1; return p1;}
Node *MQueue::mergeSkew(Node *p1, Node *p2) { //Base case either heap is null return other if(p1 == nullptr) { return p2; } if(p2 == nullptr) { return p1; }
//Making sure p1 has higher priority if(comparePrio(p1->getOrder(), p2->getOrder()) < 0) { mySwap(p1, p2); }
//Merge p2 with right chiild of p1 p1->m_right = mergeSkew(p1->m_right,p2); //swap left and right child to maintain skew properites mySwap(p1->m_left,p1->m_right);
return p1; }
int MQueue::comparePrio(const Order &order1, const Order &order2) const { int prio1 = m_priorFunc(order1); int prio2 = m_priorFunc(order2);
if(m_heapType == MAXHEAP) { if(prio1 > prio2){ return 1;} if(prio1 < prio2){ return -1;} return 0; } else { // MINHEAP if(prio1 < prio2){ return 1;} if(prio1 > prio2){return -1;} return 0; }} void MQueue::clearHelper(Node *Node) { //Base case if(Node == nullptr) { return; }
//we delete nodes left and right recursively clearHelper(Node->m_left); clearHelper(Node->m_right); delete Node; }
void MQueue::extract(Node *node, Node **array, int &i) { if (node == nullptr) { return; } // Recursively extract the left and right subtrees extract(node->m_left, array, i); extract(node->m_right, array, i);
// Store the current node in the array at index i // Then incremenent after storing array[i] = node; //cout << "Extracted Node with Priority: " << m_priorFunc(node->getOrder()) << " for index: " << i << endl; i++; //reset node to null node->m_left = nullptr; node->m_right = nullptr;}
void MQueue::preOrder(Node *node) const { //base case //no more nodes to traverse if(node == nullptr) {return;}
cout << "[" << m_priorFunc(node->getOrder()) << "]" << "Customer: " << node->getOrder().getCustomer() << ", importance: " << node->getOrder().getImportance() << ", quantity: " << node->getOrder().getQuantity() <<", order placement time: " << node->getOrder().getProcessTime() << endl;//traverse left & right subtrees preOrder(node->m_left); preOrder(node->m_right); } void MQueue::mySwap(Node *&a, Node &b) { Node temp = a; a = b; b = temp; }
int MQueue::myMin(int a, int b) { return (a < b) ? a : b; }
#include #include "mqueue.h" #include <math.h> #include #include #include using namespace std;
enum RANDOM {UNIFORMINT, UNIFORMREAL, NORMAL, SHUFFLE};
int priorityMaxHeap(const Order & order); //MAXHEAP int priorityMinHeap(const Order & order); //MINHEAP
class Random { public: Random(){} Random(int min, int max, RANDOM type=UNIFORMINT, int mean=50, int stdev=20) : m_min(min), m_max(max), m_type(type) { if (type == NORMAL){ //the case of NORMAL to generate integer numbers with normal distribution m_generator = std::mt19937(m_device()); //the data set will have the mean of 50 (default) and standard deviation of 20 (default) //the mean and standard deviation can change by passing new values to constructor m_normdist = std::normal_distribution<>(mean,stdev); } else if (type == UNIFORMINT) { //the case of UNIFORMINT to generate integer numbers // Using a fixed seed value generates always the same sequence // of pseudorandom numbers, e.g. reproducing scientific experiments // here it helps us with testing since the same sequence repeats m_generator = std::mt19937(10);// 10 is the fixed seed value m_unidist = std::uniform_int_distribution<>(min,max); } else if (type == UNIFORMREAL) { //the case of UNIFORMREAL to generate real numbers m_generator = std::mt19937(10);// 10 is the fixed seed value m_uniReal = std::uniform_real_distribution((double)min,(double)max); } else { //the case of SHUFFLE to generate every number only once m_generator = std::mt19937(m_device()); } } void setSeed(int seedNum){ // we have set a default value for seed in constructor // we can change the seed by calling this function after constructor call // this gives us more randomness m_generator = std::mt19937(seedNum); } void init(int min, int max){ m_min = min; m_max = max; m_type = UNIFORMINT; m_generator = std::mt19937(10);// 10 is the fixed seed value m_unidist = std::uniform_int_distribution<>(min,max); } void getShuffle(vector & array){ // this function provides a list of all values between min and max // in a random order, this function guarantees the uniqueness // of every value in the list // the user program creates the vector param and passes here // here we populate the vector using m_min and m_max for (int i = m_min; i<=m_max; i++){ array.push_back(i); } shuffle(array.begin(),array.end(),m_generator); }
void getShuffle(int array[]){ // this function provides a list of all values between min and max // in a random order, this function guarantees the uniqueness // of every value in the list // the param array must be of the size (m_max-m_min+1) // the user program creates the array and pass it here vector<int> temp; for (int i = m_min; i<=m_max; i++){ temp.push_back(i); } std::shuffle(temp.begin(), temp.end(), m_generator); vector<int>::iterator it; int i = 0; for (it=temp.begin(); it != temp.end(); it++){ array[i] = *it; i++; } } int getRandNum(){ // this function returns integer numbers // the object must have been initialized to generate integers int result = 0; if(m_type == NORMAL){ //returns a random number in a set with normal distribution //we limit random numbers by the min and max values result = m_min - 1; while(result < m_min || result > m_max) result = m_normdist(m_generator); } else if (m_type == UNIFORMINT){ //this will generate a random number between min and max values result = m_unidist(m_generator); } return result; } double getRealRandNum(){ // this function returns real numbers // the object must have been initialized to generate real numbers double result = m_uniReal(m_generator); // a trick to return numbers only with two deciaml points // for example if result is 15.0378, function returns 15.03 // to round up we can use ceil function instead of floor result = std::floor(result*100.0)/100.0; return result; } string getRandString(int size){ // the parameter size specifies the length of string we ask for // to use ASCII char the number range in constructor must be set to 97 - 122 // and the Random type must be UNIFORMINT (it is default in constructor) string output = ""; for (int i=0;i<size;i++){ output = output + (char)getRandNum(); } return output; } int getMin(){return m_min;} int getMax(){return m_max;} private: int m_min; int m_max; RANDOM m_type; std::random_device m_device; std::mt19937 m_generator; std::normal_distribution<> m_normdist;//normal distribution std::uniform_int_distribution<> m_unidist;//integer uniform distribution std::uniform_real_distribution<double> m_uniReal;//real uniform distribution};
class Tester { private: bool heapProperties(Node node, HEAPTYPE heapType, STRUCTURE structure, prifn_t priFn); bool checkNPLValues(Node node); bool checkLeftistProperty(Node* node); void genRandomOrder(MQueue &queue); void extractTester(Node *node, vector<Node *> &vector); const int Orders = 10; const int removeOrders = 5;
public: //need to create test cases for skewheap bool testInsertionLeftistMinHeap(); bool testInsertionLeftistMaxHeap(); bool testRemovalLeftistMinHeap(); bool testRemovalLeftistMaxHeap(); bool testInsertionEdgeCase(); bool testInsertionSkewMinHeap(); bool testInsertionSkewMaxHeap(); bool testRemovalSkewMinHeap(); bool testRemovalSkewMaxHeap(); bool testcorrectNPLValuesLeftistMinHeap(); bool testcorrectNPLValuesLeftistMaxHeap(); bool testLeftistPropertyMinHeap(); bool testLeftistPropertyMaxHeap(); bool testSkewPropertyMinHeap(); bool testSkewPropertyMaxHeap(); bool testRebuildWithNewPriority(); bool testRebuildWithNewPrioritySkew(); bool testMergeEmptyWithPopulatedQueue(); bool testMergeEmptyWithPopulatedQueueSkew(); bool testDequeueEmptyQueue(); bool testDequeueEmptyQueueSkew(); bool testMergeWithQueueDifferentPriorities(); bool testMergeWithQueueDifferentPrioritiesSkew(); bool testMergeWithQueueDifferentStructures(); bool testMergeWithQueueSelf(); bool testConstructor(); bool testCopyConstructor(); bool testCopyConstructorEmpty(); bool testCopyConstructorNotEmpty(); bool testAssignmentOperator(); bool testAssignmentOperatorEdgeCase(); bool testDestructor(); bool testPrintOrderQueueLeftistMinHeap(); bool testPrintOrderQueueLeftistMaxHeap(); bool testPrintOrderQueueSkewMinHeap(); bool testPrintOrderQueueSkewMaxHeap();
};
//Main function to run tests in int main() { Tester tester; bool constructorResult = tester.testConstructor(); cout << (constructorResult ? "Constructor test passed\n" : "Constructor test failed\n") << endl; bool copyConstructorResult = tester.testCopyConstructor(); cout << (copyConstructorResult ? "Copy constructor test passed\n" : "Copy constructor test failed\n") << endl; bool copyConstructorEmptyResult = tester.testCopyConstructorEmpty(); cout << (copyConstructorEmptyResult ? "Copy constructor empty test passed\n" : "Copy constructor empty test failed\n") << endl; bool copyConstructorNotEmptyResult = tester.testCopyConstructorNotEmpty(); cout << (copyConstructorNotEmptyResult ? "Copy constructor not empty test passed\n" : "Copy constructor not empty test failed\n") << endl; bool assignmentOperatorResult = tester.testAssignmentOperator(); cout << (assignmentOperatorResult ? "Assignment operator test passed\n" : "Assignment operator test failed\n") << endl; bool assignmentOperatorEdgeCaseResult = tester.testAssignmentOperatorEdgeCase(); cout << (assignmentOperatorEdgeCaseResult ? "Assignment operator edge case test passed\n" : "Assignment operator edge case test failed\n") << endl; // still need to fix? bool destructorResult = tester.testDestructor(); cout << (destructorResult ? "Destructor test passed\n" : "Destructor test failed\n") << endl; bool insertionMinHeapResult = tester.testInsertionLeftistMinHeap(); cout << (insertionMinHeapResult ? "Insertion min heap test passed\n" : "Insertion min heap test failed\n") << endl; bool insertionMaxHeapResult = tester.testInsertionLeftistMaxHeap(); cout << (insertionMaxHeapResult ? "Insertion max heap test passed\n" : "Insertion max heap test failed\n") << endl; bool insertionEdgeCaseResult = tester.testInsertionEdgeCase(); cout << (insertionEdgeCaseResult ? "Insertion edge case test passed\n" : "Insertion edge case test failed\n") << endl; bool removalMinHeapResult = tester.testRemovalLeftistMinHeap(); cout << (removalMinHeapResult ? "Removal min heap test passed\n" : "Removal min heap test failed\n") << endl; bool removalMaxHeapResult = tester.testRemovalLeftistMaxHeap(); cout << (removalMaxHeapResult ? "Removal max heap test passed\n" : "Removal max heap test failed\n") << endl; bool insertionSkewMinHeapResult = tester.testInsertionSkewMinHeap(); cout << (insertionSkewMinHeapResult ? "Insertion skew min heap test passed\n" : "Insertion skew min heap test failed\n") << endl; bool insertionSkewMaxHeapResult = tester.testInsertionSkewMaxHeap(); cout << (insertionSkewMaxHeapResult ? "Insertion skew max heap test passed\n" : "Insertion skew max heap test failed\n") << endl; bool removalSkewMinHeapResult = tester.testRemovalSkewMinHeap(); cout << (removalSkewMinHeapResult ? "Removal skew min heap test passed\n" : "Removal skew min heap test failed\n") << endl; bool removalSkewMaxHeapResult = tester.testRemovalSkewMaxHeap(); cout << (removalSkewMaxHeapResult ? "Removal skew max heap test passed\n" : "Removal skew max heap test failed\n") << endl; bool correctNPLValuesMinHeapResult = tester.testcorrectNPLValuesLeftistMinHeap(); cout << (correctNPLValuesMinHeapResult ? "Correct NPL values min heap test passed\n" : "Correct NPL values min heap test failed\n") << endl; bool correctNPLValuesMaxHeapResult = tester.testcorrectNPLValuesLeftistMaxHeap(); cout << (correctNPLValuesMaxHeapResult ? "Correct NPL values max heap test passed\n" : "Correct NPL values max heap test failed\n") << endl; bool correctLeftistPropertyMinHeap = tester.testLeftistPropertyMinHeap(); cout << (correctLeftistPropertyMinHeap ? "Correct leftist property min heap test passed\n" : "Correct leftist property min heap test failed\n") << endl; bool correctLeftistPropertyMaxHeap = tester.testLeftistPropertyMaxHeap(); cout << (correctLeftistPropertyMaxHeap ? "Correct leftist property max heap test passed\n" : "Correct leftist property max heap test failed\n") << endl; bool correctSkewPropertyMinHeap = tester.testSkewPropertyMinHeap(); cout << (correctSkewPropertyMinHeap ? "Correct skew property min heap test passed\n" : "Correct skew property min heap test failed\n") << endl; bool correctSkewPropertyMaxHeap = tester.testSkewPropertyMaxHeap(); cout << (correctSkewPropertyMaxHeap ? "Correct skew property max heap test passed\n" : "Correct skew property max heap test failed\n") << endl; bool rebuildWithNewPriorityResult = tester.testRebuildWithNewPriority(); cout << (rebuildWithNewPriorityResult ? "Rebuild with new priority test passed\n" : "Rebuild with new priority test failed\n") << endl; bool rebuildWithNewPriorityResultSkew = tester.testRebuildWithNewPrioritySkew(); cout << (rebuildWithNewPriorityResultSkew ? "Rebuild with new priority skew test passed\n" : "Rebuild with new priority skew test failed\n") << endl; bool mergeEmptyWithPopulatedQueueResult = tester.testMergeEmptyWithPopulatedQueue(); cout << (mergeEmptyWithPopulatedQueueResult ? "Merge empty with populated queue test passed\n" : "Merge empty with populated queue test failed\n") << endl; bool mergeEmptyWithPopulatedQueueSkewResult = tester.testMergeEmptyWithPopulatedQueueSkew(); cout << (mergeEmptyWithPopulatedQueueSkewResult ? "Merge empty with populated queue skew test passed\n" : "Merge empty with populated queue skew test failed\n") << endl; bool dequeueEmptyQueueResult = tester.testDequeueEmptyQueue(); cout << (dequeueEmptyQueueResult ? "Dequeue empty queue test passed\n" : "Dequeue empty queue test failed\n") << endl; bool dequeueEmptyQueueSkewResult = tester.testDequeueEmptyQueueSkew(); cout << (dequeueEmptyQueueSkewResult ? "Dequeue empty queue skew test passed\n" : "Dequeue empty queue skew test failed\n") << endl; bool mergeWithDifferentPrioritiesResult = tester.testMergeWithQueueDifferentPriorities(); cout << (mergeWithDifferentPrioritiesResult ? "Merge with different priorities test passed\n" : "Merge with different priorities test failed\n") << endl; bool mergeWithDifferentPrioritiesSkewResult = tester.testMergeWithQueueDifferentPrioritiesSkew(); cout << (mergeWithDifferentPrioritiesSkewResult ? "Merge with different priorities skew test passed\n" : "Merge with different priorities skew test failed\n") << endl; bool mergeWithDifferentStructuresResult = tester.testMergeWithQueueDifferentStructures(); cout << (mergeWithDifferentStructuresResult ? "Merge with different structures test passed\n" : "Merge with different structures test failed\n") << endl; bool mergeWithSelfResult = tester.testMergeWithQueueSelf(); cout << (mergeWithSelfResult ? "Merge with self test passed\n" : "Merge with self test failed\n") << endl;
return 0;}
//Leftist insertion of a min heap bool Tester::testInsertionLeftistMinHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
// Insert random orders into the queue genRandomOrder(testQueue); // Check there's actually x orders in the queue bool numOrders = (testQueue.numOrders() == Orders); // Check it's actually following min-heap properties. bool validMinHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); //testQueue.dump(); // Return true if all conditions pass false otherwise return numOrders && validMinHeap;}
bool Tester::testInsertionLeftistMaxHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
// Insert random orders into the queue genRandomOrder(testQueue); // Check there's actually x orders in the queue bool numOrders = (testQueue.numOrders() == Orders); // Check it's actually following max-heap properties. bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());// testQueue.dump();
// Return true if all conditions pass false otherwise return numOrders && validMaxHeap;}
bool Tester::testRemovalLeftistMinHeap() { //Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
//Insert random orders into the queue genRandomOrder(testQueue); //cout << "Dump Before Removal: ";// testQueue.dump();
bool minheapOrder = true; int previousPriority = 0; for(int i = 0; i < removeOrders; i++){ Order orderRemoved = testQueue.getNextOrder(); //create variable to store the current priority being removed int currentPriority = testQueue.getPriorityFn()(orderRemoved); // cout << "Removed Order with Priority: " << currentPriority << endl; if (currentPriority < previousPriority) { minheapOrder = false; break; } // Update previous priority previousPriority = currentPriority; } //cout << "Dump After Removal: ";// testQueue.dump();
//after removing check if it maintains min-heap properties bool validMinHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());
// Return true if all conditions pass false otherwise return minheapOrder && validMinHeap;}
bool Tester::testRemovalLeftistMaxHeap() { //Do the same thing as testRemovalLeftistMinHeap //but with a max heap variables MQueue testQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
genRandomOrder(testQueue); bool maxheapOrder = true; //Except here we start with the highest possible value // for the priority int previousPriority = 10400; for(int i = 0; i < removeOrders; i++){ Order orderRemoved = testQueue.getNextOrder(); int currentPriority = testQueue.getPriorityFn()(orderRemoved);
if (currentPriority > previousPriority) { maxheapOrder = false; break; } previousPriority = currentPriority;}
//after removing check if it maintains max-heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());
// Return true if all conditions pass false otherwise return maxheapOrder && validMaxHeap;}
bool Tester::testInsertionEdgeCase() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST); //Insert an order with priority 0 Order zeroPrior("Customer", 0, 0, 0, 0, 0, 0, 0, 0); //Then we attempt to insert the order into the queue. testQueue.insertOrder(zeroPrior); //Nothing should've been inserted into the queue bool numOrders = (testQueue.numOrders() == 0); return numOrders; }
bool Tester::testInsertionSkewMinHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, SKEW);
// Insert random orders into the queue genRandomOrder(testQueue); // Check there's actually x orders in the queue bool numOrders = (testQueue.numOrders() == Orders); // Check it's actually following min-heap properties. bool validMinHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());// testQueue.dump();
// Return true if all conditions pass false otherwise return numOrders && validMinHeap;}
bool Tester::testInsertionSkewMaxHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW);
// Insert random orders into the queue genRandomOrder(testQueue); // Check there's actually x orders in the queue bool numOrders = (testQueue.numOrders() == Orders); // Check it's actually following max-heap properties. bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); //testQueue.dump(); // Return true if all conditions pass false otherwise return numOrders && validMaxHeap;}
bool Tester::testRemovalSkewMinHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, SKEW);
// Insert random orders into the queue genRandomOrder(testQueue); bool minheapOrder = true; int previousPriority = 0; for(int i = 0; i < removeOrders; i++){ Order orderRemoved = testQueue.getNextOrder(); //create variable to store the current priority being removed int currentPriority = testQueue.getPriorityFn()(orderRemoved); // Check if current priority is less than previous priority if (currentPriority < previousPriority) { minheapOrder = false; break; } // Update previous priority previousPriority = currentPriority; } //after removing check if it maintains min-heap properties bool validMinHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); // Return true if all conditions pass false otherwise return minheapOrder && validMinHeap;}
bool Tester::testRemovalSkewMaxHeap() { //Do the same thing as testRemovalSkewMinHeap //but with a max heap variables MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW); genRandomOrder(testQueue);
bool maxheapOrder = true; int previousPriority = 10400; for(int i = 0; i < removeOrders; i++){ Order orderRemoved = testQueue.getNextOrder(); int currentPriority = testQueue.getPriorityFn()(orderRemoved); if (currentPriority > previousPriority) { maxheapOrder = false; break; } previousPriority = currentPriority; } //after removing check if it maintains max-heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); // Return true if all conditions pass false otherwise return maxheapOrder && validMaxHeap;}
bool Tester::testcorrectNPLValuesLeftistMinHeap() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
// Insert random orders into the queue genRandomOrder(testQueue); bool validNPL = checkNPLValues(testQueue.m_heap); return validNPL;}
bool Tester::testcorrectNPLValuesLeftistMaxHeap() { //Same thing as correctNPLValuesLeftisit but just //Maxheap variable MQueue testQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
//Insert random ordders into the queue genRandomOrder(testQueue); bool validNPL = checkNPLValues(testQueue.m_heap); return validNPL;}
bool Tester::testLeftistPropertyMinHeap() { //Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST); //Insert random orders into the queue genRandomOrder(testQueue); bool validLeftist = checkLeftistProperty(testQueue.m_heap);
//Return true if all conditions pass false otherwise return validLeftist; }
bool Tester::testLeftistPropertyMaxHeap() { //Same as testLeftistPropertyMinHeap but with maxheap variables MQueue testQueue(priorityMaxHeap, MAXHEAP, LEFTIST); genRandomOrder(testQueue); bool validLeftist = checkLeftistProperty(testQueue.m_heap);
//Return true if all conditions pass false otherwise return validLeftist;}
bool Tester::testSkewPropertyMinHeap() { //Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, SKEW); //Insert random orders into the queue genRandomOrder(testQueue); bool validSkew = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());
//Return true if all conditions pass false otherwise return validSkew;}
bool Tester::testSkewPropertyMaxHeap() { //Same as testSkewPropertyMinHeap but with maxheap variables MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW); genRandomOrder(testQueue); bool validSkew = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn());
//Return true if all conditions pass false otherwise return validSkew;}
bool Tester::testRebuildWithNewPriority() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
// Insert random orders into the queue genRandomOrder(testQueue); // Extract nodes into vector vector<Node*> orders; extractTester(testQueue.m_heap, orders); testQueue.clear(); // Change priority function testQueue.setPriorityFn(priorityMaxHeap, MAXHEAP); // Reinsert nodes for (unsigned int i = 0; i < orders.size(); i++) { testQueue.insertOrder(orders.at(i)->getOrder()); } // Check heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); return validMaxHeap;}
bool Tester::testRebuildWithNewPrioritySkew() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, SKEW);
// Insert random orders into the queue genRandomOrder(testQueue); //testQueue.dump(); // Extract nodes into vector vector<Node*> orders; extractTester(testQueue.m_heap, orders); testQueue.clear(); // Change priority function testQueue.setPriorityFn(priorityMaxHeap, MAXHEAP); // Reinsert nodes for (unsigned int i = 0; i < orders.size(); i++) { testQueue.insertOrder(orders.at(i)->getOrder()); } // Check heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); //testQueue.dump(); return validMaxHeap;}
bool Tester::testMergeEmptyWithPopulatedQueue() {
// Create an empty MQueue MQueue emptyQueue(priorityMinHeap, MINHEAP, LEFTIST); // Create a populated MQueue MQueue populatedQueue(priorityMinHeap, MINHEAP, LEFTIST); // Insert random orders into queue genRandomOrder(populatedQueue); int initialSize = populatedQueue.numOrders(); // Merge populatedQueue into emptyQueue emptyQueue.mergeWithQueue(populatedQueue); // Check conditions of emptyQueue and populatedQueue bool isSizeCorrect = (emptyQueue.numOrders() == initialSize); bool isPopulatedEmpty = (populatedQueue.numOrders() == 0); bool validHeap = heapProperties(emptyQueue.m_heap, emptyQueue.getHeapType(), emptyQueue.getStructure(), emptyQueue.getPriorityFn()); // Return true if all conditions pass false otherwise return isSizeCorrect && validHeap && isPopulatedEmpty;}
bool Tester::testMergeEmptyWithPopulatedQueueSkew() { // Create an empty MQueue MQueue emptyQueue(priorityMinHeap, MINHEAP, SKEW);
// Create a populated MQueue MQueue populatedQueue(priorityMinHeap, MINHEAP, SKEW); // Insert random orders into queue genRandomOrder(populatedQueue); int initialSize = populatedQueue.numOrders(); // Merge populatedQueue into emptyQueue emptyQueue.mergeWithQueue(populatedQueue); // Check conditions of emptyQueue and populatedQueue bool isSizeCorrect = (emptyQueue.numOrders() == initialSize); bool isPopulatedEmpty = (populatedQueue.numOrders() == 0); bool validHeap = heapProperties(emptyQueue.m_heap, emptyQueue.getHeapType(), emptyQueue.getStructure(), emptyQueue.getPriorityFn()); // Return true if all conditions pass false otherwise return isSizeCorrect && validHeap && isPopulatedEmpty;}
bool Tester::testDequeueEmptyQueue() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST); //We dont add anything since it's supposed to be empty simply try to dequeue bool exceptionThrown = false; try { testQueue.getNextOrder(); } catch(const out_of_range& e) { exceptionThrown = true; } return exceptionThrown; }
bool Tester::testDequeueEmptyQueueSkew() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, SKEW); //We dont add anything since it's supposed to be empty simply try to dequeue bool exceptionThrown = false; try { testQueue.getNextOrder(); } catch(const out_of_range& e) { exceptionThrown = true; } return exceptionThrown; }
bool Tester::testMergeWithQueueDifferentPriorities() { //Create ab MQueue instance with specific heap type and structure MQueue populatedQueue(priorityMinHeap, MINHEAP, LEFTIST); //Creat an MQueue instance that has a different priority function MQueue emptyQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
//Insert random orders into populatedQueue genRandomOrder(populatedQueue); //Attempt to merge populatedQueue into emptyQueue //Should throw an exception bool exceptionThrown = false; try { emptyQueue.mergeWithQueue(populatedQueue); } catch(const domain_error& e) { exceptionThrown = true; } return exceptionThrown;}
bool Tester::testMergeWithQueueDifferentPrioritiesSkew() { //Create an MQueue instance with specific heap type and structure MQueue populatedQueue(priorityMinHeap, MINHEAP, SKEW); //Creat an MQueue instance that has a different priority function MQueue emptyQueue(priorityMaxHeap, MAXHEAP, SKEW);
//Insert random orders into populatedQueue genRandomOrder(populatedQueue); //Attempt to merge populatedQueue into emptyQueue //Should throw an exception bool exceptionThrown = false; try { emptyQueue.mergeWithQueue(populatedQueue); } catch(const domain_error& e) { exceptionThrown = true; } return exceptionThrown;}
bool Tester::testMergeWithQueueDifferentStructures() { //Create an MQueue instance with specific heap type and structure MQueue populatedQueue(priorityMinHeap, MINHEAP, LEFTIST); //Creat an MQueue instance that has a different structure MQueue emptyQueue(priorityMaxHeap, MAXHEAP, SKEW);
//Insert random orders into populatedQueue genRandomOrder(populatedQueue); //Attempt to merge populatedQueue into emptyQueue with a skew structure //Should throw an exception bool exceptionThrown = false; try { emptyQueue.mergeWithQueue(populatedQueue); } catch(const domain_error& e) { exceptionThrown = true; } return exceptionThrown;}
bool Tester::testMergeWithQueueSelf() { //Create an MQueue instance with specific heap type and structure MQueue populatedQueue(priorityMinHeap, MINHEAP, LEFTIST); //Attempt to merge populatedQueue into itself //Should throw an exception bool exceptionThrown = false; try { populatedQueue.mergeWithQueue(populatedQueue); } catch(const domain_error& e) { exceptionThrown = true; } return exceptionThrown; }
bool Tester::testConstructor() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
// Check initial conditions for MQueue bool CorrectPrioFn = (testQueue.getPriorityFn() == priorityMinHeap); bool CorrectHeapType = (testQueue.getHeapType() == MINHEAP); bool CorrectStructure = (testQueue.getStructure() == LEFTIST); bool isEmpty = (testQueue.numOrders() == 0); // Return true if all conditions pass false otherwise return CorrectPrioFn && CorrectHeapType && CorrectStructure && isEmpty;}
bool Tester::testCopyConstructor() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
//Insert x orders into the queue genRandomOrder(testQueue); // Create a copy of the original queue using the copy constructor MQueue copiedQueue(testQueue); // Verify that the copied queue has the same state as the original queue bool SamePrioFn = (copiedQueue.getPriorityFn() == testQueue.getPriorityFn()); bool SameHeapType = (copiedQueue.getHeapType() == testQueue.getHeapType()); bool SameStructure = (copiedQueue.getStructure() == testQueue.getStructure()); bool SameNumOrders = (copiedQueue.numOrders() == testQueue.numOrders()); //Create the string streams to compare the dumps stringstream testQueueDump, copiedQueueDump; // Redirect cout to the string streams streambuf* oldCoutBuffer = cout.rdbuf(); cout.rdbuf(testQueueDump.rdbuf()); testQueue.dump(); // Restore cout tp the original state cout.rdbuf(oldCoutBuffer); streambuf* oldCoutBuffer2 = cout.rdbuf(); cout.rdbuf(copiedQueueDump.rdbuf()); copiedQueue.dump(); cout.rdbuf(oldCoutBuffer2); //String streams should now have both dumps in them //Check if they are the same bool SameCopyDump = (testQueueDump.str() == copiedQueueDump.str()); // Return true if all conditions pass false otherwise return SamePrioFn && SameHeapType && SameStructure && SameNumOrders && SameCopyDump;}
bool Tester::testCopyConstructorEmpty() { //Create an Mqueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW);
//Create a copy of the original queue using the copy constructor MQueue copiedQueue(testQueue); //Verify that the copied queue is empty bool SameHeapType = (copiedQueue.getHeapType() == testQueue.getHeapType()); bool SameStructure = (copiedQueue.getStructure() == testQueue.getStructure()); bool isEmpty = (copiedQueue.numOrders() == 0); //Return true if the copied queue is empty false otherwise return isEmpty && SameStructure && SameHeapType;}
bool Tester::testCopyConstructorNotEmpty() { //Create an Mqueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST);
//Insert x orders into the queue genRandomOrder(testQueue); //Create a copy of the original queue using the copy constructor MQueue copiedQueue(testQueue); //Verify that the copied queue has the same state as the original queue bool SamePrioFn = (copiedQueue.getPriorityFn() == testQueue.getPriorityFn()); bool SameHeapType = (copiedQueue.getHeapType() == testQueue.getHeapType()); bool SameStructure = (copiedQueue.getStructure() == testQueue.getStructure()); bool SameNumOrders = (copiedQueue.numOrders() == testQueue.numOrders()); //Return true if all conditions pass false otherwise return SamePrioFn && SameHeapType && SameStructure && SameNumOrders;}
bool Tester::testAssignmentOperator() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW);
//Insert x orders into the queue genRandomOrder(testQueue); // Create a copy of the original queue using the assignment operator MQueue assignedQueue = testQueue; //Check if the copied queue has the same state as the original queue bool samePriorityFunction = (assignedQueue.getPriorityFn() == testQueue.getPriorityFn()); bool sameHeapType = (assignedQueue.getHeapType() == testQueue.getHeapType()); bool sameStructure = (assignedQueue.getStructure() == testQueue.getStructure()); bool sameNumOrders = (assignedQueue.numOrders() == testQueue.numOrders()); //Remove an order from the assigned queue assignedQueue.getNextOrder(); //Checks to see if the queue we copied has changed and that the original queue has not bool rootChanged = (assignedQueue.m_heap->m_order.getCustomer() != testQueue.m_heap->m_order.getCustomer()); bool sizeChanged = (assignedQueue.numOrders() != testQueue.numOrders()); return samePriorityFunction && sameHeapType && sameStructure && sameNumOrders && rootChanged && sizeChanged;}
bool Tester::testAssignmentOperatorEdgeCase() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMaxHeap, MAXHEAP, SKEW); //We leave the queue empty //Create a copy of the original queue using the assignment operator MQueue assignedQueue = testQueue; //Check if the copied queue has the same state as the original queue (Should be empty here) bool samePriorityFunction = (assignedQueue.getPriorityFn() == testQueue.getPriorityFn()); bool sameHeapType = (assignedQueue.getHeapType() == testQueue.getHeapType()); bool sameStructure = (assignedQueue.getStructure() == testQueue.getStructure()); bool sameNumOrders = (assignedQueue.numOrders() == testQueue.numOrders());
return samePriorityFunction && sameHeapType && sameStructure && sameNumOrders;}
bool Tester::testDestructor() { // Create an MQueue instance with specific heap type and structure MQueue* testQueue = new MQueue(priorityMaxHeap, MAXHEAP, LEFTIST);
//Insert orders into the queue genRandomOrder(*testQueue); //Store the number of orders in the queue int numOrders = testQueue->numOrders(); //Then we delete the queue to call the destructor delete testQueue; //We expect 5 orders to have been added to the queue //Can't really check i guess without valgrind for now. return (numOrders > 0);}
bool Tester::heapProperties(Node *node, HEAPTYPE heapType, STRUCTURE structure, prifn_t priFn) { if (node == nullptr) return true;
// Get priority of current node int parentPriority = priFn(node->getOrder()); // Check heap order with left child if (node->m_left != nullptr) { int leftPriority = priFn(node->m_left->getOrder()); if (heapType == MINHEAP) { if (parentPriority > leftPriority) { cout << "Heap order violated at node [" << parentPriority << "] with left child [" << leftPriority << "]" << endl; return false; } } else { // MAXHEAP if (parentPriority < leftPriority) { cout << "Heap order violated at node [" << parentPriority << "] with left child [" << leftPriority << "]" << endl; return false; } } } // Check heap order with right child if (node->m_right != nullptr) { int rightPriority = priFn(node->m_right->getOrder()); if (heapType == MINHEAP) { if (parentPriority > rightPriority) { cout << "Heap order violated at node [" << parentPriority << "] with right child [" << rightPriority << "]" << endl; return false; } } else { // MAXHEAP if (parentPriority < rightPriority) { cout << "Heap order violated at node [" << parentPriority << "] with right child [" << rightPriority << "]" << endl; return false; } } } // For leftist heap, check leftist property/NPL if (structure == LEFTIST) { // Get NPLs of children; NPL of null nodes is -1 int leftNPL = (node->m_left) ? node->m_left->getNPL() : -1; int rightNPL = (node->m_right) ? node->m_right->getNPL() : -1; // Check leftist property (left NPL >= right NPL) if (leftNPL < rightNPL) { cout << "Leftist property violated at node [" << parentPriority << "] with left NPL [" << leftNPL << "] and right NPL [" << rightNPL << "]" << endl; return false; } // Expected NPL: NPL(node) = min(NPL(left child), NPL(right child)) + 1 int expectedNPL = std::min(leftNPL, rightNPL) + 1; // Check if the stored NPL matches the expected NPL if (node->getNPL() != expectedNPL) { cout << "NPL mismatch at node [" << parentPriority << "]: expected NPL " << expectedNPL << ", but got " << node->getNPL() << endl; return false; } } // Recursively check left and right subtrees return heapProperties(node->m_left, heapType, structure, priFn) && heapProperties(node->m_right, heapType, structure, priFn);}
bool Tester::checkNPLValues(Node *node) { if (node == nullptr) return true;
// Get NPLs of children; null nodes have an NPL of -1 for validation int leftNPL = node->m_left ? node->m_left->m_npl : -1; int rightNPL = node->m_right ? node->m_right->m_npl : -1; // Check leftist property (left NPL >= right NPL) if (leftNPL < rightNPL) { return false; } // Expected NPL: NPL(node) = min(NPL(left child), NPL(right child)) + 1 int expectedNPL = min(leftNPL, rightNPL) + 1; // Check if the stored NPL matches the expected NPL if (node->m_npl != expectedNPL) { return false; } // Recursively validate for the left and right children return checkNPLValues(node->m_left) && checkNPLValues(node->m_right);}
bool Tester::checkLeftistProperty(Node *node) { if (node == nullptr) return true;
// Get NPLs of children; null nodes have an NPL of -1 for validation int leftNPL = node->m_left ? node->m_left->m_npl : -1; int rightNPL = node->m_right ? node->m_right->m_npl : -1; //Check leftist property if(leftNPL < rightNPL) { return false; } return checkLeftistProperty(node->m_left) & checkLeftistProperty(node->m_right);}
void Tester::genRandomOrder(MQueue &queue) { Random nameGen(97, 122); // ASCII values for lowercase letters Random fifoGen(MINONE, MAX50); Random processTimeGen(MINONE, MAX12); Random dueTimeGen(MINONE, MAX12); Random slackTimeGen(MINONE, MAX12); Random materialGen(MINZERO, MAX100); Random importanceGen(MINONE, MAX100); Random workersGen(MAX100, MAX200); Random quantityGen(MIN1000, MAX10000);
for (int i = 0; i < Orders; i++) { // Generate a random name with 5 characters string name = nameGen.getRandString(5); // Create a new Order object with random values Order order(name, fifoGen.getRandNum(), processTimeGen.getRandNum(), dueTimeGen.getRandNum(), slackTimeGen.getRandNum(), materialGen.getRandNum(), importanceGen.getRandNum(), workersGen.getRandNum(), quantityGen.getRandNum()); // Insert the order into the queue queue.insertOrder(order); }} void Tester::extractTester(Node node, vector<Node> &nodeVector) { if (node == nullptr) { return; } // Recursively extract the left and right subtrees extractTester(node->m_left, nodeVector); extractTester(node->m_right, nodeVector);
// Add to vector and reset node nodeVector.push_back(node); node->m_left = nullptr; node->m_right = nullptr;}
/* Priority functions */ int priorityMaxHeap(const Order & order) { //this function works with a MAXHEAP //priority value is determined based on some criteria //priority value falls in the range [1101-10400] int minValue = MIN1000 + MAX100 + MINONE + MINZERO; int maxValue = MAX100 + MAX100 + MAX200 + MAX10000; //the larger value means the higher priority int priority = order.getMaterial() + order.getImportance() + order.getWorkForce() + order.getQuantity(); if (priority >= minValue && priority <= maxValue) return priority; else return 0; // this is an invalid order object }
int priorityMinHeap(const Order & order) { //this function works with a MINHEAP //priority value is determined based on some criteria //priority value falls in the range [4-86] int minValue = MINONE + MINONE + MINONE + MINONE; int maxValue = MAX12 + MAX12 + MAX12 + MAX50; //the smaller value means the higher priority int priority = order.getFIFO() + order.getProcessTime() + order.getDueTime() + order.getSlackTime(); if (priority >= minValue && priority <= maxValue) return priority; else return 0; // this is an invalid order object } are my two files im currently trying to fix this error in valgrind
==636833== 1 errors in context 2 of 16: ==636833== Invalid read of size 8 ==636833== at 0x49CDAF4: UnknownInlinedFun (basic_string.h:228) ==636833== by 0x49CDAF4: UnknownInlinedFun (basic_string.h:269) ==636833== by 0x49CDAF4: UnknownInlinedFun (basic_string.h:287) ==636833== by 0x49CDAF4: std::__cxx11::basic_string<char, std::char_traits, std::allocator >::~basic_string() (basic_string.h:809) ==636833== by 0x406043: Order::~Order() (mqueue.h:34) ==636833== by 0x4066FD: Node::~Node() (mqueue.h:85) ==636833== by 0x403CC6: Tester::testRebuildWithNewPriority() (mytest.cpp:568) ==636833== by 0x402A39: main (mytest.cpp:242) ==636833== Address 0x4df8fe0 is 0 bytes inside a block of size 88 free'd ==636833== at 0x4847BB8: operator delete(void*, unsigned long) (vg_replace_malloc.c:1181) ==636833== by 0x409387: MQueue::clearHelper(Node*) (mqueue.cpp:374) ==636833== by 0x4082FB: MQueue::clear() (mqueue.cpp:27) ==636833== by 0x403B57: Tester::testRebuildWithNewPriority() (mytest.cpp:553) ==636833== by 0x402A39: main (mytest.cpp:242) ==636833== Block was alloc'd at ==636833== at 0x4843FEC: operator new(unsigned long) (vg_replace_malloc.c:487) ==636833== by 0x4085F8: MQueue::insertOrder(Order const&) (mqueue.cpp:112) ==636833== by 0x405A65: Tester::genRandomOrder(MQueue&) (mytest.cpp:1061) ==636833== by 0x403B19: Tester::testRebuildWithNewPriority() (mytest.cpp:548) ==636833== by 0x402A39: main (mytest.cpp:242)
- Assistant
The issue you're encountering is due to accessing memory that has already been freed. Specifically, in your test case
testRebuildWithNewPriority, you're extracting pointers toNodeobjects, then clearing the queue, which deletes thoseNodeobjects. Subsequently, when you attempt to access theOrderobjects through these now-invalidNodepointers, Valgrind rightfully flags this as an invalid memory access.Here's a detailed breakdown of the problem and how to fix it:
Understanding the Problem
-
Extracting Node Pointers:
void Tester::extractTester(Node *node, vector<Node*> &nodeVector) { if (node == nullptr) { return; } extractTester(node->m_left, nodeVector); extractTester(node->m_right, nodeVector); nodeVector.push_back(node); node->m_left = nullptr; node->m_right = nullptr; }- What Happens Here: You're extracting pointers to
Nodeobjects from the heap and storing them in avector<Node*>.
- What Happens Here: You're extracting pointers to
-
Clearing the Queue:
void MQueue::clear() { if(m_heap != nullptr) { clearHelper(m_heap); m_heap = nullptr; m_size = 0; } }- What Happens Here: The
clearHelperfunction recursively deletes allNodeobjects in the heap. This includes theNodeobjects you've stored pointers to in yournodeVector.
- What Happens Here: The
-
Attempting to Access Deleted Nodes:
for (unsigned int i = 0; i < orders.size(); i++) { testQueue.insertOrder(orders.at(i)->getOrder()); }- What Happens Here: After clearing the queue, you're trying to access the
Orderobjects via the now-deletedNodepointers. This results in undefined behavior and causes Valgrind to report an "Invalid read."
- What Happens Here: After clearing the queue, you're trying to access the
Solution
To fix this issue, you should store copies of the
Orderobjects instead of pointers toNodeobjects. This way, even after deleting the originalNodeobjects, you still have validOrderdata to work with.Step-by-Step Fix
-
Modify the
extractTesterFunction:- Change the Vector to Store
OrderObjects:void Tester::extractTester(Node *node, vector<Order> &orderVector) { if (node == nullptr) { return; } extractTester(node->m_left, orderVector); extractTester(node->m_right, orderVector); orderVector.push_back(node->getOrder()); // Store a copy of the Order } - Explanation: Instead of storing
Node*, you're storing copies of theOrderobjects contained within eachNode. This prevents invalid memory access since you're no longer relying on the lifetime of theNodeobjects.
- Change the Vector to Store
-
Adjust Your Test Case:
- Change the Vector Type:
bool Tester::testRebuildWithNewPriority() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST); // Insert random orders into the queue genRandomOrder(testQueue); // Extract Orders instead of Node pointers vector<Order> orders; extractTester(testQueue.m_heap, orders); testQueue.clear(); // Change priority function testQueue.setPriorityFn(priorityMaxHeap, MAXHEAP); // Reinsert Orders into the queue for (unsigned int i = 0; i < orders.size(); i++) { testQueue.insertOrder(orders[i]); // Use the copied Order } // Check heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); return validMaxHeap; } - Explanation: You're now working with copies of
Orderobjects, ensuring that even after clearing the queue, theOrderdata remains valid for reinsertion.
- Change the Vector Type:
-
Ensure Proper Copy Semantics for
Order:- Check the
OrderClass: Ensure that theOrderclass has a proper copy constructor and assignment operator. IfOrdercontains dynamically allocated resources (likestd::stringobjects), the compiler-generated copy operations should suffice, but it's good practice to define them explicitly if needed.
- Check the
-
Optional: Improve
NodeCopying (If Needed):- If in the future you need to copy
Nodeobjects, ensure that they perform deep copies of theirOrderobjects to avoid similar issues.
- If in the future you need to copy
Final Revised Code Snippets
Modified
extractTesterFunction:void Tester::extractTester(Node *node, vector<Order> &orderVector) { if (node == nullptr) { return; } extractTester(node->m_left, orderVector); extractTester(node->m_right, orderVector); orderVector.push_back(node->getOrder()); // Store a copy of the Order }Updated
testRebuildWithNewPriorityTest Case:bool Tester::testRebuildWithNewPriority() { // Create an MQueue instance with specific heap type and structure MQueue testQueue(priorityMinHeap, MINHEAP, LEFTIST); // Insert random orders into the queue genRandomOrder(testQueue); // Extract Orders instead of Node pointers vector<Order> orders; extractTester(testQueue.m_heap, orders); testQueue.clear(); // Change priority function testQueue.setPriorityFn(priorityMaxHeap, MAXHEAP); // Reinsert Orders into the queue for (unsigned int i = 0; i < orders.size(); i++) { testQueue.insertOrder(orders[i]); // Use the copied Order } // Check heap properties bool validMaxHeap = heapProperties(testQueue.m_heap, testQueue.getHeapType(), testQueue.getStructure(), testQueue.getPriorityFn()); return validMaxHeap; }Additional Recommendations
-
Encapsulation:
- Access to
m_heap: Currently, yourTesterclass has direct access to theMQueue'sm_heapmember. It's better to encapsulate this by providing necessary getter functions or friend classes if needed. This promotes better object-oriented design and prevents unintended modifications.
- Access to
-
Memory Management:
- Avoid Raw Pointers: Wherever possible, use smart pointers (
std::unique_ptr,std::shared_ptr) to manage dynamic memory. This reduces the risk of memory leaks and dangling pointers.
- Avoid Raw Pointers: Wherever possible, use smart pointers (
-
Const-Correctness:
- Functions That Don't Modify State: Ensure that functions which do not modify the state of the object are marked as
const. This not only makes your code safer but also more understandable.
- Functions That Don't Modify State: Ensure that functions which do not modify the state of the object are marked as
-
Unit Testing Framework:
- Use a Testing Framework: Consider using a unit testing framework like Google Test or Catch2. These frameworks provide better structures for writing tests, assertions, and reporting results.
By implementing these changes, you should eliminate the Valgrind error and improve the overall robustness and maintainability of your code.
References:
Note: Always ensure that any resources you allocate are properly managed to prevent issues related to memory management.
TL;DR:
The Valgrind error occurs because your test extracts pointers toNodeobjects and then clears the queue, deleting thoseNodeobjects. Later, when accessing theOrderthrough these deletedNodepointers, you encounter invalid memory access. To fix this, modify your test to extract and store copies of theOrderobjects instead of pointers toNodeobjects. This ensures that after clearing the queue, you still have validOrderdata to work with. -