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 
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
Base class for all Lucene classes.
Definition: LuceneObject.h:31
static int64_t unsignedShift(int64_t num, int64_t shift)
Perform unsigned right-shift (left bits are zero filled)
A PriorityQueue maintains a partial ordering of its elements such that the least element can always b...
Definition: PriorityQueue.h:20
int32_t size() const
Returns the number of elements currently stored in the PriorityQueue.
Definition: PriorityQueue.h:133
void clear()
Removes all entries from the PriorityQueue.
Definition: PriorityQueue.h:143
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
void downHeap()
Definition: PriorityQueue.h:163
PriorityQueue(int32_t maxSize)
Definition: PriorityQueue.h:24
bool empty() const
Returns whether PriorityQueue is currently empty.
Definition: PriorityQueue.h:138
int32_t maxSize()
Return maximum size of queue.
Definition: PriorityQueue.h:71
virtual ~PriorityQueue()
Definition: PriorityQueue.h:29
TYPE updateTop()
Should be called when the Object at top changes values.
Definition: PriorityQueue.h:127
int32_t _size
Definition: PriorityQueue.h:34
TYPE pop()
Removes and returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:114
std::vector< TYPE > heap_type
Definition: PriorityQueue.h:22
virtual void initialize()
Called directly after instantiation to create objects that depend on this object being fully construc...
Definition: PriorityQueue.h:38
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
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
void upHeap()
Definition: PriorityQueue.h:151
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
TYPE top()
Returns the least element of the PriorityQueue.
Definition: PriorityQueue.h:107
int32_t _maxSize
Definition: PriorityQueue.h:35
heap_type heap
Definition: PriorityQueue.h:33
Definition: AbstractAllTermDocs.h:12
ExceptionTemplate< RuntimeException, LuceneException::IndexOutOfBounds > IndexOutOfBoundsException
Definition: LuceneException.h:78

clucene.sourceforge.net