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 ++++++++++++++++++++++++++++--------------
 src/queue.h            | 21 ++++++++++++++++++---
 src/tests/heap.cpp     |  7 ++++---
 src/tests/listsort.cpp | 12 ++++++++++++
 4 files changed, 62 insertions(+), 20 deletions(-)

(limited to 'src')

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:
diff --git a/src/queue.h b/src/queue.h
index 78f6db6..8b5c607 100644
--- a/src/queue.h
+++ b/src/queue.h
@@ -8,14 +8,29 @@
 #ifndef BU_QUEUE_H
 #define BU_QUEUE_H
 
-#include <memory>
-
 namespace Bu
 {
-	template<typename value, typename valuealloc = std::allocator<value> >
+	/**
+	 * Queue abstract baseclass
+	 */
+	template<typename value>
 	class Queue
 	{
 	public:
+		Queue()
+		{
+		}
+
+		virtual ~Queue()
+		{
+		}
+
+		virtual void enqueue( const value &i )=0;
+		virtual value dequeue()=0;
+		virtual value &peek()=0;
+		virtual const value &peek() const=0;
+		virtual bool isEmpty() const=0;
+		virtual int getSize() const=0;
 
 	private:
 
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index ae130ec..b1f510a 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -38,13 +38,14 @@ typedef struct num
 	}
 } num;
 
-void printHeap( Bu::Heap<Bu::FString> &h, int j )
+void printHeap( Bu::Heap<Bu::FString> &/*h*/, int j )
 {
+	return;
 	Bu::FString sFName;
 	sFName.format("graph-step-%02d.dot", j );
 	Bu::File fOut( sFName, Bu::File::WriteNew );
-	Bu::Formatter f( Bu::File );
-	//h.print( f );
+	Bu::Formatter f( fOut );
+//	h.print( f );
 }
 
 int main()
diff --git a/src/tests/listsort.cpp b/src/tests/listsort.cpp
index f9236e6..09c0273 100644
--- a/src/tests/listsort.cpp
+++ b/src/tests/listsort.cpp
@@ -6,6 +6,18 @@ using namespace Bu;
 
 int main()
 {
+	/*
+	List<int> il;
+	il.append( 5 );
+	il.append( 12 );
+	il.append( 0 );
+	il.append( 7 );
+	il.append( 3 );
+	il.append( 5 );
+	Bu::__basicLTCmp<int> cmp;
+	il.sortI( cmp );
+	*/
+
 	FString a("Soggy"), b("Sam");
 
 	if( a < b )
-- 
cgit v1.2.3