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
// 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