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

- Main Page
- Related Pages
- Namespaces
- Data Structures
- Files

- File List
- Globals

All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
PriorityQueue.h
Go to the documentation of this file.
1 // Copyright (c) 2009-2011 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 {
22 public:
23 typedef typename std::vector< TYPE, LuceneAllocator<TYPE> > heap_type;
24
25 PriorityQueue(int32_t maxSize)
26 {
27 this->_size = 0;
28 this->_maxSize = maxSize;
29 }
30
31 virtual ~PriorityQueue()
32 {
33 }
34
35 protected:
36 heap_type heap;
37 int32_t _size;
38 int32_t _maxSize;
39
40 public:
41 virtual void initialize()
42 {
43 bool empty = heap.empty();
44
45 if (empty)
46 {
47 int32_t heapSize = 0;
48 if (_maxSize == 0)
49 {
50 // We allocate 1 extra to avoid if statement in top()
51 heapSize = 2;
52 }
53 else if (_maxSize == INT_MAX)
54 {
55 // Don't wrap heapSize to -1, in this case, which causes a confusing NegativeArraySizeException.
56 // Note that very likely this will simply then hit an OOME, but at least that's more indicative
57 // to caller that this values is too big. We don't +1 in this case, but it's very unlikely in
58 // practice one will actually insert this many objects into the PQ
59 heapSize = INT_MAX;
60 }
61 else
62 {
63 // NOTE: we add +1 because all access to heap is 1-based not 0-based. heap[0] is unused.
64 heapSize = _maxSize + 1;
65 }
66 this->heap.resize(heapSize);
67 }
68
69 // If sentinel objects are supported, populate the queue with them
70 TYPE sentinel = getSentinelObject();
71 if (empty && sentinel)
72 {
73 heap[1] = sentinel;
74 for (int32_t i = 2; i < (int32_t)heap.size(); ++i)
75 heap[i] = getSentinelObject();
76 _size = _maxSize;
77 }
78 }
79
81 int32_t maxSize()
82 {
83 return _maxSize;
84 }
85
88 TYPE add(const TYPE& type)
89 {
90 ++_size;
91 if (_size < 0 || _size >= (int32_t)heap.size())
92 boost::throw_exception(IndexOutOfBoundsException());
93 heap[_size] = type;
94 upHeap();
95 return heap[1];
96 }
97
103 TYPE addOverflow(const TYPE& type)
104 {
105 if (_size < _maxSize)
106 {
107 add(type);
108 return TYPE();
109 }
110 else if (_size > 0 && !lessThan(type, heap[1]))
111 {
112 TYPE result = heap[1];
113 heap[1] = type;
114 updateTop();
115 return result;
116 }
117 else
118 return type;
119 }
120
122 TYPE top()
123 {
124 // We don't need to check size here: if maxSize is 0, then heap is length 2 array with both
125 // entries null. If size is 0 then heap[1] is already null.
126 return heap[1];
127 }
128
130 TYPE pop()
131 {
132 if (_size > 0)
133 {
134 TYPE result = heap[1]; // save first value
135 heap[1] = heap[_size]; // move last to first
136 heap[_size--] = TYPE();
137 downHeap(); // adjust heap
138 return result;
139 }
140 else
141 return TYPE();
142 }
143
145 TYPE updateTop()
146 {
147 downHeap();
148 return heap[1];
149 }
150
152 int32_t size() const
153 {
154 return _size;
155 }
156
158 bool empty() const
159 {
160 return (_size == 0);
161 }
162
164 void clear()
165 {
166 for (int32_t i = 0; i <= _size; ++i)
167 heap[i] = TYPE();
168 _size = 0;
169 }
170
171 protected:
172 void upHeap()
173 {
174 int32_t i = _size;
175 TYPE node = heap[i]; // save bottom node
176 int32_t j = MiscUtils::unsignedShift(i, 1);
177 while (j > 0 && lessThan(node, heap[j]))
178 {
179 heap[i] = heap[j]; // shift parents down
180 i = j;
181 j = MiscUtils::unsignedShift(j, 1);
182 }
183 heap[i] = node; // install saved node
184 }
185
186 void downHeap()
187 {
188 int32_t i = 1;
189 TYPE node = heap[i]; // save top node
190 int32_t j = i << 1; // find smaller child
191 int32_t k = j + 1;
192 if (k <= _size && lessThan(heap[k], heap[j]))
193 j = k;
194 while (j <= _size && lessThan(heap[j], node))
195 {
196 heap[i] = heap[j]; // shift up child
197 i = j;
198 j = i << 1;
199 k = j + 1;
200 if (k <= _size && lessThan(heap[k], heap[j]))
201 j = k;
202 }
203 heap[i] = node; // install saved node
204 }
205
207 virtual bool lessThan(const TYPE& first, const TYPE& second)
208 {
209 return std::less<TYPE>()(first, second);
210 }
211
218 virtual TYPE getSentinelObject()
219 {
220 return TYPE();
221 }
222 };
223 }
224
225 #endif

clucene.sourceforge.net