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