CLucene - a full-featured, c++ search engine
API Documentation

---

PriorityQueue.h

Go to the documentation of this file.

/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
* 
* Distributable under the terms of either the Apache License (Version 2.0) or 
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_util_PriorityQueue_
#define _lucene_util_PriorityQueue_

#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
CL_NS_DEF(util)

// A PriorityQueue maintains a partial ordering of its elements such that the
// least element can always be found in constant time.  Put()'s and pop()'s
//  require log(size) time. 
template <class _type,typename _valueDeletor> class PriorityQueue:LUCENE_BASE {
        private:
                _type* heap; //(was object[])
                size_t _size;
                bool dk;
                size_t maxSize;

                void upHeap(){
                        size_t i = _size;
                        _type node = heap[i];                     // save bottom node (WAS object)
                        int32_t j = ((uint32_t)i) >> 1;
                        while (j > 0 && lessThan(node,heap[j])) {
                                heap[i] = heap[j];                        // shift parents down
                                i = j;
                                j = ((uint32_t)j) >> 1;
                        }
                        heap[i] = node;                           // install saved node
                }
                void downHeap(){
                        size_t i = 1;
                        _type node = heap[i];                     // save top node
                        size_t j = i << 1;                                // find smaller child
                        size_t k = j + 1;
                        if (k <= _size && lessThan(heap[k], heap[j])) {
                                j = k;
                        }
                        while (j <= _size && lessThan(heap[j],node)) {
                                heap[i] = heap[j];                        // shift up child
                                i = j;
                                j = i << 1;
                                k = j + 1;
                                if (k <= _size && lessThan(heap[k], heap[j])) {
                                        j = k;
                                }
                        }
                        heap[i] = node;                           // install saved node
                }

        protected:
                PriorityQueue(){
                        this->_size = 0;
                        this->dk = false;
                        this->heap = NULL;
            this->maxSize = 0;
                }

                // Determines the ordering of objects in this priority queue.  Subclasses
                //      must define this one method. 
                virtual bool lessThan(_type a, _type b)=0;

                // Subclass constructors must call this. 
                void initialize(const int32_t maxSize, bool deleteOnClear){
                        _size = 0;
                        dk = deleteOnClear;
                        int32_t heapSize = maxSize + 1;
                        heap = _CL_NEWARRAY(_type,heapSize);
            this->maxSize = maxSize;
                }

        public:
                virtual ~PriorityQueue(){
                        clear();
                        _CLDELETE_ARRAY(heap);
                }

      void put(_type element){
                if ( _size>=maxSize )
                                _CLTHROWA(CL_ERR_IndexOutOfBounds,"add is out of bounds");

                        ++_size;        
                        heap[_size] = element;          
                        upHeap();
                }

      bool insert(_type element){
         if(_size < maxSize){
            put(element);
            return true;
        }else if(_size > 0 && !lessThan(element, top())){
                        if ( dk ){
                                _valueDeletor::doDelete(heap[1]);
                        }
            heap[1] = element;
            adjustTop();
            return true;
         }else
            return false;
      }

                _type top(){
                        if (_size > 0)
                                return heap[1];
                        else
                                return NULL;
                }

                _type pop(){
                        if (_size > 0) {
                                _type result = heap[1];                   // save first value
                                heap[1] = heap[_size];                    // move last to first

                                heap[_size] = (_type)0;                   // permit GC of objects
                                --_size;
                                downHeap();                               // adjust heap
                                return result;
                        } else
                                return (_type)NULL;
                }

                void adjustTop(){
                        downHeap();
                }
                    

                size_t size(){
                        return _size;
                }
                  
                void clear(){
                        for (size_t i = 1; i <= _size; ++i){
                                if ( dk ){
                                        _valueDeletor::doDelete(heap[i]);
                                }
                        }
                        _size = 0;
                }
        };

CL_NS_END
#endif

---

clucene.sourceforge.net