Jump to content
  • Advertisement
Sign in to follow this  
McZ

templates and operators?

This topic is 4671 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to write a templated priority queue using a Binary Search Tree
	template <class T>
	class CBSTPriorityQueue {

		class CNode {
		public:

			T		m_Item;		//!< The item to store

			CNode	*m_pLeft;	//!< Root node of left sub tree.
			CNode	*m_pRight;	//!< Root node of right sub tree.

			/**
				Simple constructor

				@param i - Item to store
				@param l - Left node
				@param r - Right node
			*/
			CNode( T i, CNode *l, CNode *r )
			{ m_Item = i; m_pLeft = l; m_pRight = r; }

			/**
				Insert new item into tree.

				@param o - The item to insert.
			*/
			void insert( T o )
			{
				if( o < m_Item )
				{
					CLog::message(LML_DEBUG_RUN, "BST: insert left");
					// object has lower priority, insert to the left.
					if( m_pLeft != NULL )
						m_pLeft->insert(o);
					else
						m_pLeft = new CNode(o, NULL, NULL);
				}
				else if ( o >= m_Item )
				{
					CLog::message(LML_DEBUG_RUN, "BST: insert right");
					// object has higher or equal priority, insert to the right.
					if( m_pRight != NULL )
						m_pRight->insert(o);
					else
						m_pRight = new CNode(o, NULL, NULL);
				}
			}
		};

		int		m_iSize;	//!< Size of tree.
		CNode	*m_pRoot;	//!< Root node of tree.

		/**
			finds the node that has the item with highest priority.
			and delete the node.

			@return The item with highest priority.
		*/
		T removeMax()
		{
			assert( !isEmpty() );

			CNode *removeMe = m_pRoot;
			CNode *parent = NULL;

			while( removeMe->m_pRight != NULL )
			{
				parent = removeMe;
				removeMe = removeMe->m_pRight;
			};

			// Make the parent->right point to the removeMe left node.
			if( parent != NULL )
				parent->m_pRight = removeMe->m_pLeft;
			else if( m_pRoot != removeMe )
				m_pRoot = removeMe->m_pLeft;

			// save item
			T item = removeMe->m_Item;

			// delete the node
			delete removeMe;

			// return the item
			return item;
		}

		/**
			finds the node that has the item with highest priority.

			@return The item with highest priority.
		*/
		T getMax()
		{
			if( isEmpty() )
				throw QUEUE_EMPTY;

			CNode *node = m_pRoot;

			while( node->m_pRight != NULL )
			{
				node = node->m_pRight;
			};

			// return the item
			return node->m_Item;
		}

	public:

		/**
			Initializes the tree.
		*/
		CBSTPriorityQueue()
		{
			m_iSize = 0;
			m_pRoot = NULL;
		}

		/**
			Destroys the tree.

			@see destroyQueue().
		*/
		~CBSTPriorityQueue()
		{
			destroyQueue();
		}

		void enqueue( T o )
		{
			if( isEmpty() )
			{
				// Queue is empty insert first
				CLog::message(LML_DEBUG_RUN, "BST: insert at root");
				m_pRoot = new CNode( o, NULL, NULL );
			}
			else
			{
				CLog::message(LML_DEBUG_RUN, "BST: insert after root");
				m_pRoot->insert(o);
			}
		}

		T dequeue()
		{
			if( isEmpty() )
				return NULL;

			if( m_pRoot->m_pLeft == NULL && m_pRoot->m_pRight == NULL )
			{
				CLog::message(LML_DEBUG_RUN, "BST: delete root");
				T item = m_pRoot->m_Item;

				delete m_pRoot;

				m_pRoot = NULL;

				return item;
			}
			else
			{
				CLog::message(LML_DEBUG_RUN, "BST: delete other than root");
				return removeMax();
			}
		}

		void destroyQueue()
		{
			while( !isEmpty() )
			{
				dequeue();
			};
		}

		T peek() { return getMax(); }

		bool isFull() { return false; }

		bool isEmpty() { return (m_pRoot == NULL); }

		int getSize() { return m_iSize; }
	};


I have noticed that the BST I have doesn't call the >= and < operators on the class I store in the BST, this results in wierd results. can't I call an operator on a templated item wouldn't that call the operator for the class that T is. example:
class CTest {
 int a;
public:

 bool operator < ( CTest &t )
 {
  return ( a < t.a );
 }
};

CBSTPriorityQueue<CTest*> Queue;
[/soucre]

if I do like the example above it doesn't call the operators on the CTest class.

Share this post


Link to post
Share on other sites
Advertisement
The problem is that you're storing pointers to objects of type CTest in your BST structure instead of actual CTest objects. When the BST calls any comparison operator it will be comparing addresses. The solution to this problem is to add an additional template argument to your BST class that specifies a object for performing the comparison. You might want to take a look at how std::map does this.

Share this post


Link to post
Share on other sites
First I'll assume you know that the STL provides a priority queue in <queue> and that vectors can be used as heaps which is a more approriate storage structure.

You should specialize the template for pointer types, i.e. template<class T> class CBSTPriorityQueue<T*>. So that you don't generate this for every type of pointer you should have a full specialization for void *, i.e. template <> class CBSTPriorityQueue<void *>, that the specialization for pointers inherit off of. The pointer specialization casts the pointers to the right type so that only the correct type of pointers are inserted and you're type safe.

A binary tree is a bad choice. Presumably this is a learning exercise and as such you need to learn to do it as a heap. Failing that you need to at least use a height balanced tree. Without that you run a high risk of degenerating into a linked list. Particularly if it is used for scheduling. You tend to take the lowest element and insert the highest element.

You really should seperate the whole container part out of it. Create a container template and use it in your priority queue. A balanced binary tree or even a heap is a bit more involved and there is no reason to clutter up the priority queue with it.

Share this post


Link to post
Share on other sites
LilBudyWizer > Yes I know, but I want to try for learning purpose. and I'm planning to extend the BST to be a balanced tree.

Share this post


Link to post
Share on other sites
My suggestions were based off that assumption. The specialization is how you handle the special case of a container of pointers. You want to dereference if it is pointer, but not otherwise. Moving the container out as a seperate class will make it easier to change later to a balanced tree or a heap or simply to work on/test the container.

Share this post


Link to post
Share on other sites
Since this is a learning exercise I'll point out the solution LilBudyWizer suggested is a method for reducing code bloat and isn't the correct solution to your original problem.

Suppose you created a template specialization of your container for pointers and then dereferenced them when performing comparisions (or any other operation like copy or assignment). Now suppose that would like to store pointers in your container and sort them by address. You could no longer do this without providing custom comparision operators for each type you might want to store and sort by address.

Again, the correct solution to the problem is to have an additional template
parameter that specifies a comparision operation for the type your storing in the container. This is what the STL does.

Share this post


Link to post
Share on other sites
I added a template parameter and a new class which overloads operator()

like this


/**
Default BST compare function
*/

template <class T>
class CBSTDefaultCompare {
public:
bool operator() (const T &a, const T &b)
{
return (a < b);
}
};

template <class T, class Value_Compare = CBSTDefaultCompare<T> >
class CBSTPriorityQueue {
...
};

// So now the compare looks like this
Value_Compare cmp;

if( cmp(o, m_Item ) )
{
...
}
else
{
...
}



so now when storing the CTest pointer I have created a new compare class that takes two CTest pointers and compare the correct values.

Share this post


Link to post
Share on other sites
Looks like you've got the idea. The STL already provides a less functor (std::less)as well as some others like <= and == so no need to write your own once you understand how they work.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!