1 package org.apache.lucene.util;
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 /* Derived from org.apache.lucene.util.PriorityQueue of March 2005 */
22 import java.io.IOException;
24 import org.apache.lucene.search.DocIdSetIterator;
25 import org.apache.lucene.search.Scorer;
27 /** A ScorerDocQueue maintains a partial ordering of its Scorers such that the
28 least Scorer can always be found in constant time. Put()'s and pop()'s
29 require log(size) time. The ordering is by Scorer.doc().
33 public class ScorerDocQueue { // later: SpansQueue for spans with doc and term positions
34 private final HeapedScorerDoc[] heap;
35 private final int maxSize;
38 private class HeapedScorerDoc {
42 HeapedScorerDoc(Scorer s) { this(s, s.docID()); }
44 HeapedScorerDoc(Scorer scorer, int doc) {
49 void adjust() { doc = scorer.docID(); }
52 private HeapedScorerDoc topHSD; // same as heap[1], only for speed
54 /** Create a ScorerDocQueue with a maximum size. */
55 public ScorerDocQueue(int maxSize) {
56 // assert maxSize >= 0;
58 int heapSize = maxSize + 1;
59 heap = new HeapedScorerDoc[heapSize];
60 this.maxSize = maxSize;
61 topHSD = heap[1]; // initially null
65 * Adds a Scorer to a ScorerDocQueue in log(size) time.
66 * If one tries to add more Scorers than maxSize
67 * a RuntimeException (ArrayIndexOutOfBound) is thrown.
69 public final void put(Scorer scorer) {
71 heap[size] = new HeapedScorerDoc(scorer);
76 * Adds a Scorer to the ScorerDocQueue in log(size) time if either
77 * the ScorerDocQueue is not full, or not lessThan(scorer, top()).
79 * @return true if scorer is added, false otherwise.
81 public boolean insert(Scorer scorer){
86 int docNr = scorer.docID();
87 if ((size > 0) && (! (docNr < topHSD.doc))) { // heap[1] is top()
88 heap[1] = new HeapedScorerDoc(scorer, docNr);
97 /** Returns the least Scorer of the ScorerDocQueue in constant time.
98 * Should not be used when the queue is empty.
100 public final Scorer top() {
102 return topHSD.scorer;
105 /** Returns document number of the least Scorer of the ScorerDocQueue
107 * Should not be used when the queue is empty.
109 public final int topDoc() {
114 public final float topScore() throws IOException {
116 return topHSD.scorer.score();
119 public final boolean topNextAndAdjustElsePop() throws IOException {
120 return checkAdjustElsePop(topHSD.scorer.nextDoc() != DocIdSetIterator.NO_MORE_DOCS);
123 public final boolean topSkipToAndAdjustElsePop(int target) throws IOException {
124 return checkAdjustElsePop(topHSD.scorer.advance(target) != DocIdSetIterator.NO_MORE_DOCS);
127 private boolean checkAdjustElsePop(boolean cond) {
128 if (cond) { // see also adjustTop
129 topHSD.doc = topHSD.scorer.docID();
130 } else { // see also popNoResult
131 heap[1] = heap[size]; // move last to first
139 /** Removes and returns the least scorer of the ScorerDocQueue in log(size)
141 * Should not be used when the queue is empty.
143 public final Scorer pop() {
145 Scorer result = topHSD.scorer;
150 /** Removes the least scorer of the ScorerDocQueue in log(size) time.
151 * Should not be used when the queue is empty.
153 private final void popNoResult() {
154 heap[1] = heap[size]; // move last to first
157 downHeap(); // adjust heap
160 /** Should be called when the scorer at top changes doc() value.
161 * Still log(n) worst case, but it's at least twice as fast to <pre>
162 * { pq.top().change(); pq.adjustTop(); }
163 * </pre> instead of <pre>
164 * { o = pq.pop(); o.change(); pq.push(o); }
167 public final void adjustTop() {
173 /** Returns the number of scorers currently stored in the ScorerDocQueue. */
174 public final int size() {
178 /** Removes all entries from the ScorerDocQueue. */
179 public final void clear() {
180 for (int i = 0; i <= size; i++) {
186 private final void upHeap() {
188 HeapedScorerDoc node = heap[i]; // save bottom node
190 while ((j > 0) && (node.doc < heap[j].doc)) {
191 heap[i] = heap[j]; // shift parents down
195 heap[i] = node; // install saved node
199 private final void downHeap() {
201 HeapedScorerDoc node = heap[i]; // save top node
202 int j = i << 1; // find smaller child
204 if ((k <= size) && (heap[k].doc < heap[j].doc)) {
207 while ((j <= size) && (heap[j].doc < node.doc)) {
208 heap[i] = heap[j]; // shift up child
212 if (k <= size && (heap[k].doc < heap[j].doc)) {
216 heap[i] = node; // install saved node