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 public abstract class PriorityQueue {
24 private int size;
25 private int maxSize;
26 protected Object[] heap;
27
28 /** Determines the ordering of objects in this priority queue. Subclasses
29 must define this one method. */
30 protected abstract boolean lessThan(Object a, Object b);
31
32 /** Subclass constructors must call this. */
33 protected final void initialize(int maxSize) {
34 size = 0;
35 int heapSize;
36 if (0 == maxSize)
37 // We allocate 1 extra to avoid if statement in top()
38 heapSize = 2;
39 else
40 heapSize = maxSize + 1;
41 heap = new Object[heapSize];
42 this.maxSize = maxSize;
43 }
44
45 /**
46 * Adds an Object to a PriorityQueue in log(size) time.
47 * If one tries to add more objects than maxSize from initialize
48 * a RuntimeException (ArrayIndexOutOfBound) is thrown.
49 */
50 public final void put(Object element) {
51 size++;
52 heap[size] = element;
53 upHeap();
54 }
55
56 /**
57 * Adds element to the PriorityQueue in log(size) time if either
58 * the PriorityQueue is not full, or not lessThan(element, top()).
59 * @param element
60 * @return true if element is added, false otherwise.
61 */
62 public boolean insert(Object element) {
63 return insertWithOverflow(element) != element;
64 }
65
66 /**
67 * insertWithOverflow() is the same as insert() except its
68 * return value: it returns the object (if any) that was
69 * dropped off the heap because it was full. This can be
70 * the given parameter (in case it is smaller than the
71 * full heap's minimum, and couldn't be added), or another
72 * object that was previously the smallest value in the
73 * heap and now has been replaced by a larger one, or null
74 * if the queue wasn't yet full with maxSize elements.
75 */
76 public Object insertWithOverflow(Object element) {
77 if (size < maxSize) {
78 put(element);
79 return null;
80 } else if (size > 0 && !lessThan(element, heap[1])) {
81 Object ret = heap[1];
82 heap[1] = element;
83 adjustTop();
84 return ret;
85 } else {
86 return element;
87 }
88 }
89
90 /** Returns the least element of the PriorityQueue in constant time. */
91 public final Object top() {
92 // We don't need to check size here: if maxSize is 0,
93 // then heap is length 2 array with both entries null.
94 // If size is 0 then heap[1] is already null.
95 return heap[1];
96 }
97
98 /** Removes and returns the least element of the PriorityQueue in log(size)
99 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 }
Save This Page