Changed the Bu::Heap to allow iteration, and added lots of cool features to

Bu::MiniCron.

5 files changed, 433 insertions, 39 deletions

diff --git a/src/heap.h b/src/heap.h
index ca12a42..9df4121 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -18,6 +18,25 @@ namespace Bu
 {
         subExceptionDecl( HeapException );
 
+        /**
+         * A priority queue that allows for an unlimited number of priorities.  All
+         * objects enqueued must support less-than-comparison.  Then every time an
+         * item is dequeued it is always the least item in the heap.  The heap
+         * operates using a binary tree for storage, which allows most operations
+         * to be very fast.  Enqueueing and dequeueing are both O(log(N)) operatoins
+         * whereas peeking is constant time.
+         *
+         * This heap implementation allows iterating, however please note that any
+         * enqueue or dequeue operation will invalidate the iterator and make it
+         * unusable (if it still works, you shouldn't trust the results).  Also,
+         * the items are not stored in memory in order, they are optomized into a
+         * tree.  This means that the items will be in effectively random order
+         * while iterating through them, and the order cannot be trusted.  Also,
+         * modifying an item in the heap will not cause that item to be re-sorted.
+         * If you want to change the position of an item in the heap you will have
+         * to dequeue every item before it, dequeue that item, change it, and
+         * re-enqueue all of the items removed.
+         */
         template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
         class Heap : public Queue<item>
         {
@@ -165,29 +184,306 @@ namespace Bu
                         return iFill;
                 }
 
-                /*
-                void print( class Formatter &f )
+                class iterator
                 {
-                        f << "graph G {" << "\n";
-                        for( int j = 0; j < iFill; j++ )
+                        friend class const_iterator;
+                        friend class Heap<item, cmpfunc, itemalloc>;
+                private:
+                        Heap<item, cmpfunc, itemalloc> *pHeap;
+                        int iIndex;
+
+                        iterator( Heap<item, cmpfunc, itemalloc> *pHeap, int iIndex ) :
+                                pHeap( pHeap ), iIndex( iIndex )
                         {
-                                if( j*2+1 < iFill )
-                                        f << "    " << j << " -- " << j*2+1 << ";" << "\n";
-                                if( j*2+2 < iFill )
-                                        f << "    " << j << " -- " << j*2+2 << ";" << "\n";
                         }
-                        for( int j = 0; j < iFill; j++ )
+
+                        void checkValid()
+                        {
+                                if( pHeap == NULL )
+                                        throw Bu::ExceptionBase("Iterator not initialized.");
+                                if( iIndex < 0 || iIndex >= pHeap->iFill )
+                                        throw Bu::ExceptionBase("Iterator out of bounds.");
+                        }
+
+                public:
+                        iterator() :
+                                pHeap( NULL ),
+                                iIndex( -1 )
+                        {
+                        }
+
+                        iterator( const iterator &i ) :
+                                pHeap( i.pHeap ),
+                                iIndex( i.iIndex )
+                        {
+                        }
+
+                        bool operator==( const iterator &oth ) const
+                        {
+                                return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
+                        }
+
+                        bool operator!=( const iterator &oth ) const
+                        {
+                                return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
+                        }
+
+                        item &operator*()
+                        {
+                                return pHeap->aItem[iIndex];
+                        }
+
+                        item *operator->()
+                        {
+                                return &(pHeap->aItem[iIndex]);
+                        }
+
+                        iterator &operator++()
+                        {
+                                checkValid();
+                                iIndex++;
+                                if( iIndex >= pHeap->iFill )
+                                        iIndex = -1;
+
+                                return *this;
+                        }
+
+                        iterator &operator--()
+                        {
+                                checkValid();
+                                iIndex--;
+
+                                return *this;
+                        }
+                        
+                        iterator &operator++( int )
                         {
-                                f << "    " << j << " [label=\"" << aItem[j] << "\"];" << "\n";
+                                checkValid();
+                                iIndex++;
+                                if( iIndex >= pHeap->iFill )
+                                        iIndex = -1;
+
+                                return *this;
+                        }
+
+                        iterator &operator--( int )
+                        {
+                                checkValid();
+                                iIndex--;
+
+                                return *this;
+                        }
+
+                        iterator operator+( int iDelta )
+                        {
+                                checkValid();
+                                iterator ret( *this );
+                                ret.iIndex += iDelta;
+                                if( ret.iIndex >= pHeap->iFill )
+                                        ret.iIndex = -1;
+                                return ret;
+                        }
+
+                        iterator operator-( int iDelta )
+                        {
+                                checkValid();
+                                iterator ret( *this );
+                                ret.iIndex -= iDelta;
+                                if( ret.iIndex < 0 )
+                                        ret.iIndex = -1;
+                                return ret;
+                        }
+
+                        operator bool()
+                        {
+                                return iIndex != -1;
+                        }
+
+                        bool isValid()
+                        {
+                                return iIndex != -1;
+                        }
+
+                        iterator &operator=( const iterator &oth )
+                        {
+                                pHeap = oth.pHeap;
+                                iIndex = oth.iIndex;
+                        }
+                };
+                
+                class const_iterator
+                {
+                        friend class Heap<item, cmpfunc, itemalloc>;
+                private:
+                        Heap<item, cmpfunc, itemalloc> *pHeap;
+                        int iIndex;
+
+                        const_iterator( Heap<item, cmpfunc, itemalloc> *pHeap,
+                                        int iIndex ) :
+                                pHeap( pHeap ), iIndex( iIndex )
+                        {
+                        }
+
+                        void checkValid()
+                        {
+                                if( pHeap == NULL )
+                                        throw Bu::ExceptionBase("Iterator not initialized.");
+                                if( iIndex < 0 || iIndex >= pHeap->iFill )
+                                        throw Bu::ExceptionBase("Iterator out of bounds.");
                         }
-                        f << "}" << "\n";
-                } */
+
+                public:
+                        const_iterator() :
+                                pHeap( NULL ),
+                                iIndex( -1 )
+                        {
+                        }
+                        
+                        const_iterator( const const_iterator &i ) :
+                                pHeap( i.pHeap ),
+                                iIndex( i.iIndex )
+                        {
+                        }
+                        
+                        const_iterator( const iterator &i ) :
+                                pHeap( i.pHeap ),
+                                iIndex( i.iIndex )
+                        {
+                        }
+
+                        bool operator==( const const_iterator &oth ) const
+                        {
+                                return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
+                        }
+
+                        bool operator!=( const const_iterator &oth ) const
+                        {
+                                return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
+                        }
+
+                        const item &operator*()
+                        {
+                                return pHeap->aItem[iIndex];
+                        }
+
+                        const item *operator->()
+                        {
+                                return &(pHeap->aItem[iIndex]);
+                        }
+
+                        const_iterator &operator++()
+                        {
+                                checkValid();
+                                iIndex++;
+                                if( iIndex >= pHeap->iFill )
+                                        iIndex = -1;
+
+                                return *this;
+                        }
+
+                        const_iterator &operator--()
+                        {
+                                checkValid();
+                                iIndex--;
+
+                                return *this;
+                        }
+                        
+                        const_iterator &operator++( int )
+                        {
+                                checkValid();
+                                iIndex++;
+                                if( iIndex >= pHeap->iFill )
+                                        iIndex = -1;
+
+                                return *this;
+                        }
+
+                        const_iterator &operator--( int )
+                        {
+                                checkValid();
+                                iIndex--;
+
+                                return *this;
+                        }
+
+                        const_iterator operator+( int iDelta )
+                        {
+                                checkValid();
+                                const_iterator ret( *this );
+                                ret.iIndex += iDelta;
+                                if( ret.iIndex >= pHeap->iFill )
+                                        ret.iIndex = -1;
+                                return ret;
+                        }
+
+                        const_iterator operator-( int iDelta )
+                        {
+                                checkValid();
+                                const_iterator ret( *this );
+                                ret.iIndex -= iDelta;
+                                if( ret.iIndex < 0 )
+                                        ret.iIndex = -1;
+                                return ret;
+                        }
+
+                        operator bool()
+                        {
+                                return iIndex != -1;
+                        }
+
+                        bool isValid()
+                        {
+                                return iIndex != -1;
+                        }
+
+                        const_iterator &operator=( const const_iterator &oth )
+                        {
+                                pHeap = oth.pHeap;
+                                iIndex = oth.iIndex;
+                        }
+
+                        const_iterator &operator=( const iterator &oth )
+                        {
+                                pHeap = oth.pHeap;
+                                iIndex = oth.iIndex;
+                        }
+                };
+
+                iterator begin()
+                {
+                        if( iFill == 0 )
+                                return end();
+                        return iterator( this, 0 );
+                }
+
+                const_iterator begin() const
+                {
+                        if( iFill == 0 )
+                                return end();
+                        return const_iterator( this, 0 );
+                }
+
+                iterator end()
+                {
+                        return iterator( this, -1 );
+                }
+
+                const_iterator end() const
+                {
+                        return const_iterator( this, -1 );
+                }
+
 
         private:
                 void upSize()
                 {
                         item *aNewItems = ia.allocate( iSize*2+1 );
-//                      memcpy( aNewItems, aItem, sizeof(item)*iFill );
+                        //
+                        // We cannot use a memcopy here because we don't know what kind
+                        // of datastructures are being used, we have to copy them one at
+                        // a time.
+                        //
                         for( int j = 0; j < iFill; j++ )
                         {
                                 ia.construct( &aNewItems[j], aItem[j] );
diff --git a/src/minicron.cpp b/src/minicron.cpp
index 8aace26..491d143 100644
--- a/src/minicron.cpp
+++ b/src/minicron.cpp
@@ -35,6 +35,18 @@ time_t Bu::MiniCron::getNextRun()
         return -1;
 }
 
+time_t Bu::MiniCron::getNextRun( Bu::MiniCron::JobId jid )
+{
+        for( JobHeap::iterator i = hJobs.begin(); i; i++ )
+        {
+                if( (*i)->getId() == jid )
+                {
+                        return (*i)->getNextRunTime();
+                }
+        }
+        return -1;
+}
+
 void Bu::MiniCron::poll()
 {
         time_t tNow = time( NULL );
@@ -61,11 +73,11 @@ void Bu::MiniCron::poll()
         }
 }
 
-Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob,
-                const Bu::MiniCron::Timer &t )
+Bu::MiniCron::JobId Bu::MiniCron::addJob( const Bu::FString &sName,
+                Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t )
 {
         JobId jid = jidNext++;
-        Job *pJob = new Job( jid );
+        Job *pJob = new Job( sName, jid );
         pJob->sigJob = sigJob;
         pJob->pTimer = t.clone();
         pJob->tNextRun = pJob->pTimer->nextTime();
@@ -74,11 +86,11 @@ Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob,
         return jid;
 }
 
-Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( Bu::MiniCron::CronSignal sigJob,
-                const Bu::MiniCron::Timer &t )
+Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( const Bu::FString &sName,
+                Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t )
 {
         JobId jid = jidNext++;
-        Job *pJob = new Job( jid, false );
+        Job *pJob = new Job( sName, jid, false );
         pJob->sigJob = sigJob;
         pJob->pTimer = t.clone();
         pJob->tNextRun = pJob->pTimer->nextTime();
@@ -107,7 +119,21 @@ void Bu::MiniCron::removeJob( JobId jid )
         }
 }
 
-Bu::MiniCron::Job::Job( JobId jid, bool bRepeat ) :
+Bu::MiniCron::JobInfoList Bu::MiniCron::getJobInfo()
+{
+        JobInfoList lRet;
+        for( JobHeap::iterator i = hJobs.begin(); i; i++ )
+        {
+                lRet.append(
+                        JobInfo( (*i)->getName(), (*i)->getId(), (*i)->getNextRun() )
+                        );
+        }
+        lRet.sort();
+        return lRet;
+}
+
+Bu::MiniCron::Job::Job( const Bu::FString &sName, JobId jid, bool bRepeat ) :
+        sName( sName ),
         pTimer( NULL ),
         bContinue( bRepeat ),
         jid( jid ),
@@ -129,7 +155,7 @@ void Bu::MiniCron::Job::run()
         sigJob( *this );
 }
 
-time_t Bu::MiniCron::Job::getNextRun()
+time_t Bu::MiniCron::Job::getNextRun() const
 {
         return tNextRun;
 }
@@ -156,21 +182,48 @@ void Bu::MiniCron::Job::resume()
         bContinue = true;
 }
 
-Bu::MiniCron::JobId Bu::MiniCron::Job::getId()
+Bu::MiniCron::JobId Bu::MiniCron::Job::getId() const
 {
         return jid;
 }
 
-time_t Bu::MiniCron::Job::getTimeCreated()
+time_t Bu::MiniCron::Job::getTimeCreated() const
 {
         return tAdded;
 }
 
-int Bu::MiniCron::Job::getRunCount()
+int Bu::MiniCron::Job::getRunCount() const
 {
         return iRunCount;
 }
 
+time_t Bu::MiniCron::Job::getNextRunTime() const
+{
+        return tNextRun;
+}
+
+Bu::FString Bu::MiniCron::Job::getName() const
+{
+        return sName;
+}
+
+Bu::MiniCron::JobInfo::JobInfo( const Bu::FString &sName, JobId jid,
+                time_t tNext ) :
+        sName( sName ),
+        jid( jid ),
+        tNext( tNext )
+{
+}
+
+Bu::MiniCron::JobInfo::~JobInfo()
+{
+}
+
+bool Bu::MiniCron::JobInfo::operator<( const JobInfo &rhs ) const
+{
+        return jid < rhs.jid;
+}
+
 Bu::MiniCron::Timer::Timer()
 {
 }
diff --git a/src/minicron.h b/src/minicron.h
index 7475020..b045e79 100644
--- a/src/minicron.h
+++ b/src/minicron.h
@@ -66,6 +66,12 @@ namespace Bu
                  *@returns The timestamp that the next job will execute at.
                  */
                 virtual time_t getNextRun();
