Jump to content

  • Log In with Google      Sign In   
  • Create Account


Comparing strings using a priority queue(heap)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 02 March 2013 - 08:04 PM

I made a heap that works as a priority queue.

I can make it to work with integers, floats and doubles, but when im using character strings it gives me an error.

Basically my heap uses comparison functions to find out in which order the numbers should be placed. In the comparison function I subtract the left value from the right value to determine where the value should be placed.

In order to use char strings, I use the strcmp function to achieve a similar result to subtracting left to right.

 

Heres my code(c++)

 

The main file. Error is all the way at the bottom for you to see

#pragma once
#include <iostream>
#include "Heap.h"
#include <string.h>
using namespace std;


int Compare(int left, int right)
{
	return (left - right);
}

double dCompare(double left, double right)
{
	return (left - right);
}

float fCompare(float left, float right)
{
	return (left - right);
}

int sCompare(char* left, char* right)
{
	return strcmp(left, right);
}



int main()
{
	//Declare a heap with the size of 10
	Heap<int> myHeap(10, Compare);

	//Insert Some items into the heap
	myHeap.Enqueue(1);
	myHeap.Enqueue(2);
	myHeap.Enqueue(3);
	myHeap.Enqueue(10);
	myHeap.Enqueue(12);
	myHeap.Enqueue(4);
	myHeap.Enqueue(8);
	myHeap.Enqueue(100);
	myHeap.Enqueue(87);
	myHeap.Enqueue(99);

	//Now show the items in the heap
	int index;
	for(index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}

	//Now remove some items from the heap
	myHeap.Dequeue();
	myHeap.Dequeue();
	myHeap.Dequeue();

	//Now show the updated heap
	cout << endl << endl << "Now showing the updated heap:" << endl << endl;
	for(index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}


	//Create a heap that uses a double instead of a int
    cout << endl << endl << "Creating a double heap" << endl << endl;
	Heap<double> doubleHeap(5, dCompare);
	doubleHeap.Enqueue(5.64);
	doubleHeap.Enqueue(6.37);
	doubleHeap.Enqueue(2.78);
	doubleHeap.Enqueue(1.32);
	doubleHeap.Enqueue(9.51);

	//Show the double heap
	for(int index = 1; index <= doubleHeap.m_count; index++)
	{
		cout << doubleHeap[index] << ", ";
	}

	//Remove some items from the double heap
	doubleHeap.Dequeue();
	doubleHeap.Dequeue();

	//Show the updated double heap
	cout << endl << endl << "Showing the updated double heap" << endl << endl;
	for(int index = 1; index <= doubleHeap.m_count; index++)
	{
		cout << doubleHeap[index] << ", ";
	}


	//Create a float Heap
	Heap<float> floatHeap(5, fCompare);
	floatHeap.Enqueue(20.22f);
	floatHeap.Enqueue(10.11f);
	floatHeap.Enqueue(30.33f);
	floatHeap.Enqueue(50.55f);
	floatHeap.Enqueue(40.44f);

	//Show the float heap
	cout << endl << endl << "The float Heap: " << endl << endl;
	for(int index = 1; index <= floatHeap.m_count; index++)
	{
		cout << floatHeap[index] << ", ";
	}

	//Remove some items from the heap
	floatHeap.Dequeue();
	floatHeap.Dequeue();

	//Show the updated float heap
	cout << endl << endl << "The float Heap: " << endl << endl;
	for(int index = 1; index <= floatHeap.m_count; index++)
	{
		cout << floatHeap[index] << ", ";
	}


	//Create a string heap
	Heap<char> stringHeap(5, sCompare);
	
	

	


	cin.get();
	return 0;
}

 

the heap class

 

#pragma once
#include "Array.h"




template <class DataType>
class Heap: public Array<DataType>
{
public:

	//CLASS VARIABLES======================================

	//Keeps track of how many items are in the heap
	int m_count;

	//Function pointer to a comparison function
	DataType (*m_compare)(DataType, DataType);


	//CLASS FUNCTIONS=======================================

