// 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 <sstream>
#include "mqueue.h"
#include <math.h>
#include <algorithm>
#include <random>
#include <vector>
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>((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<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 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<char>, std::allocator<char> >::~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)