lucene-java-3.5.0/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 }