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 |
13 | CL_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. |
18 | template <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 | |
176 | CL_NS_END |
177 | #endif |
178 | |