| /*------------------------------------------------------------------------------ |
| * 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); |
| } |
| |
| /** |
| * Adds an Object to a PriorityQueue in log(size) time. |
| * If one tries to add more objects than maxSize from initialize |
| * a RuntimeException (ArrayIndexOutOfBound) is thrown. |
| */ |
| void put(_type element){ |
| if ( _size>=maxSize ) |
| _CLTHROWA(CL_ERR_IndexOutOfBounds,"add is out of bounds"); |
| |
| ++_size; |
| heap[_size] = element; |
| upHeap(); |
| } |
| |
| /** |
| * Adds element to the PriorityQueue in log(size) time if either |
| * the PriorityQueue is not full, or not lessThan(element, top()). |
| * @param element |
| * @return true if element is added, false otherwise. |
| */ |
| 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; |
| } |
| |
| /** |
| * Returns the least element of the PriorityQueue in constant time. |
| */ |
| _type top(){ |
| if (_size > 0) |
| return heap[1]; |
| else |
| return NULL; |
| } |
| |
| /** Removes and returns the least element of the PriorityQueue in log(size) |
| * time. |
| */ |
| _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; |
| } |
| |
| /**Should be called when the object at top changes values. Still log(n) |
| worst case, but it's at least twice as fast to <pre> |
| { pq.top().change(); pq.adjustTop(); } |
| </pre> instead of <pre> |
| { o = pq.pop(); o.change(); pq.push(o); } |
| </pre> |
| */ |
| void adjustTop(){ |
| downHeap(); |
| } |
| |
| |
| /** |
| * Returns the number of elements currently stored in the PriorityQueue. |
| */ |
| size_t size(){ |
| return _size; |
| } |
| |
| /** |
| * Removes all entries from the PriorityQueue. |
| */ |
| void clear(){ |
| for (size_t i = 1; i <= _size; ++i){ |
| if ( dk ){ |
| _valueDeletor::doDelete(heap[i]); |
| } |
| } |
| _size = 0; |
| } |
| }; |
| |
| CL_NS_END |
| #endif |