	//Constructor: Initializes the array with p_size, and 
	//recieves a pointer to a function
	Heap( int p_size, DataType (*p_compare)(DataType, DataType))
		:Array<DataType>(p_size + 1)
	{
		//Number of items in the heap currently are zero
		m_count = 0;

		//Makes the function pointer point to the passed in pointer
		m_compare = p_compare;
	}


	//Enqueue: Inserts an item into the heap
	void Enqueue(DataType p_data)
	{
		//Updates the counter, to keep track of how many
		//items are in the heap
		m_count++;

		//If the number of entries is larger then the array size
		if(m_count >= m_size)
		{
			//The double the size of the array
			Resize(m_size*2);
		}

		//Inserts the the data in the proper index
		m_array[m_count] = p_data;

		//Perform the WalkUp algorithm to see if the newly inserted
		//item is larger then its parent
		WalkUp(m_count);
	}


	//Dequeue: Removes first/top/root item from the the heap
	void Dequeue()
	{
		//If the heap is not empty
		if(m_count >= 1)
		{
			//Moves the item at the bottom of the heap
			//to the root
			m_array[1] = m_array[m_count];

			//Calls the WalkDown function to align the nodes properly
			// to keep it as a heap
			WalkDown(1);

			//Decrements the number of items in the array
			m_count--;
		}
	}

	//Item: Returns the value at the top of the heap
	DataType& Item()
	{
		return m_array[1];
	}


	//WalkUp: Moves a piece of data upward through the tree, until
	//the tree becomes a valid heap
	void WalkUp(int p_index)
	{
		//The current parent index
		int parent = p_index / 2;

		//The current child index
		int child  = p_index;

		//A temporary variable that holds the data of the child
		DataType temp = m_array[child];

		//While the parent index is not zero
		while(parent > 0)
		{
			//Determines if the node is walking up is in
			//the correct place or not by checking the parent value

			//If the parent node is greater then the node that is being
			//walked up, the function uses the break keyword to quit the loop
		    //If the parent node is less then the node, then the parent
			//node is moved down into the child node, and both the parent 
			//and child pointers are divided by 2, moving them up one level.
			if(m_compare(temp, m_array[parent]) > 0)
			{
				m_array[child] = m_array[parent];
				child = parent;
				parent /= 2;
			}
			else
				break;
		}
		//The data that was supposed to be moved up is moved into the cell
		//that the child points to.
		m_array[child] = temp;
	}

	//WalkDown: Moves the root down the tree until it becomes a heap
	void WalkDown(int p_index)
	{
		//Keeps track of the current parent index
		int parent = p_index;

		//Keeps track of the current child index
		int child = p_index * 2;

		//Stores the data that is being walked down into a temporary variable
		DataType temp = m_array[parent];

		//Starts a loop, loops through the tree until the child index is
		//greater then the tree size
		while(child < m_count)
		{
			//Checks to see if the right child exists
			if(child < m_count - 1)
			{
				//Compares the left and right child to see which one is larger
				
				//             LEFT CHILD       RIGHT CHILD
				if(m_compare(m_array[child], m_array[child + 1]) < 0)
				{
					//If the right child is larger, then increment the child index
					//because the the index of the right child is always is one larger
					//then the left child
					child++;
				}
			}

			//Now the function knows which child it wants to move upward. It
            //Determines if the child node needs to move upward by comparing
			//it to the value in the temp variable

			//If a swap needs to be made
			if(m_compare(temp, m_array[child]) < 0)
			{
				//Moves the child upward into the parent index
				m_array[parent] = m_array[child];

				//Moves the the parent and child index down one level
				parent = child;
				child *= 2;
			}
			//If no swap is needed
			else
				break;
		}
		
		//The value in temp is placed into the correct index
		m_array[parent] = temp;
	}

};


	

and finally the error:

 

\desktop\heap\heap\example.cpp(122): error C2664: 'Heap<DataType>::Heap(int,DataType (__cdecl *)(DataType,DataType))' : cannot convert parameter 2 from 'int (__cdecl *)(char *,char *)' to 'char (__cdecl *)(char,char)'


 

