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