1 package org.apache.lucene.util;
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
20 /** A PriorityQueue maintains a partial ordering of its elements such that the
21 * least element can always be found in constant time. Put()'s and pop()'s
22 * require log(size) time.
24 * <p><b>NOTE</b>: This class pre-allocates a full array of
25 * length <code>maxSize+1</code>, in {@link #initialize}.
29 public abstract class PriorityQueue<T> {
34 /** Determines the ordering of objects in this priority queue. Subclasses
35 * must define this one method.
36 * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
38 protected abstract boolean lessThan(T a, T b);
41 * This method can be overridden by extending classes to return a sentinel
42 * object which will be used by {@link #initialize(int)} to fill the queue, so
43 * that the code which uses that queue can always assume it's full and only
44 * change the top without attempting to insert any new object.<br>
46 * Those sentinel values should always compare worse than any non-sentinel
47 * value (i.e., {@link #lessThan} should always favor the
48 * non-sentinel values).<br>
50 * By default, this method returns false, which means the queue will not be
51 * filled with sentinel values. Otherwise, the value returned will be used to
52 * pre-populate the queue. Adds sentinel values to the queue.<br>
54 * If this method is extended to return a non-null value, then the following
55 * usage pattern is recommended:
58 * // extends getSentinelObject() to return a non-null value.
59 * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
60 * // save the 'top' element, which is guaranteed to not be null.
61 * MyObject pqTop = pq.top();
63 * // now in order to add a new element, which is 'better' than top (after
64 * // you've verified it is better), it is as simple as:
66 * pqTop = pq.updateTop();
69 * <b>NOTE:</b> if this method returns a non-null value, it will be called by
70 * {@link #initialize(int)} {@link #size()} times, relying on a new object to
71 * be returned and will not check if it's null again. Therefore you should
72 * ensure any call to this method creates a new instance and behaves
73 * consistently, e.g., it cannot return null if it previously returned
76 * @return the sentinel object to use to pre-populate the queue, or null if
77 * sentinel objects are not supported.
79 protected T getSentinelObject() {
83 /** Subclass constructors must call this. */
84 @SuppressWarnings("unchecked")
85 protected final void initialize(int maxSize) {
89 // We allocate 1 extra to avoid if statement in top()
92 if (maxSize == Integer.MAX_VALUE) {
93 // Don't wrap heapSize to -1, in this case, which
94 // causes a confusing NegativeArraySizeException.
95 // Note that very likely this will simply then hit
96 // an OOME, but at least that's more indicative to
97 // caller that this values is too big. We don't +1
98 // in this case, but it's very unlikely in practice
99 // one will actually insert this many objects into
101 heapSize = Integer.MAX_VALUE;
103 // NOTE: we add +1 because all access to heap is
104 // 1-based not 0-based. heap[0] is unused.
105 heapSize = maxSize + 1;
108 heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
109 this.maxSize = maxSize;
111 // If sentinel objects are supported, populate the queue with them
112 T sentinel = getSentinelObject();
113 if (sentinel != null) {
115 for (int i = 2; i < heap.length; i++) {
116 heap[i] = getSentinelObject();
123 * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
124 * more objects than maxSize from initialize an
125 * {@link ArrayIndexOutOfBoundsException} is thrown.
127 * @return the new 'top' element in the queue.
129 public final T add(T element) {
131 heap[size] = element;
137 * Adds an Object to a PriorityQueue in log(size) time.
138 * It returns the object (if any) that was
139 * dropped off the heap because it was full. This can be
140 * the given parameter (in case it is smaller than the
141 * full heap's minimum, and couldn't be added), or another
142 * object that was previously the smallest value in the
143 * heap and now has been replaced by a larger one, or null
144 * if the queue wasn't yet full with maxSize elements.
146 public T insertWithOverflow(T element) {
147 if (size < maxSize) {
150 } else if (size > 0 && !lessThan(element, heap[1])) {
160 /** Returns the least element of the PriorityQueue in constant time. */
161 public final T top() {
162 // We don't need to check size here: if maxSize is 0,
163 // then heap is length 2 array with both entries null.
164 // If size is 0 then heap[1] is already null.
168 /** Removes and returns the least element of the PriorityQueue in log(size)
170 public final T pop() {
172 T result = heap[1]; // save first value
173 heap[1] = heap[size]; // move last to first
174 heap[size] = null; // permit GC of objects
176 downHeap(); // adjust heap
183 * Should be called when the Object at top changes values. Still log(n) worst
184 * case, but it's at least twice as fast to
199 * @return the new 'top' element.
201 public final T updateTop() {
206 /** Returns the number of elements currently stored in the PriorityQueue. */
207 public final int size() {
211 /** Removes all entries from the PriorityQueue. */
212 public final void clear() {
213 for (int i = 0; i <= size; i++) {
219 private final void upHeap() {
221 T node = heap[i]; // save bottom node
223 while (j > 0 && lessThan(node, heap[j])) {
224 heap[i] = heap[j]; // shift parents down
228 heap[i] = node; // install saved node
231 private final void downHeap() {
233 T node = heap[i]; // save top node
234 int j = i << 1; // find smaller child
236 if (k <= size && lessThan(heap[k], heap[j])) {
239 while (j <= size && lessThan(heap[j], node)) {
240 heap[i] = heap[j]; // shift up child
244 if (k <= size && lessThan(heap[k], heap[j])) {
248 heap[i] = node; // install saved node
251 /** This method returns the internal heap array as Object[].
254 protected final Object[] getHeapArray() {
255 return (Object[]) heap;