1> with


 

1> [


 

1> DataType=char


 

1> ]


 

1> None of the functions with this name in scope match the target type


 

I know its saying that it cannot convert, but Im using templates so any datatype can work.


 



Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9388

Like
0Likes
Like

Posted 02 March 2013 - 08:12 PM

The error is pretty explicit what the problem is. You have a Heap<char> and the constructor wants a char (*)(char, char) function. A single char is not the same as a string. If you want a Heap that holds a string you should do something like Heap<std::string> or Heap<char *>. Of course, you'll probably still have problems because you specify DataType as the return type from the comparison function when you should probably standardize on something like int or bool.

#3 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 02 March 2013 - 08:21 PM

but if I use DataType, it can return an int, whenever the return value is int. The same goes for double and float.

hmmm im not getting something here



#4 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 02 March 2013 - 08:25 PM

Alright I changed my comparison function pointer to using ints only. This way it can read standards ints and char strings but not doubles or floats. How can I let it use any datatype?


Edited by ISDCaptain01, 02 March 2013 - 08:27 PM.


#5 ultramailman   Prime Members   -  Reputation: 1557

Like
0Likes
Like

Posted 02 March 2013 - 08:53 PM

Why can't it work for doubles and floats?



#6 JTippetts   Moderators   -  Reputation: 8159

Like
1Likes
Like

Posted 02 March 2013 - 08:53 PM

A common use case for something like this is to implement the comparison function as a precedence function that returns true if the first operand should precede the second and false if the second operand should precede the first. That way, you can implement compare() without caring what the data type is. Your current functions are implemented this way (if the sign of the subtraction is negative, that indicates the first operand should come before the second) but it does it in a way that the enclosing code needs to know what the data type is, when it really shouldn't have to care.



#7 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 02 March 2013 - 10:09 PM

Not sure I got what your exactly trying to say JTippetts

 

 

 

So far im thinking of using multiple constructors in my class each with its own enqueue/dequeue function



#8 JTippetts   Moderators   -  Reputation: 8159

Like
0Likes
Like

Posted 02 March 2013 - 10:32 PM

You're over-complicating it.

 

Look at your code, and the way you use compare().

 

if(m_compare(temp, m_array[parent]) > 0)
{
   // ...
}
else
{
   // ...
}

 

You use the return value of compare to determine the ordering of the two elements passed to it. The problem is, the code that calls compare() has to know what the data type is in order to determine that ordering. It has to know, for example, that it can be compared to 0. Why can't you do that comparison inside your compare() function instead? That way, your calling code never has to know what type of data it is acting on. All it has to know is whether or not operand 1 precedes operand 2.

 

This is the key to creating generic abstract data types. Encapsulate the data as much as you can, so that the algorithms themselves don't have to worry or know or care about what the types are.



#9 stannic   Members   -  Reputation: 173

Like
0Likes
Like

Posted 02 March 2013 - 10:33 PM

Rewrite your compare functions such that if left is greater than right return 1 or some number greater than 1 else if left is less than right return -1 or some number less than 1 else return 0 if its the same.

 

or as a hack, just use a double as the return type.


Edited by stannic, 02 March 2013 - 10:36 PM.


#10 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 03 March 2013 - 02:04 AM

Alright I made a comparison function like this:

int trueCompare(int left, int right)
{
	if(left > right)
	{
		return 1;
	}
	if(left < right)
	{
		return -1;
	}
	return 0;
}

 

lemme see if I can figure out more of this


Edited by ISDCaptain01, 03 March 2013 - 02:05 AM.


#11 ultramailman   Prime Members   -  Reputation: 1557

Like
0Likes
Like

Posted 03 March 2013 - 02:18 AM

Alright I made a comparison function like this:

int trueCompare(int left, int right)
{
	if(left > right)
	{
		return 1;
	}
	if(left < right)
	{
		return -1;
	}
	return 0;
}

 

lemme see if I can figure out more of this

I think that's a bit overkill, this is more suited for non integral types such as float and double. For integral types, a simple (left - right) like it was originally will do.



