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
include
PriorityQueue.h
Go to the documentation of this file.
1
2
// 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
clucene.sourceforge.net