From e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314 Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
Date: Tue, 19 Feb 2008 09:24:27 +0000
Subject: Bu::Heap is a real class, it works great, except it doesn't grow
 right now. I'm thinking the heap should add one layer to the binary tree each
 time it grows, which means double+1 each time.  The Bu::ItoHeap will be
 implemented as soon as the rest of Bu::Heap is done.

Also, I finally added bu/util.h which is mainly handy template functions like
Bu::swap, Bu::min, Bu::max, and Bu::mid.  A few more may be added.
---
 src/heap.h | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 134 insertions(+)
 create mode 100644 src/heap.h

(limited to 'src/heap.h')

diff --git a/src/heap.h b/src/heap.h
new file mode 100644
index 0000000..0ca4422
--- /dev/null
+++ b/src/heap.h
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2007-2008 Xagasoft, All rights reserved.
+ *
+ * This file is part of the libbu++ library and is released under the
+ * terms of the license contained in the file LICENSE.
+ */
+
+#ifndef BU_HEAP_H
+#define BU_HEAP_H
+
+#include <stddef.h>
+#include <string.h>
+#include <memory>
+#include <iostream>
+#include "bu/util.h"
+
+namespace Bu
+{
+	template<typename item>
+	struct __basicLTCmp
+	{
+		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 ),
+			iFill( 0 ),
+			aItem( new item[iSize] )
+		{
+		}
+
+		virtual ~Heap()
+		{
+			delete[] aItem;
+			aItem = NULL;
+		}
+
+		void push( item i )
+		{
+			for( int j = 0; j < iFill; )
+			{
+				if( cmp( i, aItem[j] ) )
+				{
+					swap( i, aItem[j] );
+				}
+
+				if( cmp( i, aItem[j*2+1] ) )
+				{
+					j = j*2+1;
+				}
+				else
+				{
+					j = j*2+2;
+				}
+			}
+			aItem[iFill] = i;
+			for( int j = iFill; j >= 0; )
+			{
+				int k = (j-1)/2;
+				if( cmp( aItem[k], aItem[j] ) )
+					break;
+
+				swap( aItem[k], aItem[j] );
+				j = k;
+			}
+			iFill++;
+		}
+
+		item &peek()
+		{
+			return aItem[0];
+		}
+
+		void pop()
+		{
+			int j;
+			for( j = 0; j < iFill; )
+			{
+				if( cmp( aItem[j*2+2], aItem[j*2+1] ) && j*2+2 < iFill )
+				{
+					aItem[j] = aItem[j*2+2];
+					j = j*2+2;
+				}
+				else if( j*2+1 < iFill )
+				{
+					aItem[j] = aItem[j*2+1];
+					j = j*2+1;
+				}
+				else
+					break;
+			}
+			aItem[j] = aItem[iFill-1];
+			iFill--;
+		}
+
+		void print()
+		{
+			printf("graph G {\n");
+			for( int j = 0; j < iFill; j++ )
+			{
+				if( j*2+1 < iFill )
+					printf("    %d -- %d;\n",
+							j, j*2+1
+						  );
+				if( j*2+2 < iFill )
+					printf("    %d -- %d;\n",
+							j, j*2+2
+						  );
+			}
+			for( int j = 0; j < iFill; j++ )
+			{
+				printf("    %d [label=\"%d\"];\n",
+						j, aItem[j]
+					  );
+			}
+			printf("}\n");
+		}		
+
+	private:
+		int iSize;
+		int iFill;
+		item *aItem;
+		cmpfunc cmp;
+	};
+};
+
+#endif
-- 
cgit v1.2.3