/usr/include/CLucene/util/PriorityQueue.h is in libclucene-dev 0.9.21b-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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
|