[Hgengine-cvs] SF.net SVN: hgengine:[540] Mercury2/src/PriorityQueue.h

[<cn...@us...>]

Revision: 540
          http://hgengine.svn.sourceforge.net/hgengine/?rev=540&view=rev
Author:   cnlohr
Date:     2009-09-26 18:08:19 +0000 (Sat, 26 Sep 2009)

Log Message:
-----------
new priority queue (more lean-and-mean)

Modified Paths:
--------------
    Mercury2/src/PriorityQueue.h

Modified: Mercury2/src/PriorityQueue.h
===================================================================
--- Mercury2/src/PriorityQueue.h	2009-09-26 18:07:23 UTC (rev 539)
+++ Mercury2/src/PriorityQueue.h	2009-09-26 18:08:19 UTC (rev 540)
@@ -1,38 +1,177 @@
 #ifndef PRIORITYQUEUE_H
 #define PRIORITYQUEUE_H
 
-#include <list>
-#include <map>
+#include <stdlib.h>
 
-template<typename T1, typename T2>
+#define DEFAULTHEAPSIZE 8
+
 class PriorityQueue
 {
-	public:
-		void Insert(const T1& priority, const T2& x)
+public:
+	PriorityQueue( bool (*LessThanFn)( void*, void* ) )
+	{
+		Size = 0;
+		Comp = LessThanFn;
+		Reserved = DEFAULTHEAPSIZE;
+		Heap = (void**)malloc( sizeof( void* ) * Reserved );
+	}
+
+	~PriorityQueue()
+	{
+		free( Heap );
+	}
+
+	void PushRaw( void * ptr )
+	{
+		if( Size >= Reserved )
 		{
-			m_queue[priority].push_back(x);
+			Reserved *= 2;
+			Heap = (void**)realloc( Heap, sizeof( void* ) * Reserved );
 		}
-		
-		bool empty() { return m_queue.empty(); }
-		
-		const T1& PeekNextPriority() { return m_queue.begin()->first; }
-		T2& GetNext() { return m_queue.begin()->second.front(); }
-		void PopNext()
+		Heap[Size] = ptr;
+		Size++;
+	}
+
+	void Push( void * ptr )
+	{
+		unsigned i;
+		PushRaw( ptr );
+
+		//Percolate up
+		i = Size - 1;
+		while( i )
 		{
-			m_queue.begin()->second.pop_front();
-			
-			if ( m_queue.begin()->second.empty() )
-				m_queue.erase( m_queue.begin() );
+			int parent;
+			void * tmp;
+			parent = (i - 1)/2;
+
+			if( Comp( Heap[parent], Heap[i] ) )
+				break;
+
+			tmp = Heap[parent];
+			Heap[parent] = Heap[i];
+			Heap[i] = tmp;
+
+			i = parent;
 		}
-		
-	private:
-		std::map< T1, std::list<T2> > m_queue;
+	}
+
+	void Fixup()
+	{
+		int comps = 0;
+		int swaps = 0;
+		if( Size < 2 )
+			return;
+
+		unsigned i;
+
+		//As strange as it is, doing it in this order is linear time
+		//I don't fully understand the math behind it, but
+		//doing it in reverse order results in more swaps and comps.
+		//Comps should be close to but less than Size*2
+		//Swaps should be close to but less than Size
+		for( i = Size-1; i > 0; i-- )
+		{
+			void * swap;
+			int ths = i;
+			unsigned parent = (ths-1)/2;
+
+
+			comps++;
+			while( ths && Comp( Heap[ths], Heap[parent] ) )
+			{
+				swaps++; comps++;
+				swap = Heap[parent];
+				Heap[parent] = Heap[ths];
+				Heap[ths] = swap;
+
+				ths = parent;
+				parent = (ths-1)/2;
+			}
+		}
+	}
+
+	void * Front( )
+	{
+		if( Size )
+			return Heap[0];
+		else
+			return 0;
+	}
+
+	void * Peek( )
+	{
+		return Size?Heap[0]:0;
+	}
+
+	void * Pop( )
+	{
+		void * ret;
+		int i;
+		if( !Size )
+			return 0;
+		Size--;
+		if( !Size )
+			return Heap[0];
+
+		ret = Heap[0];
+
+		Heap[0] = Heap[Size];
+
+		i = 0;
+		//Now, heapify-down
+		do
+		{
+			int smaller;
+			int childL, childR;
+			void * swap;
+
+			childL = (i*2)+1;
+			childR = (i*2)+2;
+
+			//No Children?  Done!
+			if( childL > (int)Size && childR > (int)Size )
+				return ret;
+
+			if( childR > (int)Size )
+			{
+				if( Comp( Heap[childL], Heap[i] ) )
+				{
+					swap = Heap[childL];
+					Heap[childL] = Heap[i];
+					Heap[i] = swap;
+				}
+
+				return ret;
+			}
+
+			smaller = Comp( Heap[childL], Heap[childR] )?childL:childR;
+
+			//We're already smaller than the smallest child.
+			if( Comp( Heap[i], Heap[smaller] ) )
+				return ret;
+
+			swap = Heap[smaller];
+			Heap[smaller] = Heap[i];
+			Heap[i] = swap;
+			i = smaller;
+		}
+		while(true);
+	}
+
+	inline bool Empty() { return !Size; }
+private:
+	void ** Heap;
+	unsigned int Reserved;
+	unsigned int Size;
+	bool (*Comp)( void*, void*);
 };
 
 #endif
 
 /****************************************************************************
- *   Copyright (C) 2008 by Joshua Allen                                     *
+ *   Copyright (C) 2008-2009 by Joshua Allen                                *
+ *                              Charles Lohr                                *
  *                                                                          *
  *                                                                          *
  *   All rights reserved.                                                   *


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.