0

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;
        }
};
2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by tesuji
0

yeah, aaaaaand the ardently demanding question is what does that only mean:

>> merge function is not working at all ?

Any error message, divide by zero, memory fault, endless loops, computer on strike, or something else, you see?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.