#12 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 03 March 2013 - 02:19 AM

^ that's what im trying to do. I want it to work for more than just ints. I still cant get it to work:

 

Heres what works:

 

1- Works with ints, doubles and floats but not with strings

 

2- Works with ints and strings but not doubles or floats


Edited by ISDCaptain01, 03 March 2013 - 02:21 AM.


#13 ultramailman   Prime Members   -  Reputation: 1557

Like
0Likes
Like

Posted 03 March 2013 - 02:28 AM

Why not let the user provide the comparison function?

So for char arrays, user would provide the function pointer to strcmp.

For int comparison, user would provide the pointer to int comparison function.

For float comparison, user would provide the pointer to float comparison function.

 

The function pointer can be passed to the constructor, or as a template arg.

 

Another alternative is to not use comparison functions, and just user arithmetic comparison operators on left and right. This will require the DataType to have some operators overloaded though.

 

Works with ints and strings but not doubles or floats

 

How? There should be one cmp function for each type, so why can't float cmp functions be implemented?


Edited by ultramailman, 03 March 2013 - 02:44 AM.


#14 ISDCaptain01   Members   -  Reputation: 1315

Like
0Likes
Like

Posted 03 March 2013 - 02:45 AM

alright im gonna try this tomorrow. Gonna go to sleep lol. Thanks for the ideas people. Ill update this if I get it working



#15 ISDCaptain01   Members   -  Reputation: 1315

Like
1Likes
Like

Posted 04 March 2013 - 01:42 AM

Well Everyone. I got it to work!!!!

 

What I did was remove the function pointer and made the comparison function built inside the class. The comparison function

just returns bool values so it can work with any datatype now:

 

Heres the brand new and improved class:

#pragma once
#include <iostream>
#include "Array.h"
using namespace std;


template <class DataType>


class Heap2: public Array<DataType>
{
public:

	//CLASS VARIABLES================================

	//Keeps track of how many items are in the heap
	int m_count;


	//CLASS FUNCTIONS================================


	//Constructor
	Heap2(int p_size)
		: Array<DataType> (p_size + 1)
	{
		m_count = 0;
	}


	//Enqueue
	void Enqueue(DataType p_data)
	{
		//Updates the counter, to keep track of how many
		//items are in the heap
		m_count++;

		//If the number of entries is larger then the array size
		if(m_count >= m_size)
		{
			Resize(m_size*2);
		}

		//Inserts the the data in the proper index
		m_array[m_count] = p_data;

		//Perform the WalkUp algorithm to see if the newly inserted
		//item is larger then its parent
		WalkUp(m_count);
	}

	//Dequeue
	void Dequeue()
	{
		//If the heap is not empty
		if(m_count >= 1)
		{
			//Moves the item at the bottom of the heap
			//to the root
			m_array[1] = m_array[m_count];

			//Calls the WalkDown function to align the nodes properly
			// to keep it as a heap
			WalkDown(1);

			//Decrements the number of items in the array
			m_count--;
		}
	}


