From 92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
Date: Wed, 18 Nov 2009 21:22:54 +0000
Subject: Hey, fixed the problems in heap.  It should now work properly no
 matter what the data or order etc.

---
 src/heap.h | 42 ++++++++++++++++++++++++++++--------------
 1 file changed, 28 insertions(+), 14 deletions(-)

(limited to 'src/heap.h')

diff --git a/src/heap.h b/src/heap.h
index a8d904c..523c8e2 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -12,14 +12,14 @@
 #include <memory>
 #include "bu/exceptionbase.h"
 #include "bu/util.h"
-// #include "bu/formatter.h"
+#include "bu/queue.h"
 
 namespace Bu
 {
 	subExceptionDecl( HeapException );
 
 	template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
-	class Heap
+	class Heap : public Queue<item>
 	{
 	public:
 		Heap() :
@@ -64,8 +64,10 @@ namespace Bu
 			aItem = NULL;
 		}
 
-		void enqueue( item i )
+		virtual void enqueue( const item &it )
 		{
+			item i = it; // TODO: This is a silly workaround, put the i item
+						 // at the end.
 			if( iFill+1 >= iSize )
 				upSize();
 
@@ -103,14 +105,21 @@ namespace Bu
 			iFill++;
 		}
 
-		item &peek()
+		virtual item &peek()
 		{
 			if( iFill == 0 )
 				throw HeapException("Heap empty.");
 			return aItem[0];
 		}
 
-		item dequeue()
+		virtual const item &peek() const
+		{
+			if( iFill == 0 )
+				throw HeapException("Heap empty.");
+			return aItem[0];
+		}
+
+		virtual item dequeue()
 		{
 			if( iFill == 0 )
 				throw HeapException("Heap empty.");
@@ -121,11 +130,15 @@ namespace Bu
 				int k = j*2+1;
 				if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) )
 				{
+					if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) )
+						break;
 					aItem[j] = aItem[k+1];
 					j = k+1;
 				}
 				else if( k < iFill )
 				{
+					if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) )
+						break;
 					aItem[j] = aItem[k];
 					j = k;
 				}
@@ -140,31 +153,32 @@ namespace Bu
 			return iRet;
 		}
 
-		bool isEmpty()
+		virtual bool isEmpty() const
 		{
 			return (iFill==0);
 		}
 
-		int getSize()
+		virtual int getSize() const
 		{
 			return iFill;
 		}
-/*
-		void print( Formatter &f )
+
+		/*
+		void print( class Formatter &f )
 		{
-			f << "graph G {" << f.nl;
+			f << "graph G {" << "\n";
 			for( int j = 0; j < iFill; j++ )
 			{
 				if( j*2+1 < iFill )
-					f << "    " << j << " -- " << j*2+1 << ";" << f.nl;
+					f << "    " << j << " -- " << j*2+1 << ";" << "\n";
 				if( j*2+2 < iFill )
-					f << "    " << j << " -- " << j*2+2 << ";" << f.nl;
+					f << "    " << j << " -- " << j*2+2 << ";" << "\n";
 			}
 			for( int j = 0; j < iFill; j++ )
 			{
-				f << "    " << j << " [label=\"" << aItem[j] << "\"];" << f.nl;
+				f << "    " << j << " [label=\"" << aItem[j] << "\"];" << "\n";
 			}
-			f << "}" << f.nl;
+			f << "}" << "\n";
 		} */
 
 	private:
-- 
cgit v1.2.3