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


 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 
26  {
27  this->_size = 0;
28  this->_maxSize = maxSize;
29  }
30 
31  virtual ~PriorityQueue()
32  {
33  }
34 
35  protected:
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