7 #ifndef PRIORITYQUEUE_H 8 #define PRIORITYQUEUE_H 19 template <
typename TYPE>
39 bool empty = heap.empty();
46 }
else if (_maxSize == INT_MAX) {
54 heapSize = _maxSize + 1;
56 this->heap.resize(heapSize);
61 if (empty && sentinel) {
63 for (int32_t i = 2; i < (int32_t)heap.size(); ++i) {
77 TYPE
add(
const TYPE& type) {
79 if (_size < 0 || _size >= (int32_t)heap.size()) {
93 if (_size < _maxSize) {
96 }
else if (_size > 0 && !
lessThan(type, heap[1])) {
97 TYPE result = heap[1];
116 TYPE result = heap[1];
117 heap[1] = heap[
_size];
118 heap[_size--] = TYPE();
144 for (int32_t i = 0; i <=
_size; ++i) {
155 while (j > 0 &&
lessThan(node, heap[j])) {
168 if (k <= _size &&
lessThan(heap[k], heap[j])) {
171 while (j <= _size &&
lessThan(heap[j], node)) {
176 if (k <= _size &&
lessThan(heap[k], heap[j])) {
184 virtual bool lessThan(
const TYPE& first,
const TYPE& second) {
185 return std::less<TYPE>()(first, second);
heap_type heap
Definition: PriorityQueue.h:33
virtual void initialize()
Called directly after instantiation to create objects that depend on this object being fully construc...
Definition: PriorityQueue.h:38
A PriorityQueue maintains a partial ordering of its elements such that the least element can always b...
Definition: PriorityQueue.h:20
static int64_t unsignedShift(int64_t num, int64_t shift)
Perform unsigned right-shift (left bits are zero filled)
int32_t maxSize()
Return maximum size of queue.
Definition: PriorityQueue.h:71
PriorityQueue(int32_t maxSize)
Definition: PriorityQueue.h:24
int32_t size() const
Returns the number of elements currently stored in the PriorityQueue.
Definition: PriorityQueue.h:133
bool empty() const
Returns whether PriorityQueue is currently empty.
Definition: PriorityQueue.h:138
virtual bool lessThan(const TYPE &first, const TYPE &second)
Determines the ordering of objects in this priority queue. Subclasses must define this one method...
Definition: PriorityQueue.h:184
std::vector< TYPE > heap_type
Definition: PriorityQueue.h:22
TYPE pop()
Removes and returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:114
void downHeap()
Definition: PriorityQueue.h:163
TYPE addOverflow(const TYPE &type)
Adds an Object to a PriorityQueue in log(size) time. It returns the object (if any) that was dropped ...
Definition: PriorityQueue.h:92
Base class for all Lucene classes.
Definition: LuceneObject.h:31
TYPE add(const TYPE &type)
Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize fr...
Definition: PriorityQueue.h:77
int32_t _size
Definition: PriorityQueue.h:34
Definition: AbstractAllTermDocs.h:12
virtual TYPE getSentinelObject()
This method can be overridden by extending classes to return a sentinel object which will be used by ...
Definition: PriorityQueue.h:194
int32_t _maxSize
Definition: PriorityQueue.h:35
void upHeap()
Definition: PriorityQueue.h:151
ExceptionTemplate< RuntimeException, LuceneException::IndexOutOfBounds > IndexOutOfBoundsException
Definition: LuceneException.h:74
TYPE top()
Returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:107
virtual ~PriorityQueue()
Definition: PriorityQueue.h:29
void clear()
Removes all entries from the PriorityQueue.
Definition: PriorityQueue.h:143
TYPE updateTop()
Should be called when the Object at top changes values.
Definition: PriorityQueue.h:127