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

PriorityQueue.h
Go to the documentation of this file.
1 // Copyright (c) 2009-2014 Alan Wright. All rights reserved.
3 // Distributable under the terms of either the Apache License (Version 2.0)
4 // or the GNU Lesser General Public License.
6
7 #ifndef PRIORITYQUEUE_H
8 #define PRIORITYQUEUE_H
9
10 #include "LuceneObject.h"
11 #include "MiscUtils.h"
12
13 namespace Lucene {
14
19 template <typename TYPE>
20 class PriorityQueue : public LuceneObject {
21 public:
22 typedef typename std::vector<TYPE> heap_type;
23
24 PriorityQueue(int32_t maxSize) {
25 this->_size = 0;
26 this->_maxSize = maxSize;
27 }
28
29 virtual ~PriorityQueue() {
30 }
31
32 protected:
33 heap_type heap;
34 int32_t _size;
35 int32_t _maxSize;
36
37 public:
38 virtual void initialize() {
39 bool empty = heap.empty();
40
41 if (empty) {
42 int32_t heapSize = 0;
43 if (_maxSize == 0) {
44 // We allocate 1 extra to avoid if statement in top()
45 heapSize = 2;
46 } else if (_maxSize == INT_MAX) {
47 // Don't wrap heapSize to -1, in this case, which causes a confusing NegativeArraySizeException.
48 // Note that very likely this will simply then hit an OOME, but at least that's more indicative
49 // to caller that this values is too big. We don't +1 in this case, but it's very unlikely in
50 // practice one will actually insert this many objects into the PQ
51 heapSize = INT_MAX;
52 } else {
53 // NOTE: we add +1 because all access to heap is 1-based not 0-based. heap[0] is unused.
54 heapSize = _maxSize + 1;
55 }
56 this->heap.resize(heapSize);
57 }
58
59 // If sentinel objects are supported, populate the queue with them
60 TYPE sentinel = getSentinelObject();
61 if (empty && sentinel) {
62 heap[1] = sentinel;
63 for (int32_t i = 2; i < (int32_t)heap.size(); ++i) {
64 heap[i] = getSentinelObject();
65 }
66 _size = _maxSize;
67 }
68 }
69
71 int32_t maxSize() {
72 return _maxSize;
73 }
74
77 TYPE add(const TYPE& type) {
78 ++_size;
79 if (_size < 0 || _size >= (int32_t)heap.size()) {
80 boost::throw_exception(IndexOutOfBoundsException());
81 }
82 heap[_size] = type;
83 upHeap();
84 return heap[1];
85 }
86
92 TYPE addOverflow(const TYPE& type) {
93 if (_size < _maxSize) {
94 add(type);
95 return TYPE();
96 } else if (_size > 0 && !lessThan(type, heap[1])) {
97 TYPE result = heap[1];
98 heap[1] = type;
99 updateTop();
100 return result;
101 } else {
102 return type;
103 }
104 }
105
107 TYPE top() {
108 // We don't need to check size here: if maxSize is 0, then heap is length 2 array with both
109 // entries null. If size is 0 then heap[1] is already null.
110 return heap[1];
111 }
112
114 TYPE pop() {
115 if (_size > 0) {
116 TYPE result = heap[1]; // save first value
117 heap[1] = heap[_size]; // move last to first
118 heap[_size--] = TYPE();
119 downHeap(); // adjust heap
120 return result;
121 } else {
122 return TYPE();
123 }
124 }
125
127 TYPE updateTop() {
128 downHeap();
129 return heap[1];
130 }
131
133 int32_t size() const {
134 return _size;
135 }
136
138 bool empty() const {
139 return (_size == 0);
140 }
141
143 void clear() {
144 for (int32_t i = 0; i <= _size; ++i) {
145 heap[i] = TYPE();
146 }
147 _size = 0;
148 }
149
150 protected:
151 void upHeap() {
152 int32_t i = _size;
153 TYPE node = heap[i]; // save bottom node
154 int32_t j = MiscUtils::unsignedShift(i, 1);
155 while (j > 0 && lessThan(node, heap[j])) {
156 heap[i] = heap[j]; // shift parents down
157 i = j;
158 j = MiscUtils::unsignedShift(j, 1);
159 }
160 heap[i] = node; // install saved node
161 }
162
163 void downHeap() {
164 int32_t i = 1;
165 TYPE node = heap[i]; // save top node
166 int32_t j = i << 1; // find smaller child
167 int32_t k = j + 1;
168 if (k <= _size && lessThan(heap[k], heap[j])) {
169 j = k;
170 }
171 while (j <= _size && lessThan(heap[j], node)) {
172 heap[i] = heap[j]; // shift up child
173 i = j;
174 j = i << 1;
175 k = j + 1;
176 if (k <= _size && lessThan(heap[k], heap[j])) {
177 j = k;
178 }
179 }
180 heap[i] = node; // install saved node
181 }
182
184 virtual bool lessThan(const TYPE& first, const TYPE& second) {
185 return std::less<TYPE>()(first, second);
186 }
187
194 virtual TYPE getSentinelObject() {
195 return TYPE();
196 }
197 };
198
199 }
200
201 #endif
Lucene::PriorityQueue::updateTop
TYPE updateTop()
Should be called when the Object at top changes values.
Definition: PriorityQueue.h:127
Lucene::PriorityQueue::~PriorityQueue
virtual ~PriorityQueue()
Definition: PriorityQueue.h:29
Lucene::MiscUtils::unsignedShift
static int64_t unsignedShift(int64_t num, int64_t shift)
Perform unsigned right-shift (left bits are zero filled)
Lucene::PriorityQueue::size
int32_t size() const
Returns the number of elements currently stored in the PriorityQueue.
Definition: PriorityQueue.h:133
Lucene::PriorityQueue
A PriorityQueue maintains a partial ordering of its elements such that the least element can always b...
Definition: PriorityQueue.h:20
Lucene::PriorityQueue::initialize
virtual void initialize()
Called directly after instantiation to create objects that depend on this object being fully construc...
Definition: PriorityQueue.h:38
Lucene::PriorityQueue::getSentinelObject
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
Lucene::PriorityQueue::PriorityQueue
PriorityQueue(int32_t maxSize)
Definition: PriorityQueue.h:24
Lucene
Definition: AbstractAllTermDocs.h:12
Lucene::LuceneObject
Base class for all Lucene classes.
Definition: LuceneObject.h:31
Lucene::PriorityQueue::maxSize
int32_t maxSize()
Return maximum size of queue.
Definition: PriorityQueue.h:71
Lucene::PriorityQueue::_maxSize
int32_t _maxSize
Definition: PriorityQueue.h:35
Lucene::PriorityQueue::empty
bool empty() const
Returns whether PriorityQueue is currently empty.
Definition: PriorityQueue.h:138
Lucene::IndexOutOfBoundsException
ExceptionTemplate< RuntimeException, LuceneException::IndexOutOfBounds > IndexOutOfBoundsException
Definition: LuceneException.h:74
Lucene::PriorityQueue::heap_type
std::vector< TYPE > heap_type
Definition: PriorityQueue.h:22
Lucene::PriorityQueue::lessThan
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
Lucene::PriorityQueue::add
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
Lucene::PriorityQueue::pop
TYPE pop()
Removes and returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:114
Lucene::PriorityQueue::downHeap
void downHeap()
Definition: PriorityQueue.h:163
Lucene::PriorityQueue::clear
void clear()
Removes all entries from the PriorityQueue.
Definition: PriorityQueue.h:143
Lucene::PriorityQueue::addOverflow
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
Lucene::PriorityQueue::top
TYPE top()
Returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:107
MiscUtils.h
Lucene::PriorityQueue::_size
int32_t _size
Definition: PriorityQueue.h:34
Lucene::PriorityQueue::heap
heap_type heap
Definition: PriorityQueue.h:33
Lucene::PriorityQueue::upHeap
void upHeap()
Definition: PriorityQueue.h:151
LuceneObject.h

clucene.sourceforge.net