lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/PriorityQueue.java

   1 package org.apache.lucene.util;
   2
   3 /**
   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
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  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.
  18  */
  19
  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.
  23  *
  24  * <p><b>NOTE</b>: This class pre-allocates a full array of
  25  * length <code>maxSize+1</code>, in {@link #initialize}.
  26  *
  27  * @lucene.internal
  28 */
  29 public abstract class PriorityQueue<T> {
  30   private int size;
  31   private int maxSize;
  32   private T[] heap;
  33
  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>.
  37    */
  38   protected abstract boolean lessThan(T a, T b);
  39
  40   /**
  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>
  45    *
  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>
  49    *
  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>
  53    *
  54    * If this method is extended to return a non-null value, then the following
  55    * usage pattern is recommended:
  56    *
  57    * <pre>
  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();
  62    * &lt;...&gt;
  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:
  65    * pqTop.change().
  66    * pqTop = pq.updateTop();
  67    * </pre>
  68    *
  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
  74    * non-null.
  75    *
  76    * @return the sentinel object to use to pre-populate the queue, or null if
  77    *         sentinel objects are not supported.
  78    */
  79   protected T getSentinelObject() {
  80     return null;
  81   }
  82
  83   /** Subclass constructors must call this. */
  84   @SuppressWarnings("unchecked")
  85   protected final void initialize(int maxSize) {
  86     size = 0;
  87     int heapSize;
  88     if (0 == maxSize)
  89       // We allocate 1 extra to avoid if statement in top()
  90       heapSize = 2;
  91     else {
  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
 100         // the PQ:
 101         heapSize = Integer.MAX_VALUE;
 102       } else {
 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;
 106       }
 107     }
 108     heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
 109     this.maxSize = maxSize;
 110
 111     // If sentinel objects are supported, populate the queue with them
 112     T sentinel = getSentinelObject();
 113     if (sentinel != null) {
 114       heap[1] = sentinel;
 115       for (int i = 2; i < heap.length; i++) {
 116         heap[i] = getSentinelObject();
 117       }
 118       size = maxSize;
 119     }
 120   }
 121
 122   /**
 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.
 126    *
 127    * @return the new 'top' element in the queue.
 128    */
 129   public final T add(T element) {
 130     size++;
 131     heap[size] = element;
 132     upHeap();
 133     return heap[1];
 134   }
 135
 136   /**
 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.
 145    */
 146   public T insertWithOverflow(T element) {
 147     if (size < maxSize) {
 148       add(element);
 149       return null;
 150     } else if (size > 0 && !lessThan(element, heap[1])) {
 151       T ret = heap[1];
 152       heap[1] = element;
 153       updateTop();
 154       return ret;
 155     } else {
 156       return element;
 157     }
 158   }
 159
 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.
 165     return heap[1];
 166   }
 167
 168   /** Removes and returns the least element of the PriorityQueue in log(size)
 169     time. */
 170   public final T pop() {
 171     if (size > 0) {
 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
 175       size--;
 176       downHeap();                                 // adjust heap
 177       return result;
 178     } else
 179       return null;
 180   }
 181
 182   /**
 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
 185    *
 186    * <pre>
 187    * pq.top().change();
 188    * pq.updateTop();
 189    * </pre>
 190    *
 191    * instead of
 192    *
 193    * <pre>
 194    * o = pq.pop();
 195    * o.change();
 196    * pq.push(o);
 197    * </pre>
 198    *
 199    * @return the new 'top' element.
 200    */
 201   public final T updateTop() {
 202     downHeap();
 203     return heap[1];
 204   }
 205
 206   /** Returns the number of elements currently stored in the PriorityQueue. */
 207   public final int size() {
 208     return size;
 209   }
 210
 211   /** Removes all entries from the PriorityQueue. */
 212   public final void clear() {
 213     for (int i = 0; i <= size; i++) {
 214       heap[i] = null;
 215     }
 216     size = 0;
 217   }
 218
 219   private final void upHeap() {
 220     int i = size;
 221     T node = heap[i];                     // save bottom node
 222     int j = i >>> 1;
 223     while (j > 0 && lessThan(node, heap[j])) {
 224       heap[i] = heap[j];                          // shift parents down
 225       i = j;
 226       j = j >>> 1;
 227     }
 228     heap[i] = node;                               // install saved node
 229   }
 230
 231   private final void downHeap() {
 232     int i = 1;
 233     T node = heap[i];                     // save top node
 234     int j = i << 1;                               // find smaller child
 235     int k = j + 1;
 236     if (k <= size && lessThan(heap[k], heap[j])) {
 237       j = k;
 238     }
 239     while (j <= size && lessThan(heap[j], node)) {
 240       heap[i] = heap[j];                          // shift up child
 241       i = j;
 242       j = i << 1;
 243       k = j + 1;
 244       if (k <= size && lessThan(heap[k], heap[j])) {
 245         j = k;
 246       }
 247     }
 248     heap[i] = node;                               // install saved node
 249   }
 250
 251   /** This method returns the internal heap array as Object[].
 252    * @lucene.internal
 253    */
 254   protected final Object[] getHeapArray() {
 255     return (Object[]) heap;
 256   }
 257 }