diff options
Diffstat (limited to '3rdparty/clucene/src/CLucene/util/PriorityQueue.h')
-rw-r--r-- | 3rdparty/clucene/src/CLucene/util/PriorityQueue.h | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/3rdparty/clucene/src/CLucene/util/PriorityQueue.h b/3rdparty/clucene/src/CLucene/util/PriorityQueue.h new file mode 100644 index 000000000..45649ee7f --- /dev/null +++ b/3rdparty/clucene/src/CLucene/util/PriorityQueue.h @@ -0,0 +1,177 @@ +/*------------------------------------------------------------------------------ +* 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 |