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.

6 files changed, 212 insertions, 0 deletions

diff --git a/src/heap.cpp b/src/heap.cpp
new file mode 100644
index 0000000..00a5d5d
--- /dev/null
+++ b/src/heap.cpp
@@ -0,0 +1,9 @@
+/*
+ * 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.
+ */
+
+#include "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
diff --git a/src/itoheap.cpp b/src/itoheap.cpp
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/itoheap.cpp
diff --git a/src/itoheap.h b/src/itoheap.h
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/itoheap.h
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
new file mode 100644
index 0000000..e93749f
--- /dev/null
+++ b/src/tests/heap.cpp
@@ -0,0 +1,29 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "bu/heap.h"
+
+int main()
+{
+        Bu::Heap<int> hInt;
+
+        for( int j = 0; j < 15; j++ )
+        {
+                int r = rand()%10;
+                printf("Pushing: %d, top: ", r );
+                hInt.push( r );
+                printf("%d\n", hInt.peek() );
+        }
+
+        for( int j = 0; j < 15; j++ )
+        {
+                printf("%d ", hInt.peek() );
+                hInt.pop();
+        }
+        printf("\n");
+        
+//      hInt.print();
+
+        return 0;
+}
+
diff --git a/src/util.h b/src/util.h
new file mode 100644
index 0000000..977645c
--- /dev/null
+++ b/src/util.h
@@ -0,0 +1,40 @@
+/*
+ * 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_UTIL_H
+#define BU_UTIL_H
+
+namespace Bu
+{
+        template<typename item>
+        void swap( item &a, item &b )
+        {
+                item tmp = a;
+                a = b;
+                b = tmp;
+        }
+
+        template<typename item>
+        item &min( item &a, item &b )
+        {
+                return a<b?a:b;
+        }
+        
+        template<typename item>
+        item &max( item &a, item &b )
+        {
+                return a>b?a:b;
+        }
+        
+        template<typename item>
+        item &mid( item &a, item &b, item &c )
+        {
+                return min( max( a, b ), c );
+        }
+};
+
+#endif