1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
*
* Distributable under the terms of either the Apache License (Version 2.0) or
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_util_PriorityQueue_
#define _lucene_util_PriorityQueue_
#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
CL_NS_DEF(util)
// A PriorityQueue maintains a partial ordering of its elements such that the
// least element can always be found in constant time. Put()'s and pop()'s
// require log(size) time.
template <class _type,typename _valueDeletor> class PriorityQueue:LUCENE_BASE {
private:
_type* heap; //(was object[])
size_t _size;
bool dk;
size_t maxSize;
void upHeap(){
size_t i = _size;
_type node = heap[i]; // save bottom node (WAS object)
int32_t j = ((uint32_t)i) >> 1;
while (j > 0 && lessThan(node,heap[j])) {
heap[i] = heap[j]; // shift parents down
i = j;
j = ((uint32_t)j) >> 1;
}
heap[i] = node; // install saved node
}
void downHeap(){
size_t i = 1;
_type node = heap[i]; // save top node
size_t j = i << 1; // find smaller child
size_t k = j + 1;
if (k <= _size && lessThan(heap[k], heap[j])) {
j = k;
}
while (j <= _size && lessThan(heap[j],node)) {
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
if (k <= _size && lessThan(heap[k], heap[j])) {
j = k;
}
}
heap[i] = node; // install saved node
}
protected:
PriorityQueue(){
this->_size = 0;
this->dk = false;
this->heap = NULL;
this->maxSize = 0;
}
// Determines the ordering of objects in this priority queue. Subclasses
// must define this one method.
virtual bool lessThan(_type a, _type b)=0;
// Subclass constructors must call this.
void initialize(const int32_t maxSize, bool deleteOnClear){
_size = 0;
dk = deleteOnClear;
int32_t heapSize = maxSize + 1;
heap = _CL_NEWARRAY(_type,heapSize);
this->maxSize = maxSize;
}
public:
virtual ~PriorityQueue(){
clear();
_CLDELETE_ARRAY(heap);
}
/**
* Adds an Object to a PriorityQueue in log(size) time.
* If one tries to add more objects than maxSize from initialize
* a RuntimeException (ArrayIndexOutOfBound) is thrown.
*/
void put(_type element){
if ( _size>=maxSize )
_CLTHROWA(CL_ERR_IndexOutOfBounds,"add is out of bounds");
++_size;
heap[_size] = element;
upHeap();
}
/**
* Adds element to the PriorityQueue in log(size) time if either
* the PriorityQueue is not full, or not lessThan(element, top()).
* @param element
* @return true if element is added, false otherwise.
*/
bool insert(_type element){
if(_size < maxSize){
put(element);
return true;
}else if(_size > 0 && !lessThan(element, top())){
if ( dk ){
_valueDeletor::doDelete(heap[1]);
}
heap[1] = element;
adjustTop();
return true;
}else
return false;
}
/**
* Returns the least element of the PriorityQueue in constant time.
*/
_type top(){
if (_size > 0)
return heap[1];
else
return NULL;
}
/** Removes and returns the least element of the PriorityQueue in log(size)
* time.
*/
_type pop(){
if (_size > 0) {
_type result = heap[1]; // save first value
heap[1] = heap[_size]; // move last to first
heap[_size] = (_type)0; // permit GC of objects
--_size;
downHeap(); // adjust heap
return result;
} else
return (_type)NULL;
}
/**Should be called when the object at top changes values. Still log(n)
worst case, but it's at least twice as fast to <pre>
{ pq.top().change(); pq.adjustTop(); }
</pre> instead of <pre>
{ o = pq.pop(); o.change(); pq.push(o); }
</pre>
*/
void adjustTop(){
downHeap();
}
/**
* Returns the number of elements currently stored in the PriorityQueue.
*/
size_t size(){
return _size;
}
/**
* Removes all entries from the PriorityQueue.
*/
void clear(){
for (size_t i = 1; i <= _size; ++i){
if ( dk ){
_valueDeletor::doDelete(heap[i]);
}
}
_size = 0;
}
};
CL_NS_END
#endif
|
