Oops. I made the Bu::Heap API look like a stack, not a queue, that's been

fixed, and the Bu::ItoHeap is working and tested.  Note that when multiple items
have the same sort order, they will come out in random order.

5 files changed, 287 insertions, 21 deletions

diff --git a/src/heap.h b/src/heap.h
index f276157..dd2764f 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -24,7 +24,7 @@ namespace Bu
         {
                 bool operator()( const item &a, const item &b )
                 {
-                        return a <= b;
+                        return a < b;
                 }
         };
         
@@ -33,7 +33,7 @@ namespace Bu
         {
                 bool operator()( const item &a, const item &b )
                 {
-                        return a >= b;
+                        return a > b;
                 }
         };
 
@@ -42,7 +42,7 @@ namespace Bu
         {
                 bool operator()( const item &a, const item &b )
                 {
-                        return *a <= *b;
+                        return *a < *b;
                 }
         };
         
@@ -51,7 +51,7 @@ namespace Bu
         {
                 bool operator()( const item &a, const item &b )
                 {
-                        return *a >= *b;
+                        return *a > *b;
                 }
         };
 
@@ -74,7 +74,7 @@ namespace Bu
                         aItem = NULL;
                 }
 
-                void push( item i )
+                void enqueue( item i )
                 {
                         if( iFill+1 >= iSize )
                                 upSize();
@@ -96,14 +96,17 @@ namespace Bu
                                 }
                         }
                         ia.construct( &aItem[iFill], i );
-                        for( int j = iFill; j >= 0; )
+                        if( iFill > 0 )
                         {
-                                int k = (j-1)/2;
-                                if( cmp( aItem[k], aItem[j] ) )
-                                        break;
+                                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;
+                                        swap( aItem[k], aItem[j] );
+                                        j = k;
+                                }
                         }
                         iFill++;
                 }
@@ -115,10 +118,11 @@ namespace Bu
                         return aItem[0];
                 }
 
