Hello all,
I was wondering if you all could help me out with a Binomial Queue problem I am having. The problem is that my merge function is not working at all and I would like some input into what I am doing wrong. Here is my merge function:
//merges this with rhs tree
void merge(BiQueue<T> &rhs){
currentSize += rhs.currentSize;
BiNode<T> *carry = NULL;
for(int posistion = 0; posistion < this->MAX_SIZE; posistion++){
if(this->Trees[posistion] == NULL && rhs.Trees[posistion] != NULL && carry == NULL){
this->Trees[posistion] = rhs.Trees[posistion];
rhs.Trees[posistion] = NULL;
//cout << "here 1" << endl;
}
else if(this->Trees[posistion] == NULL && rhs.Trees[posistion] == NULL && carry != NULL){
this->Trees[posistion] = carry;
carry = NULL;
//cout << "here 2" << endl;
}
else if(this->Trees[posistion] != NULL && rhs.Trees[posistion] != NULL && carry == NULL){
carry = mergeSame(this->Trees[posistion], rhs.Trees[posistion]);
this->Trees[posistion] = NULL;
rhs.Trees[posistion] = NULL;
//cout << "here 4" << endl;
}
else if(this->Trees[posistion] != NULL && rhs.Trees[posistion] != NULL && carry != NULL){
if(this->Trees[posistion]->value < rhs.Trees[posistion]->value && Trees[posistion]->value < carry->value){
carry = mergeSame(carry, rhs.Trees[posistion]);
rhs.Trees[posistion] = NULL;
}
else if(rhs.Trees[posistion]->value < Trees[posistion]->value && rhs.Trees[posistion]->value < carry->value){
carry = mergeSame(carry, Trees[posistion]);
Trees[posistion] = rhs.Trees[posistion];
rhs.Trees[posistion] = NULL;
}
else{
BiNode<T>* temp = carry;
carry = mergeSame(Trees[posistion], rhs.Trees[posistion]);
Trees[posistion] = temp;
rhs.Trees[posistion] = NULL;
temp = NULL;
}
}
}
}//end function(merge)Here is the rest of my code incase you do not see anything wrong there:
/*
David Tolley
CS2420
HW04
3846
*/
#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <class T>
class BiQueue{
public:
template <class T>
class BiNode{
public:
T value;
BiNode* leftChild;
BiNode* nextSib;
BiNode(T value){
this->value = value;
this->leftChild = NULL;
this->nextSib = NULL;
}
};
//current size of the forrest
int currentSize;
//vector holds the trees
vector<BiNode<T> *> Trees;
//const for the max size of the forest
static const int MAX_SIZE = 15;
//constructor for the queue, sets the max size for the vector holding the trees
BiQueue() : Trees(MAX_SIZE){
for(int posistion = 0; posistion < this->MAX_SIZE; posistion++)
Trees[posistion] = NULL;
this->currentSize = 0;
}
void printTree(){
string indent = "";
for(int posistion = 0; posistion < this->MAX_SIZE; posistion++)
printTree(this->Trees[posistion], indent);
}
void printTree(BiNode<T>* ptrNode, string indent){
if(ptrNode == NULL)
return;
cout << indent << ptrNode->value << endl;
indent.append(" ");
printTree(ptrNode->leftChild, indent);
printTree(ptrNode->nextSib, indent);
}
//function to insert a value in the forrest
void insert(T value){
BiQueue<T> newTree;
newTree.currentSize = 1;
newTree.Trees[0] = new BiNode<T>(value);
merge(newTree);
}
//finds the max value, deletes it, and returns that value
T deleteMax(){
T temp = findMax();
return temp;
}
//finds the max value
T findMax(){
if(Trees[findMaxIndex()] != NULL)
return Trees[findMaxIndex()]->value;
}
//finds the index of the max value
int findMaxIndex(){
int posistion;
int maxIndex;
for(posistion = 0; this->Trees[posistion] == NULL; posistion++)
;
for(maxIndex = posistion; posistion < this->Trees.size(); posistion++){
if(this->Trees[posistion] != NULL && this->Trees[posistion]->value > this->Trees[maxIndex]->value)
maxIndex = posistion;
}
return maxIndex;
}
//merges this with rhs tree
void merge(BiQueue<T> &rhs){
currentSize += rhs.currentSize;
BiNode<T> *carry = NULL;
for(int posistion = 0; posistion < this->MAX_SIZE; posistion++){
if(this->Trees[posistion] == NULL && rhs.Trees[posistion] != NULL && carry == NULL){
this->Trees[posistion] = rhs.Trees[posistion];
rhs.Trees[posistion] = NULL;
//cout << "here 1" << endl;
}
else if(this->Trees[posistion] == NULL && rhs.Trees[posistion] == NULL && carry != NULL){
this->Trees[posistion] = carry;
carry = NULL;
//cout << "here 2" << endl;
}
else if(this->Trees[posistion] != NULL && rhs.Trees[posistion] != NULL && carry == NULL){
carry = mergeSame(this->Trees[posistion], rhs.Trees[posistion]);
this->Trees[posistion] = NULL;
rhs.Trees[posistion] = NULL;
//cout << "here 4" << endl;
}
else if(this->Trees[posistion] != NULL && rhs.Trees[posistion] != NULL && carry != NULL){
if(this->Trees[posistion]->value < rhs.Trees[posistion]->value && Trees[posistion]->value < carry->value){
carry = mergeSame(carry, rhs.Trees[posistion]);
rhs.Trees[posistion] = NULL;
}
else if(rhs.Trees[posistion]->value < Trees[posistion]->value && rhs.Trees[posistion]->value < carry->value){
carry = mergeSame(carry, Trees[posistion]);
Trees[posistion] = rhs.Trees[posistion];
rhs.Trees[posistion] = NULL;
}
else{
BiNode<T>* temp = carry;
carry = mergeSame(Trees[posistion], rhs.Trees[posistion]);
Trees[posistion] = temp;
rhs.Trees[posistion] = NULL;
temp = NULL;
}
}
}
}//end function(merge)
//merges trees with the same size together
BiNode<T> *mergeSame(BiNode<T> *t1, BiNode<T> *t2){
BiNode<T>* big;
BiNode<T>* small;
if(t1->value < t2->value){
big = t2;
small = t1;
}
else{
big = t1;
small = t2;
}
if(small->nextSib != NULL)
cout << "oops..." << endl;
if(big->nextSib != NULL)
cout << "oops2..." << endl;
small->nextSib = big->leftChild;
big->leftChild = small;
return big;
}
};