	//WalkUp
	void WalkUp(int p_index)
	{
		//The current parent index
		int parent = p_index / 2;

		//The current child index
		int child  = p_index;

		//A temporary variable that holds the data of the child
		DataType temp = m_array[child];

		//While the parent index is not zero
		while(parent > 0)
		{
			//Determines if the node is walking up is in
			//the correct place or not by checking the parent value

			//If the parent node is greater then the node that is being
			//walked up, the function uses the break keyword to quit the loop
		    //If the parent node is less then the node, then the parent
			//node is moved down into the child node, and both the parent 
			//and child pointers are divided by 2, moving them up one level.
			if(m_compare(temp, m_array[parent]) == true)
			{
				m_array[child] = m_array[parent];
				child = parent;
				parent /= 2;
			}
			else
				break;
		}
		//The data that was supposed to be moved up is moved into the cell
		//that the child points to.
		m_array[child] = temp;
	}



	
	//WalkDown: Moves the root down the tree until it becomes a heap
	void WalkDown(int p_index)
	{
		//Keeps track of the current parent index
		int parent = p_index;

		//Keeps track of the current child index
		int child = p_index * 2;

		//Stores the data that is being walked down into a temporary variable
		DataType temp = m_array[parent];

		//Starts a loop, loops through the tree until the child index is
		//greater then the tree size
		while(child < m_count)
		{
			//Checks to see if the right child exists
			if(child < m_count - 1)
			{
				//Compares the left and right child to see which one is larger
				
				//             LEFT CHILD       RIGHT CHILD
				if(m_compare(m_array[child], m_array[child + 1]) == false)
				{
					//If the right child is larger, then increment the child index
					//because the the index of the right child is always is one larger
					//then the left child
					child++;
				}
			}

			//Now the function knows which child it wants to move upward. It
            //Determines if the child node needs to move upward by comparing
			//it to the value in the temp variable

			//If a swap needs to be made
			if(m_compare(temp, m_array[child]) == false)
			{
				//Moves the child upward into the parent index
				m_array[parent] = m_array[child];

				//Moves the the parent and child index down one level
				parent = child;
				child *= 2;
			}
			//If no swap is needed
			else
				break;
		}
		
		//The value in temp is placed into the correct index
		m_array[parent] = temp;
	}


	bool m_compare( DataType left, DataType right)
	{
		if(left > right)
			return true;
		if(right > left)
			return false;
		else
		{
			cout << "Critical Failure" << endl;
		}

	}

};


 

and heres the source file:

#include <iostream>
#include "Heap2.h"
using namespace std;


int main()
{
	//Create a heap and inserts some values into it
	cout << "Inserting ints into the heap..." << endl;
	Heap2<int> myHeap(5);
	myHeap.Enqueue(1);
	myHeap.Enqueue(2);
	myHeap.Enqueue(3);
	myHeap.Enqueue(10);
	myHeap.Enqueue(20);

	//Show the heap on screen
	cout << "Showing the heap: " << endl << endl;
	for(int index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}
	cout << endl << endl;

	
	//Create a double heap
	cout << "Inserting doubles into the heap..." << endl;
	Heap2<double> dHeap(5);
	dHeap.Enqueue(22.22);
	dHeap.Enqueue(33.33);
	dHeap.Enqueue(44.44);
	dHeap.Enqueue(11.11);
	dHeap.Enqueue(55.55);

	//Show the double heap on screen
	cout << "Showing the  double heap: " << endl << endl;
	for(int index = 1; index <= dHeap.m_count; index++)
	{
		cout << dHeap[index] << ", ";
	}
	cout << endl << endl;


	//Create a string heap
	cout << "Inserting strings into the heap..." << endl;
	Heap2<char*> sHeap(5);
	sHeap.Enqueue("Hello");
	sHeap.Enqueue("Bye");
	sHeap.Enqueue("Red");
	sHeap.Enqueue("Blue");
	sHeap.Enqueue("Green");

	//Show the string heap on screen
	cout << "Showing the  string heap: " << endl << endl;
	for(int index = 1; index <= sHeap.m_count; index++)
	{
		cout << sHeap[index] << ", ";
	}
	cout << endl << endl;




	cin.get();
	return 0;
}

 

Thanks to everyone for the input and ideas. Felt like I conquered something lol



#16 ultramailman   Prime Members   -  Reputation: 1557

Like
0Likes
Like

Posted 04 March 2013 - 01:56 AM

Ah, good job. I think there are ways to make it more general, but it's more important to have something working than to have a beautiful piece of art. : )



#17 Chad Smith   Members   -  Reputation: 1041

Like
0Likes
Like

Posted 04 March 2013 - 11:04 PM

Good job.

 

Little nitpick: maybe instead of having the count public, you could make that private then add a function that would return the current size of the Heap.  That way the size of the heap couldn't absolutely get modified when it is not supposed to.  But I guess you could say that is "preference." 

 

Though it's pretty good!  Last year for a class I had to write a heap.  Yours turned out A LOT better than mine did.  Mine was entirely to dependent on the datatype.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS