priority_queue.h

Go to the documentation of this file.

// Copyright (C) 2005-2008 Washington University in St Louis, Baylor College of Medicine.  All rights reserved
// Author:        Tao Ju (taoju@cse.wustl.edu)
// Description:   A Priority queue implementation
 
#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H
 
#include <cstdlib>
#include <cstdio>
 
namespace EMAN {
 
template < class ValueT, class KeyT >
class PriorityQueue
{
public:
        int queueLength ;
 
        int maxLength ;
 
        ValueT ** valueQueue ;
 
        KeyT * keyQueue ;
 
public:
        
        PriorityQueue ( int max )
        {
                this->maxLength = max ;
                this->queueLength = 0 ;
                this->valueQueue = new ValueT* [ max ] ;
                this->keyQueue = new KeyT [ max ] ;
 
        };
 
        ~PriorityQueue ()
        {
                delete [] keyQueue ;
                for ( int i = 0 ; i < queueLength ; i ++ )
                {
                        delete valueQueue [ i ] ;
                }
                delete [] valueQueue ;
        };
 
        int getLength ( )
        {
                return this->queueLength ;
        };
 
        bool isEmpty ( )
        {
                return ( this->queueLength == 0 ) ;
        };
 
        bool isFull ( )
        {
                return ( this->queueLength == this->maxLength  ) ;
        };
 
        void add ( ValueT * v, KeyT k )
        {
                if ( this->isFull() )
                {
                        printf("PRIORITY QUEUE FILLED UP !!! \n");
                        return ;
                }
 
                int ind = queueLength ;
                int tind ;
                queueLength ++ ;
 
                while ( ind > 0 )
                {
                        tind = ( ind + 1 ) / 2 - 1 ;
                        if ( k < keyQueue[tind] )
                        {
                                keyQueue[ ind ] = keyQueue [ tind ] ;
                                valueQueue [ ind ] = valueQueue [ tind ] ;
                                ind = tind ;
                        }
                        else
                        {
                                break;
                        }
                }
 
                valueQueue[ ind ] = v ;
                keyQueue [ ind ] = k ;
        };
 
        void remove ( ValueT *& v, KeyT & k )
        {
                if ( this->isEmpty() )
                {
                        v = NULL ;
                        k = 0 ;
                        return ;
                }
 
                v = valueQueue[0] ;
                k = keyQueue[0] ;
                queueLength -- ;
 
                if ( queueLength == 0 )
                {
                        valueQueue[0] = NULL ;
                        return ;
                }
 
                ValueT * vv = valueQueue [ queueLength ] ;
                KeyT kk = keyQueue [ queueLength ], lowk ;
                int ind = 0, tind, ind2, ind3 ;
                while ( 1 )
                {
                        ind2 = 2 * ( ind + 1 ) - 1 ;
                        ind3 = ind2 + 1 ;
                        tind = ind ; 
                        lowk = kk ;
 
                        if ( ind2 >= queueLength )
                        {
                                break ;
                        }
                        else 
                        {
                                if ( keyQueue [ ind2 ] < lowk )
                                {
                                        tind = ind2 ;
                                        lowk = keyQueue [ ind2 ] ;
                                }
 
                                if ( ind3 < queueLength )
                                {
                                        if ( keyQueue [ ind3 ] < lowk )
                                        {
                                                tind = ind3 ;
                                        }
                                }
 
                                if ( ind != tind )
                                {
                                        valueQueue [ ind ] = valueQueue [ tind ] ;
                                        keyQueue [ ind ] = keyQueue [ tind ] ;
                                        ind = tind ;
                                }
                                else
                                {
                                        break ;
                                }
                        }
                }
 
                valueQueue [ ind ] = vv ;
                keyQueue [ ind ] = kk ;
                valueQueue [ queueLength ] = NULL ;
                keyQueue [ queueLength ] = NULL ;
        };
 
};
 
 
}
 
#endif