-                void pop()
+                item dequeue()
                 {
                         if( iFill == 0 )
                                 throw HeapException("Heap empty.");
+                        item iRet = aItem[0];
                         int j;
                         for( j = 0; j < iFill; )
                         {
@@ -138,6 +142,18 @@ namespace Bu
                         aItem[j] = aItem[iFill-1];
                         ia.destroy( &aItem[iFill-1] );
                         iFill--;
+
+                        return iRet;
+                }
+
+                bool isEmpty()
+                {
+                        return (iFill==0);
+                }
+
+                int getSize()
+                {
+                        return iFill;
                 }
 
                 void print()
diff --git a/src/itoheap.cpp b/src/itoheap.cpp
index e69de29..f4582bc 100644
--- a/src/itoheap.cpp
+++ b/src/itoheap.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 "bu/itoheap.h"
+
diff --git a/src/itoheap.h b/src/itoheap.h
index e69de29..59a8158 100644
--- a/src/itoheap.h
+++ b/src/itoheap.h
@@ -0,0 +1,154 @@
+/*
+ * 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_ITO_HEAP_H
+#define BU_ITO_HEAP_H
+
+#include "bu/heap.h"
+#include "bu/itomutex.h"
+#include "bu/itocondition.h"
+
+namespace Bu
+{
+        class ItoMutex;
+        class ItoCondition;
+
+        template<typename item, typename cmpfunc=__basicLTCmp<item>,
+                typename itemalloc=std::allocator<item> >
+        class ItoHeap
+        {
+        public:
+                ItoHeap()
+                {
+                }
+
+                virtual ~ItoHeap()
+                {
+                }
+
+                void enqueue( item i )
+                {
+                        imData.lock();
+                        hData.enqueue( i );
+                        icBlock.signal();
+                        imData.unlock();
+                }
+
+                item dequeue( bool bBlock=false )
+                {
+                        imData.lock();
+                        if( hData.isEmpty() )
+                        {
+                                imData.unlock();
+
+                                if( bBlock )
+                                {
+                                        icBlock.lock();
+
+                                        while( hData.isEmpty() )
+                                                icBlock.wait();
+
+                                        imData.lock();
+                                        try
+                                        {
+                                                item iRet = hData.dequeue();
+                                                imData.unlock();
+                                                icBlock.unlock();
+                                                return iRet;
+                                        }
+                                        catch(...)
+                                        {
+                                                imData.unlock();
+                                                icBlock.unlock();
+                                                throw;
+                                        }
+                                }
+                                throw HeapException("Heap empty.");
+                        }
+                        else
+                        {
+                                try
+                                {
+                                        item iRet = hData.dequeue();
+                                        imData.unlock();
+                                        return iRet;
+                                }
+                                catch(...)
+                                {
+                                        imData.unlock();
+                                        throw;
+                                }
+                        }
+                }
+
+                item dequeue( int iSec, int iUSec )
+                {
+                        imData.lock();
+                        if( hData.isEmpty() )
+                        {
+                                imData.unlock();
+
+                                icBlock.lock();
+
+                                icBlock.wait( iSec, iUSec );
+
+                                imData.lock();
+                                try
+                                {
+                                        item iRet = hData.dequeue();
+                                        imData.unlock();
+                                        icBlock.unlock();
+                                        return iRet;
+                                }
+                                catch(...)
+                                {
+                                        imData.unlock();
+                                        icBlock.unlock();
+                                        throw;
+                                }
+                        }
+                        else
+                        {
+                                try
+                                {
+                                        item iRet = hData.dequeue();
+                                        imData.unlock();
+                                        return iRet;
+                                }
+                                catch(...)
+                                {
+                                        imData.unlock();
+                                        throw;
+                                }
+                        }
+                }
+                
+                bool isEmpty()
+                {
+                        imData.lock();
+                        bool bRet = hData.isEmpty();
+                        imData.unlock();
+                        return bRet;
+                }
+
+                int getSize()
+                {
+                        imData.lock();
+                        int iRet = hData.getSize();
+                        imData.unlock();
+                        return iRet;
+                }
+
+        private:
+                Heap< item, cmpfunc, itemalloc > hData;
+                ItoMutex imData;
+                ItoCondition icBlock;
+        };
+};
+
+#endif
+
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index 3217715..e35ea2a 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -3,26 +3,49 @@
 
 #include "bu/heap.h"
 
+typedef struct num
+{
+        num( int iNum, int iOrder ) : iNum( iNum ), iOrder( iOrder )
+        {
+        }
+
+        num( const num &src ) : iNum( src.iNum ), iOrder( src.iOrder )
+        {
+        }
+
+        int iNum;
+        int iOrder;
+
+        bool operator<( const num &oth ) const
+        {
+                if( iNum == oth.iNum )
+                        return iOrder < oth.iOrder;
+                return iNum < oth.iNum;
+        }
+        bool operator>( const num &oth ) const
+        {
+                return iNum > oth.iNum;
+        }
+} num;
+
 int main()
 {
-        Bu::Heap<int, Bu::__basicGTCmp<int> > hInt;
+        Bu::Heap<num> hNum;
 
-        for( int j = 0; j < 15; j++ )
+        for( int j = 0; j < 30; j++ )
         {
                 int r = rand()%10;
                 printf("Pushing: %d, top: ", r );
-                hInt.push( r );
-                printf("%d\n", hInt.peek() );
+                hNum.enqueue( num( r, j ) );
+                printf("%d\n", hNum.peek().iNum );
         }
 
-        for( int j = 0; j < 15; j++ )
+        while( !hNum.isEmpty() )
         {
-                printf("%d ", hInt.peek() );
-                hInt.pop();
+                printf("(%d:%d) ", hNum.peek().iOrder, hNum.peek().iNum );
+                hNum.dequeue();
         }
         printf("\n");
-        
-//      hInt.print();
 
         return 0;
 }
diff --git a/src/tests/itoheap.cpp b/src/tests/itoheap.cpp
new file mode 100644
index 0000000..67169e7
--- /dev/null
+++ b/src/tests/itoheap.cpp
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bu/itoheap.h"
+#include "bu/ito.h"
+
+class Consumer : public Bu::Ito
+{
+public:
+        Consumer()
+        {
+        }
+
+        virtual ~Consumer()
+        {
+        }
+
+        void *run()
+        {
+                for( int j = 0; j < 10; j++ )
+                {
+                        printf("Trying to read [%d].\n", j );
+
+                        try
+                        {
+                                int iNum = hInt.dequeue( 0, 500000 );
+                                printf("Read %d\n", iNum );
+                        }
+                        catch( Bu::HeapException &e )
+                        {
+                                printf("Nothing yet...\n");
+                        }
+                }
+
+                return NULL;
+        }
+
+        Bu::ItoHeap<int> hInt;
+};
+
+
+int main()
+{
+        Consumer c;
+
+        for( int j = 0; j < 3; j++ )
+        {
+                int iNum = rand()%10;
+                printf("Enqueuing %d.\n", iNum );
+                c.hInt.enqueue( iNum );
+        }
+
+        printf("Sarting consumer.\n");
+        c.start();
+
+        for( int j = 0; j < 5; j++ )
+        {
+                sleep( 1 );
+                int iNum = rand()%10;
+                printf("Enqueuing %d.\n", iNum );
+                c.hInt.enqueue( iNum );
+        }
+}
+