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: /* Derived from org.apache.lucene.util.PriorityQueue of March 2005 */
021:
022: import java.io.IOException;
023: import org.apache.lucene.search.Scorer;
024:
025: /** A ScorerDocQueue maintains a partial ordering of its Scorers such that the
026: least Scorer can always be found in constant time. Put()'s and pop()'s
027: require log(size) time. The ordering is by Scorer.doc().
028: */
029: public class ScorerDocQueue { // later: SpansQueue for spans with doc and term positions
030: private final HeapedScorerDoc[] heap;
031: private final int maxSize;
032: private int size;
033:
034: private class HeapedScorerDoc {
035: Scorer scorer;
036: int doc;
037:
038: HeapedScorerDoc(Scorer s) {
039: this (s, s.doc());
040: }
041:
042: HeapedScorerDoc(Scorer scorer, int doc) {
043: this .scorer = scorer;
044: this .doc = doc;
045: }
046:
047: void adjust() {
048: doc = scorer.doc();
049: }
050: }
051:
052: private HeapedScorerDoc topHSD; // same as heap[1], only for speed
053:
054: /** Create a ScorerDocQueue with a maximum size. */
055: public ScorerDocQueue(int maxSize) {
056: // assert maxSize >= 0;
057: size = 0;
058: int heapSize = maxSize + 1;
059: heap = new HeapedScorerDoc[heapSize];
060: this .maxSize = maxSize;
061: topHSD = heap[1]; // initially null
062: }
063:
064: /**
065: * Adds a Scorer to a ScorerDocQueue in log(size) time.
066: * If one tries to add more Scorers than maxSize
067: * a RuntimeException (ArrayIndexOutOfBound) is thrown.
068: */
069: public final void put(Scorer scorer) {
070: size++;
071: heap[size] = new HeapedScorerDoc(scorer);
072: upHeap();
073: }
074:
075: /**
076: * Adds a Scorer to the ScorerDocQueue in log(size) time if either
077: * the ScorerDocQueue is not full, or not lessThan(scorer, top()).
078: * @param scorer
079: * @return true if scorer is added, false otherwise.
080: */
081: public boolean insert(Scorer scorer) {
082: if (size < maxSize) {
083: put(scorer);
084: return true;
085: } else {
086: int docNr = scorer.doc();
087: if ((size > 0) && (!(docNr < topHSD.doc))) { // heap[1] is top()
088: heap[1] = new HeapedScorerDoc(scorer, docNr);
089: downHeap();
090: return true;
091: } else {
092: return false;
093: }
094: }
095: }
096:
097: /** Returns the least Scorer of the ScorerDocQueue in constant time.
098: * Should not be used when the queue is empty.
099: */
100: public final Scorer top() {
101: // assert size > 0;
102: return topHSD.scorer;
103: }
104:
105: /** Returns document number of the least Scorer of the ScorerDocQueue
106: * in constant time.
107: * Should not be used when the queue is empty.
108: */
109: public final int topDoc() {
110: // assert size > 0;
111: return topHSD.doc;
112: }
113:
114: public final float topScore() throws IOException {
115: // assert size > 0;
116: return topHSD.scorer.score();
117: }
118:
119: public final boolean topNextAndAdjustElsePop() throws IOException {
120: return checkAdjustElsePop(topHSD.scorer.next());
121: }
122:
123: public final boolean topSkipToAndAdjustElsePop(int target)
124: throws IOException {
125: return checkAdjustElsePop(topHSD.scorer.skipTo(target));
126: }
127:
128: private boolean checkAdjustElsePop(boolean cond) {
129: if (cond) { // see also adjustTop
130: topHSD.doc = topHSD.scorer.doc();
131: } else { // see also popNoResult
132: heap[1] = heap[size]; // move last to first
133: heap[size] = null;
134: size--;
135: }
136: downHeap();
137: return cond;
138: }
139:
140: /** Removes and returns the least scorer of the ScorerDocQueue in log(size)
141: * time.
142: * Should not be used when the queue is empty.
143: */
144: public final Scorer pop() {
145: // assert size > 0;
146: Scorer result = topHSD.scorer;
147: popNoResult();
148: return result;
149: }
150:
151: /** Removes the least scorer of the ScorerDocQueue in log(size) time.
152: * Should not be used when the queue is empty.
153: */
154: private final void popNoResult() {
155: heap[1] = heap[size]; // move last to first
156: heap[size] = null;
157: size--;
158: downHeap(); // adjust heap
159: }
160:
161: /** Should be called when the scorer at top changes doc() value.
162: * Still log(n) worst case, but it's at least twice as fast to <pre>
163: * { pq.top().change(); pq.adjustTop(); }
164: * </pre> instead of <pre>
165: * { o = pq.pop(); o.change(); pq.push(o); }
166: * </pre>
167: */
168: public final void adjustTop() {
169: // assert size > 0;
170: topHSD.adjust();
171: downHeap();
172: }
173:
174: /** Returns the number of scorers currently stored in the ScorerDocQueue. */
175: public final int size() {
176: return size;
177: }
178:
179: /** Removes all entries from the ScorerDocQueue. */
180: public final void clear() {
181: for (int i = 0; i <= size; i++) {
182: heap[i] = null;
183: }
184: size = 0;
185: }
186:
187: private final void upHeap() {
188: int i = size;
189: HeapedScorerDoc node = heap[i]; // save bottom node
190: int j = i >>> 1;
191: while ((j > 0) && (node.doc < heap[j].doc)) {
192: heap[i] = heap[j]; // shift parents down
193: i = j;
194: j = j >>> 1;
195: }
196: heap[i] = node; // install saved node
197: topHSD = heap[1];
198: }
199:
200: private final void downHeap() {
201: int i = 1;
202: HeapedScorerDoc node = heap[i]; // save top node
203: int j = i << 1; // find smaller child
204: int k = j + 1;
205: if ((k <= size) && (heap[k].doc < heap[j].doc)) {
206: j = k;
207: }
208: while ((j <= size) && (heap[j].doc < node.doc)) {
209: heap[i] = heap[j]; // shift up child
210: i = j;
211: j = i << 1;
212: k = j + 1;
213: if (k <= size && (heap[k].doc < heap[j].doc)) {
214: j = k;
215: }
216: }
217: heap[i] = node; // install saved node
218: topHSD = heap[1];
219: }
220: }
|