Hey, fixed the problems in heap. It should now work properly no matter what the

data or order etc.

4 files changed, 62 insertions, 20 deletions

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 )