← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/java/org/apache/lucene/util/ScorerDocQueue.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
lucene/src/java/org/apache/lucene/util/ScorerDocQueue.java
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
 
/* Derived from org.apache.lucene.util.PriorityQueue of March 2005 */
21
 
 
22
 
import java.io.IOException;
23
 
 
24
 
import org.apache.lucene.search.DocIdSetIterator;
25
 
import org.apache.lucene.search.Scorer;
26
 
 
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().
30
 
 *
31
 
 * @lucene.internal
32
 
 */
33
 
public class ScorerDocQueue {  // later: SpansQueue for spans with doc and term positions
34
 
  private final HeapedScorerDoc[] heap;
35
 
  private final int maxSize;
36
 
  private int size;
37
 
  
38
 
  private class HeapedScorerDoc {
39
 
    Scorer scorer;
40
 
    int doc;
41
 
    
42
 
    HeapedScorerDoc(Scorer s) { this(s, s.docID()); }
43
 
    
44
 
    HeapedScorerDoc(Scorer scorer, int doc) {
45
 
      this.scorer = scorer;
46
 
      this.doc = doc;
47
 
    }
48
 
    
49
 
    void adjust() { doc = scorer.docID(); }
50
 
  }
51
 
  
52
 
  private HeapedScorerDoc topHSD; // same as heap[1], only for speed
53
 
 
54
 
  /** Create a ScorerDocQueue with a maximum size. */
55
 
  public ScorerDocQueue(int maxSize) {
56
 
    // assert maxSize >= 0;
57
 
    size = 0;
58
 
    int heapSize = maxSize + 1;
59
 
    heap = new HeapedScorerDoc[heapSize];
60
 
    this.maxSize = maxSize;
61
 
    topHSD = heap[1]; // initially null
62
 
  }
63
 
 
64
 
  /**
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.
68
 
   */
69
 
  public final void put(Scorer scorer) {
70
 
    size++;
71
 
    heap[size] = new HeapedScorerDoc(scorer);
72
 
    upHeap();
73
 
  }
74
 
 
75
 
  /**
76
 
   * Adds a Scorer to the ScorerDocQueue in log(size) time if either
77
 
   * the ScorerDocQueue is not full, or not lessThan(scorer, top()).
78
 
   * @param scorer
79
 
   * @return true if scorer is added, false otherwise.
80
 
   */
81
 
  public boolean insert(Scorer scorer){
82
 
    if (size < maxSize) {
83
 
      put(scorer);
84
 
      return true;
85
 
    } else {
86
 
      int docNr = scorer.docID();
87
 
      if ((size > 0) && (! (docNr < topHSD.doc))) { // heap[1] is top()
88
 
        heap[1] = new HeapedScorerDoc(scorer, docNr);
89
 
        downHeap();
90
 
        return true;
91
 
      } else {
92
 
        return false;
93
 
      }
94
 
    }
95
 
   }
96
 
 
97
 
  /** Returns the least Scorer of the ScorerDocQueue in constant time.
98
 
   * Should not be used when the queue is empty.
99
 
   */
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.nextDoc() != DocIdSetIterator.NO_MORE_DOCS);
121
 
  }
122
 
 
123
 
  public final boolean topSkipToAndAdjustElsePop(int target) throws IOException {
124
 
    return checkAdjustElsePop(topHSD.scorer.advance(target) != DocIdSetIterator.NO_MORE_DOCS);
125
 
  }
126
 
  
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
132
 
      heap[size] = null;
133
 
      size--;
134
 
    }
135
 
    downHeap();
136
 
    return cond;
137
 
  }
138
 
 
139
 
  /** Removes and returns the least scorer of the ScorerDocQueue in log(size)
140
 
   * time.
141
 
   * Should not be used when the queue is empty.
142
 
   */
143
 
  public final Scorer pop() {
144
 
    // assert size > 0;
145
 
    Scorer result = topHSD.scorer;
146
 
    popNoResult();
147
 
    return result;
148
 
  }
149
 
  
150
 
  /** Removes the least scorer of the ScorerDocQueue in log(size) time.
151
 
   * Should not be used when the queue is empty.
152
 
   */
153
 
  private final void popNoResult() {
154
 
    heap[1] = heap[size]; // move last to first
155
 
    heap[size] = null;
156
 
    size--;
157
 
    downHeap(); // adjust heap
158
 
  }
159
 
 
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); }
165
 
   * </pre>
166
 
   */
167
 
  public final void adjustTop() {
168
 
    // assert size > 0;
169
 
    topHSD.adjust();
170
 
    downHeap();
171
 
  }
172
 
 
173
 
  /** Returns the number of scorers currently stored in the ScorerDocQueue. */
174
 
  public final int size() {
175
 
    return size;
176
 
  }
177
 
 
178
 
  /** Removes all entries from the ScorerDocQueue. */
179
 
  public final void clear() {
180
 
    for (int i = 0; i <= size; i++) {
181
 
      heap[i] = null;
182
 
    }
183
 
    size = 0;
184
 
  }
185
 
 
186
 
  private final void upHeap() {
187
 
    int i = size;
188
 
    HeapedScorerDoc node = heap[i];               // save bottom node
189
 
    int j = i >>> 1;
190
 
    while ((j > 0) && (node.doc < heap[j].doc)) {
191
 
      heap[i] = heap[j];                          // shift parents down
192
 
      i = j;
193
 
      j = j >>> 1;
194
 
    }
195
 
    heap[i] = node;                               // install saved node
196
 
    topHSD = heap[1];
197
 
  }
198
 
 
199
 
  private final void downHeap() {
200
 
    int i = 1;
201
 
    HeapedScorerDoc node = heap[i];               // save top node
202
 
    int j = i << 1;                               // find smaller child
203
 
    int k = j + 1;
204
 
    if ((k <= size) && (heap[k].doc < heap[j].doc)) {
205
 
      j = k;
206
 
    }
207
 
    while ((j <= size) && (heap[j].doc < node.doc)) {
208
 
      heap[i] = heap[j];                          // shift up child
209
 
      i = j;
210
 
      j = i << 1;
211
 
      k = j + 1;
212
 
      if (k <= size && (heap[k].doc < heap[j].doc)) {
213
 
        j = k;
214
 
      }
215
 
    }
216
 
    heap[i] = node;                               // install saved node
217
 
    topHSD = heap[1];
218
 
  }
219
 
}