PriorityQueue.java
001 package gate.creole.annic.apache.lucene.util;
002 
003 /**
004  * Copyright 2004 The Apache Software Foundation
005  *
006  * Licensed under the Apache License, Version 2.0 (the "License");
007  * you may not use this file except in compliance with the License.
008  * You may obtain a copy of the License at
009  *
010  *     http://www.apache.org/licenses/LICENSE-2.0
011  *
012  * Unless required by applicable law or agreed to in writing, software
013  * distributed under the License is distributed on an "AS IS" BASIS,
014  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015  * See the License for the specific language governing permissions and
016  * limitations under the License.
017  */
018 
019 /** A PriorityQueue maintains a partial ordering of its elements such that the
020   least element can always be found in constant time.  Put()'s and pop()'s
021   require log(size) time. */
022 public abstract class PriorityQueue {
023   private Object[] heap;
024   private int size;
025   private int maxSize;
026 
027   /** Determines the ordering of objects in this priority queue.  Subclasses
028     must define this one method. */
029   protected abstract boolean lessThan(Object a, Object b);
030 
031   /** Subclass constructors must call this. */
032   protected final void initialize(int maxSize) {
033     size = 0;
034     int heapSize = maxSize + 1;
035     heap = new Object[heapSize];
036     this.maxSize = maxSize;
037   }
038 
039   /**
040    * Adds an Object to a PriorityQueue in log(size) time.
041    * If one tries to add more objects than maxSize from initialize
042    * a RuntimeException (ArrayIndexOutOfBound) is thrown.
043    */
044   public final void put(Object element) {
045     size++;
046     heap[size= element;
047     upHeap();
048   }
049 
050   /**
051    * Adds element to the PriorityQueue in log(size) time if either
052    * the PriorityQueue is not full, or not lessThan(element, top()).
053    @param element
054    @return true if element is added, false otherwise.
055    */
056   public boolean insert(Object element){
057     if(size < maxSize){
058         put(element);
059         return true;
060     }
061     else if(size > && !lessThan(element, top())){
062         heap[1= element;
063         adjustTop();
064         return true;
065     }
066     else
067         return false;
068    }
069 
070   /** Returns the least element of the PriorityQueue in constant time. */
071   public final Object top() {
072     if (size > 0)
073       return heap[1];
074     else
075       return null;
076   }
077 
078   /** Removes and returns the least element of the PriorityQueue in log(size)
079     time. */
080   public final Object pop() {
081     if (size > 0) {
082       Object result = heap[1];        // save first value
083       heap[1= heap[size];        // move last to first
084       heap[sizenull;        // permit GC of objects
085       size--;
086       downHeap();          // adjust heap
087       return result;
088     else
089       return null;
090   }
091 
092   /** Should be called when the Object at top changes values.  Still log(n)
093    * worst case, but it's at least twice as fast to <pre>
094    *  { pq.top().change(); pq.adjustTop(); }
095    </pre> instead of <pre>
096    *  { o = pq.pop(); o.change(); pq.push(o); }
097    </pre>
098    */
099   public final void adjustTop() {
100     downHeap();
101   }
102 
103 
104   /** Returns the number of elements currently stored in the PriorityQueue. */
105   public final int size() {
106     return size;
107   }
108 
109   /** Removes all entries from the PriorityQueue. */
110   public final void clear() {
111     for (int i = 0; i <= size; i++)
112       heap[inull;
113     size = 0;
114   }
115 
116   private final void upHeap() {
117     int i = size;
118     Object node = heap[i];        // save bottom node
119     int j = i >>> 1;
120     while (j > && lessThan(node, heap[j])) {
121       heap[i= heap[j];        // shift parents down
122       i = j;
123       j = j >>> 1;
124     }
125     heap[i= node;          // install saved node
126   }
127 
128   private final void downHeap() {
129     int i = 1;
130     Object node = heap[i];        // save top node
131     int j = i << 1;          // find smaller child
132     int k = j + 1;
133     if (k <= size && lessThan(heap[k], heap[j])) {
134       j = k;
135     }
136     while (j <= size && lessThan(heap[j], node)) {
137       heap[i= heap[j];        // shift up child
138       i = j;
139       j = i << 1;
140       k = j + 1;
141       if (k <= size && lessThan(heap[k], heap[j])) {
142   j = k;
143       }
144     }
145     heap[i= node;          // install saved node
146   }
147 }