From 62287ea894a1587553f017d0f6a09d4c87ad3b1f Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
Date: Tue, 19 Feb 2008 19:30:09 +0000
Subject: I believe this will do the trick.  The Bu::Heap class now uses the
 appropriate allocators for all work, every data type used in a Bu::Heap must
 support the equals operator and <= or >=, or you need to write your own
 comparison functor.

The heap works as both a min-heap and max-heap, just change out the functor used
for camparison, kinda' cool.

The print function I'll leave in for a little while, but not in the long run, it
just prints a dot graph to stdout.

Next up, the Ito version.
---
 src/heap.cpp       |  1 +
 src/heap.h         | 61 +++++++++++++++++++++++++++++++++++++++++++++++++-----
 src/tests/heap.cpp |  2 +-
 3 files changed, 58 insertions(+), 6 deletions(-)

diff --git a/src/heap.cpp b/src/heap.cpp
index 00a5d5d..01a5f50 100644
--- a/src/heap.cpp
+++ b/src/heap.cpp
@@ -7,3 +7,4 @@
 
 #include "heap.h"
 
+namespace Bu { subExceptionDef( HeapException ) }
diff --git a/src/heap.h b/src/heap.h
index 0ca4422..f276157 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -12,10 +12,13 @@
 #include <string.h>
 #include <memory>
 #include <iostream>
+#include "bu/exceptionbase.h"
 #include "bu/util.h"
 
 namespace Bu
 {
+	subExceptionDecl( HeapException );
+
 	template<typename item>
 	struct __basicLTCmp
 	{
@@ -24,26 +27,58 @@ namespace Bu
 			return a <= b;
 		}
 	};
+	
+	template<typename item>
+	struct __basicGTCmp
+	{
+		bool operator()( const item &a, const item &b )
+		{
+			return a >= b;
+		}
+	};
+
+	template<typename item>
+	struct __basicPtrLTCmp
+	{
+		bool operator()( const item &a, const item &b )
+		{
+			return *a <= *b;
+		}
+	};
+	
+	template<typename item>
+	struct __basicPtrGTCmp
+	{
+		bool operator()( const item &a, const item &b )
+		{
+			return *a >= *b;
+		}
+	};
 
 	template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
 	class Heap
 	{
 	public:
 		Heap() :
-			iSize( 40 ),
+			iSize( 7 ),
 			iFill( 0 ),
-			aItem( new item[iSize] )
+			aItem( ia.allocate( iSize ) )
 		{
 		}
 
 		virtual ~Heap()
 		{
-			delete[] aItem;
+			for( int j = 0; j < iFill; j++ )
+				ia.destroy( &aItem[j] );
+			ia.deallocate( aItem, iSize );
 			aItem = NULL;
 		}
 
 		void push( item i )
 		{
+			if( iFill+1 >= iSize )
+				upSize();
+
 			for( int j = 0; j < iFill; )
 			{
 				if( cmp( i, aItem[j] ) )
@@ -60,7 +95,7 @@ namespace Bu
 					j = j*2+2;
 				}
 			}
-			aItem[iFill] = i;
+			ia.construct( &aItem[iFill], i );
 			for( int j = iFill; j >= 0; )
 			{
 				int k = (j-1)/2;
@@ -75,11 +110,15 @@ namespace Bu
 
 		item &peek()
 		{
+			if( iFill == 0 )
+				throw HeapException("Heap empty.");
 			return aItem[0];
 		}
 
 		void pop()
 		{
+			if( iFill == 0 )
+				throw HeapException("Heap empty.");
 			int j;
 			for( j = 0; j < iFill; )
 			{
@@ -97,6 +136,7 @@ namespace Bu
 					break;
 			}
 			aItem[j] = aItem[iFill-1];
+			ia.destroy( &aItem[iFill-1] );
 			iFill--;
 		}
 
@@ -121,13 +161,24 @@ namespace Bu
 					  );
 			}
 			printf("}\n");
-		}		
+		}
+
+	private:
+		void upSize()
+		{
+			item *aNewItems = ia.allocate( iSize*2+1 );
+			memcpy( aNewItems, aItem, sizeof(item)*iFill );
+			ia.deallocate( aItem, iSize );
+			aItem = aNewItems;
+			iSize = iSize*2+1;
+		}
 
 	private:
 		int iSize;
 		int iFill;
 		item *aItem;
 		cmpfunc cmp;
+		itemalloc ia;
 	};
 };
 
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index e93749f..3217715 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -5,7 +5,7 @@
 
 int main()
 {
-	Bu::Heap<int> hInt;
+	Bu::Heap<int, Bu::__basicGTCmp<int> > hInt;
 
 	for( int j = 0; j < 15; j++ )
 	{
-- 
cgit v1.2.3