--- /dev/null
+package org.apache.lucene.util;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/** 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.
+ *
+ * <p><b>NOTE</b>: This class pre-allocates a full array of
+ * length <code>maxSize+1</code>, in {@link #initialize}.
+ *
+ * @lucene.internal
+*/
+public abstract class PriorityQueue<T> {
+ private int size;
+ private int maxSize;
+ private T[] heap;
+
+ /** Determines the ordering of objects in this priority queue. Subclasses
+ * must define this one method.
+ * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
+ */
+ protected abstract boolean lessThan(T a, T b);
+
+ /**
+ * This method can be overridden by extending classes to return a sentinel
+ * object which will be used by {@link #initialize(int)} to fill the queue, so
+ * that the code which uses that queue can always assume it's full and only
+ * change the top without attempting to insert any new object.<br>
+ *
+ * Those sentinel values should always compare worse than any non-sentinel
+ * value (i.e., {@link #lessThan} should always favor the
+ * non-sentinel values).<br>
+ *
+ * By default, this method returns false, which means the queue will not be
+ * filled with sentinel values. Otherwise, the value returned will be used to
+ * pre-populate the queue. Adds sentinel values to the queue.<br>
+ *
+ * If this method is extended to return a non-null value, then the following
+ * usage pattern is recommended:
+ *
+ * <pre>
+ * // extends getSentinelObject() to return a non-null value.
+ * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
+ * // save the 'top' element, which is guaranteed to not be null.
+ * MyObject pqTop = pq.top();
+ * <...>
+ * // now in order to add a new element, which is 'better' than top (after
+ * // you've verified it is better), it is as simple as:
+ * pqTop.change().
+ * pqTop = pq.updateTop();
+ * </pre>
+ *
+ * <b>NOTE:</b> if this method returns a non-null value, it will be called by
+ * {@link #initialize(int)} {@link #size()} times, relying on a new object to
+ * be returned and will not check if it's null again. Therefore you should
+ * ensure any call to this method creates a new instance and behaves
+ * consistently, e.g., it cannot return null if it previously returned
+ * non-null.
+ *
+ * @return the sentinel object to use to pre-populate the queue, or null if
+ * sentinel objects are not supported.
+ */
+ protected T getSentinelObject() {
+ return null;
+ }
+
+ /** Subclass constructors must call this. */
+ @SuppressWarnings("unchecked")
+ protected final void initialize(int maxSize) {
+ size = 0;
+ int heapSize;
+ if (0 == maxSize)
+ // We allocate 1 extra to avoid if statement in top()
+ heapSize = 2;
+ else {
+ if (maxSize == Integer.MAX_VALUE) {
+ // Don't wrap heapSize to -1, in this case, which
+ // causes a confusing NegativeArraySizeException.
+ // Note that very likely this will simply then hit
+ // an OOME, but at least that's more indicative to
+ // caller that this values is too big. We don't +1
+ // in this case, but it's very unlikely in practice
+ // one will actually insert this many objects into
+ // the PQ:
+ heapSize = Integer.MAX_VALUE;
+ } else {
+ // NOTE: we add +1 because all access to heap is
+ // 1-based not 0-based. heap[0] is unused.
+ heapSize = maxSize + 1;
+ }
+ }
+ heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
+ this.maxSize = maxSize;
+
+ // If sentinel objects are supported, populate the queue with them
+ T sentinel = getSentinelObject();
+ if (sentinel != null) {
+ heap[1] = sentinel;
+ for (int i = 2; i < heap.length; i++) {
+ heap[i] = getSentinelObject();
+ }
+ size = maxSize;
+ }
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
+ * more objects than maxSize from initialize an
+ * {@link ArrayIndexOutOfBoundsException} is thrown.
+ *
+ * @return the new 'top' element in the queue.
+ */
+ public final T add(T element) {
+ size++;
+ heap[size] = element;
+ upHeap();
+ return heap[1];
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time.
+ * It returns the object (if any) that was
+ * dropped off the heap because it was full. This can be
+ * the given parameter (in case it is smaller than the
+ * full heap's minimum, and couldn't be added), or another
+ * object that was previously the smallest value in the
+ * heap and now has been replaced by a larger one, or null
+ * if the queue wasn't yet full with maxSize elements.
+ */
+ public T insertWithOverflow(T element) {
+ if (size < maxSize) {
+ add(element);
+ return null;
+ } else if (size > 0 && !lessThan(element, heap[1])) {
+ T ret = heap[1];
+ heap[1] = element;
+ updateTop();
+ return ret;
+ } else {
+ return element;
+ }
+ }
+
+ /** Returns the least element of the PriorityQueue in constant time. */
+ public final T top() {
+ // We don't need to check size here: if maxSize is 0,
+ // then heap is length 2 array with both entries null.
+ // If size is 0 then heap[1] is already null.
+ return heap[1];
+ }
+
+ /** Removes and returns the least element of the PriorityQueue in log(size)
+ time. */
+ public final T pop() {
+ if (size > 0) {
+ T result = heap[1]; // save first value
+ heap[1] = heap[size]; // move last to first
+ heap[size] = null; // permit GC of objects
+ size--;
+ downHeap(); // adjust heap
+ return result;
+ } else
+ return 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.updateTop();
+ * </pre>
+ *
+ * instead of
+ *
+ * <pre>
+ * o = pq.pop();
+ * o.change();
+ * pq.push(o);
+ * </pre>
+ *
+ * @return the new 'top' element.
+ */
+ public final T updateTop() {
+ downHeap();
+ return heap[1];
+ }
+
+ /** Returns the number of elements currently stored in the PriorityQueue. */
+ public final int size() {
+ return size;
+ }
+
+ /** Removes all entries from the PriorityQueue. */
+ public final void clear() {
+ for (int i = 0; i <= size; i++) {
+ heap[i] = null;
+ }
+ size = 0;
+ }
+
+ private final void upHeap() {
+ int i = size;
+ T node = heap[i]; // save bottom node
+ int j = i >>> 1;
+ while (j > 0 && lessThan(node, heap[j])) {
+ heap[i] = heap[j]; // shift parents down
+ i = j;
+ j = j >>> 1;
+ }
+ heap[i] = node; // install saved node
+ }
+
+ private final void downHeap() {
+ int i = 1;
+ T node = heap[i]; // save top node
+ int j = i << 1; // find smaller child
+ int 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
+ }
+
+ /** This method returns the internal heap array as Object[].
+ * @lucene.internal
+ */
+ protected final Object[] getHeapArray() {
+ return (Object[]) heap;
+ }
+}
fnp / pylucene.git / blobdiff