+                
+                /**
+                 * Tells you the time the job matching jid will run next.
+                 *@returns The timestamp that the job jid will next run.
+                 */
+                virtual time_t getNextRun( JobId jid );
 
                 /**
                  * Call this regularly to execute all jobs that should be executed.
@@ -83,7 +89,8 @@ namespace Bu
                  * JobId which can be used at a later time to control the execution of
                  * the job.
                  */
-                virtual JobId addJob( CronSignal sigJob, const Timer &t );
+                virtual JobId addJob( const Bu::FString &sName, CronSignal sigJob,
+                                const Timer &t );
 
                 /**
                  * Add a job for one time scheduling.  Pass in a slot to signal, and a
@@ -91,7 +98,8 @@ namespace Bu
                  * function returns a JobId which can be used at a later time to control
                  * the execution of the job.
                  */
-                virtual JobId addJobOnce( CronSignal sigJob, const Timer &t );
+                virtual JobId addJobOnce( const Bu::FString &sName, CronSignal sigJob,
+                                const Timer &t );
 
                 /**
                  * Remove a job, preventing all future runs of the job.  If there is no
@@ -102,6 +110,22 @@ namespace Bu
                  */
                 virtual void removeJob( JobId jid );
 
+                class JobInfo
+                {
+                public:
+                        JobInfo( const Bu::FString &sName, JobId jid, time_t tNext );
+                        virtual ~JobInfo();
+                        
+                        bool operator<( const JobInfo &rhs ) const;
+
+                        Bu::FString sName;
+                        JobId jid;
+                        time_t tNext;
+                };
+                typedef Bu::List<JobInfo> JobInfoList;
+
+                JobInfoList getJobInfo();
+
                 /**
                  * The baseclass for timer/schedulers for MiniCron jobs.  Classes that
                  * inherit from this are used to determine when jobs will run and at
@@ -201,7 +225,7 @@ namespace Bu
                 {
                         friend class Bu::MiniCron;
                 private:
-                        Job( JobId jid, bool bRepeat=true );
+                        Job( const Bu::FString &sName, JobId jid, bool bRepeat=true );
                         virtual ~Job();
 
                 public:
@@ -215,7 +239,7 @@ namespace Bu
                         /**
                          * Get the time this job will next run.
                          */
-                        time_t getNextRun();
+                        time_t getNextRun() const;
 
                         /**
                          * Compute the time this job will next run.
@@ -243,20 +267,33 @@ namespace Bu
                         /**
                          * Get the unique ID of this job.
                          */
-                        JobId getId();
+                        JobId getId() const;
 
                         /**
                          * Get the timestamp this job was created.
                          */
-                        time_t getTimeCreated();
+                        time_t getTimeCreated() const;
 
                         /**
                          * Get the current run count of this job, how many times it has been
                          * executed.  This is incremented before the slot is signaled.
                          */
-                        int getRunCount();
+                        int getRunCount() const;
+
+                        /**
+                         * Get the next time that this job will be run.  Certain timers may
+                         * have the ability to delay job executions, so this is the earliest
+                         * time that the job may run.
+                         */
+                        time_t getNextRunTime() const;
+
+                        /**
+                         * Gets the name that was set when the job was created.
+                         */
+                        Bu::FString getName() const;
 
                 private:
+                        Bu::FString sName;
                         CronSignal sigJob;
                         time_t tNextRun;
                         Timer *pTimer;
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index 6f68598..7538936 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -38,14 +38,19 @@ typedef struct num
         }
 } num;
 
-void printHeap( Bu::Heap<Bu::FString> &/*h*/, int j )
+void printHeap( Bu::Heap<Bu::FString> &h, int j )
 {
-        return;
+//      return;
         Bu::FString sFName;
         sFName.format("graph-step-%02d.dot", j );
         Bu::File fOut( sFName, Bu::File::WriteNew );
         Bu::Formatter f( fOut );
-//      h.print( f );
+        f << "Graph step: " << j << ", total size: " << h.getSize() << f.nl;
+        for( Bu::Heap<Bu::FString>::iterator i = h.begin(); i; i++ )
+        {
+                f << *i << f.nl;
+        }
+        f << f.nl;
 }
 
 int main()
diff --git a/src/tests/minicron.cpp b/src/tests/minicron.cpp
index 8abf8ad..0749f90 100644
--- a/src/tests/minicron.cpp
+++ b/src/tests/minicron.cpp
@@ -41,11 +41,14 @@ void job3( Bu::MiniCron::Job &job )
 
 int main()
 {
-
-        mCron.addJob( slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) );
-        mCron.addJob( slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) );
-        mCron.addJob( slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") );
-        mCron.addJob( slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) );
+        mCron.addJob(
+                "job0", slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) );
+        mCron.addJob(
+                "job1", slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) );
+        mCron.addJob(
+                "job2", slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") );
+        mCron.addJob(
+                "job3", slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) );
 
         sio << time( NULL ) << ": Program started." << sio.nl;