1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19 package org.apache.myfaces.shared.util;
20
21 /** A PriorityQueue maintains a partial ordering of its elements such that the
22 * least element can always be found in constant time. Put()'s and pop()'s
23 * require log(size) time.
24 *
25 * <p><b>NOTE</b>: This class will pre-allocate a full array of
26 * length <code>maxSize+1</code> if instantiated via the
27 * {@link #PriorityQueue(int,boolean)} constructor with
28 * <code>prepopulate</code> set to <code>true</code>.
29 *
30 * @lucene.internal
31 * @see org.apache.lucene.util.PriorityQueue
32 */
33 public abstract class PriorityQueue<T>
34 {
35 private int size;
36 private final int maxSize;
37 private final T[] heap;
38
39 public PriorityQueue(int maxSize)
40 {
41 this(maxSize, true);
42 }
43
44 @SuppressWarnings("unchecked")
45 public PriorityQueue(int maxSize, boolean prepopulate)
46 {
47 size = 0;
48 int heapSize;
49 if (0 == maxSize)
50 {
51 // We allocate 1 extra to avoid if statement in top()
52 heapSize = 2;
53 }
54 else
55 {
56 if (maxSize == Integer.MAX_VALUE)
57 {
58 // Don't wrap heapSize to -1, in this case, which
59 // causes a confusing NegativeArraySizeException.
60 // Note that very likely this will simply then hit
61 // an OOME, but at least that's more indicative to
62 // caller that this values is too big. We don't +1
63 // in this case, but it's very unlikely in practice
64 // one will actually insert this many objects into
65 // the PQ:
66 heapSize = Integer.MAX_VALUE;
67 }
68 else
69 {
70 // NOTE: we add +1 because all access to heap is
71 // 1-based not 0-based. heap[0] is unused.
72 heapSize = maxSize + 1;
73 }
74 }
75 heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
76 this.maxSize = maxSize;
77
78 if (prepopulate)
79 {
80 // If sentinel objects are supported, populate the queue with them
81 T sentinel = getSentinelObject();
82 if (sentinel != null)
83 {
84 heap[1] = sentinel;
85 for (int i = 2; i < heap.length; i++)
86 {
87 heap[i] = getSentinelObject();
88 }
89 size = maxSize;
90 }
91 }
92 }
93
94 /** Determines the ordering of objects in this priority queue. Subclasses
95 * must define this one method.
96 * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
97 */
98 protected abstract boolean lessThan(T a, T b);
99
100 /**
101 * This method can be overridden by extending classes to return a sentinel
102 * object which will be used by the {@link PriorityQueue#PriorityQueue(int,boolean)}
103 * constructor to fill the queue, so that the code which uses that queue can always
104 * assume it's full and only change the top without attempting to insert any new
105 * object.<br>
106 *
107 * Those sentinel values should always compare worse than any non-sentinel
108 * value (i.e., {@link #lessThan} should always favor the
109 * non-sentinel values).<br>
110 *
111 * By default, this method returns false, which means the queue will not be
112 * filled with sentinel values. Otherwise, the value returned will be used to
113 * pre-populate the queue. Adds sentinel values to the queue.<br>
114 *
115 * If this method is extended to return a non-null value, then the following
116 * usage pattern is recommended:
117 *
118 * <pre>
119 * // extends getSentinelObject() to return a non-null value.
120 * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
121 * // save the 'top' element, which is guaranteed to not be null.
122 * MyObject pqTop = pq.top();
123 * <...>
124 * // now in order to add a new element, which is 'better' than top (after
125 * // you've verified it is better), it is as simple as:
126 * pqTop.change().
127 * pqTop = pq.updateTop();
128 * </pre>
129 *
130 * <b>NOTE:</b> if this method returns a non-null value, it will be called by
131 * the {@link PriorityQueue#PriorityQueue(int,boolean)} constructor
132 * {@link #size()} times, relying on a new object to be returned and will not
133 * check if it's null again. Therefore you should ensure any call to this
134 * method creates a new instance and behaves consistently, e.g., it cannot
135 * return null if it previously returned non-null.
136 *
137 * @return the sentinel object to use to pre-populate the queue, or null if
138 * sentinel objects are not supported.
139 */
140 protected T getSentinelObject()
141 {
142 return null;
143 }
144
145 /**
146 * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
147 * more objects than maxSize from initialize an
148 * {@link ArrayIndexOutOfBoundsException} is thrown.
149 *
150 * @return the new 'top' element in the queue.
151 */
152 public final T add(T element)
153 {
154 size++;
155 heap[size] = element;
156 upHeap();
157 return heap[1];
158 }
159
160 /**
161 * Adds an Object to a PriorityQueue in log(size) time.
162 * It returns the object (if any) that was
163 * dropped off the heap because it was full. This can be
164 * the given parameter (in case it is smaller than the
165 * full heap's minimum, and couldn't be added), or another
166 * object that was previously the smallest value in the
167 * heap and now has been replaced by a larger one, or null
168 * if the queue wasn't yet full with maxSize elements.
169 */
170 public T insertWithOverflow(T element)
171 {
172 if (size < maxSize)
173 {
174 add(element);
175 return null;
176 }
177 else if (size > 0 && !lessThan(element, heap[1]))
178 {
179 T ret = heap[1];
180 heap[1] = element;
181 updateTop();
182 return ret;
183 }
184 else
185 {
186 return element;
187 }
188 }
189
190 /** Returns the least element of the PriorityQueue in constant time. */
191 public final T top()
192 {
193 // We don't need to check size here: if maxSize is 0,
194 // then heap is length 2 array with both entries null.
195 // If size is 0 then heap[1] is already null.
196 return heap[1];
197 }
198
199 /** Removes and returns the least element of the PriorityQueue in log(size)
200 time. */
201 public final T pop()
202 {
203 if (size > 0)
204 {
205 T result = heap[1]; // save first value
206 heap[1] = heap[size]; // move last to first
207 heap[size] = null; // permit GC of objects
208 size--;
209 downHeap(); // adjust heap
210 return result;
211 }
212 else
213 {
214 return null;
215 }
216 }
217
218 /**
219 * Should be called when the Object at top changes values. Still log(n) worst
220 * case, but it's at least twice as fast to
221 *
222 * <pre>
223 * pq.top().change();
224 * pq.updateTop();
225 * </pre>
226 *
227 * instead of
228 *
229 * <pre>
230 * o = pq.pop();
231 * o.change();
232 * pq.push(o);
233 * </pre>
234 *
235 * @return the new 'top' element.
236 */
237 public final T updateTop()
238 {
239 downHeap();
240 return heap[1];
241 }
242
243 /** Returns the number of elements currently stored in the PriorityQueue. */
244 public final int size()
245 {
246 return size;
247 }
248
249 /** Removes all entries from the PriorityQueue. */
250 public final void clear()
251 {
252 for (int i = 0; i <= size; i++)
253 {
254 heap[i] = null;
255 }
256 size = 0;
257 }
258
259 private final void upHeap()
260 {
261 int i = size;
262 T node = heap[i]; // save bottom node
263 int j = i >>> 1;
264 while (j > 0 && lessThan(node, heap[j]))
265 {
266 heap[i] = heap[j]; // shift parents down
267 i = j;
268 j = j >>> 1;
269 }
270 heap[i] = node; // install saved node
271 }
272
273 private final void downHeap()
274 {
275 int i = 1;
276 T node = heap[i]; // save top node
277 int j = i << 1; // find smaller child
278 int k = j + 1;
279 if (k <= size && lessThan(heap[k], heap[j]))
280 {
281 j = k;
282 }
283 while (j <= size && lessThan(heap[j], node))
284 {
285 heap[i] = heap[j]; // shift up child
286 i = j;
287 j = i << 1;
288 k = j + 1;
289 if (k <= size && lessThan(heap[k], heap[j]))
290 {
291 j = k;
292 }
293 }
294 heap[i] = node; // install saved node
295 }
296
297 /** This method returns the internal heap array as Object[].
298 * @lucene.internal
299 */
300 protected final Object[] getHeapArray()
301 {
302 return (Object[]) heap;
303 }
304 }