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_

CL_NS_DEF(util)


template <class _type,typename _valueDeletor> class PriorityQueue:LUCENE_BASE {
        private:
                size_t _size;
                bool dk;
                size_t maxSize;
        protected:
                _type* heap; //(was object[])

        private:
                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;
                        if (0 == maxSize)
                                // We allocate 1 extra to avoid if statement in top()
                                heapSize = 2;
                        else
                                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){
                  _type t = insertWithOverflow(element);
                  if (t != element) {
                          if (t) _valueDeletor::doDelete(t);
                          return true;
                  }
                  return false;
          }

          _type insertWithOverflow(_type element) {
                  if(_size < maxSize){
                          put(element);
                          return NULL;
                  }else if(_size > 0 && !lessThan(element, heap[1])){
                          _type ret = heap[1];
                          heap[1] = element;
                          adjustTop();
                          return ret;
                  }else
                          return element;
          }

          _type top(){
                  // We don't need to check size here: if maxSize is 0,
                  // then heap is length 2 array with both entries null.
                  // If size is 0 then heap[1] is already null.
                  return heap[1];
          }

                _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