+++ /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