FileDocCategorySizeDatePackage
ScorerDocQueue.javaAPI DocApache Lucene 2.1.06178Wed Feb 14 10:46:42 GMT 2007org.apache.lucene.util

ScorerDocQueue

public class ScorerDocQueue extends Object
A ScorerDocQueue maintains a partial ordering of its Scorers such that the least Scorer can always be found in constant time. Put()'s and pop()'s require log(size) time. The ordering is by Scorer.doc().

Fields Summary
private final HeapedScorerDoc[]
heap
private final int
maxSize
private int
size
private HeapedScorerDoc
topHSD
Constructors Summary
public ScorerDocQueue(int maxSize)
Create a ScorerDocQueue with a maximum size.

    // assert maxSize >= 0;
    size = 0;
    int heapSize = maxSize + 1;
    heap = new HeapedScorerDoc[heapSize];
    this.maxSize = maxSize;
    topHSD = heap[1]; // initially null
Methods Summary
public final voidadjustTop()
Should be called when the scorer at top changes doc() value. Still log(n) worst case, but it's at least twice as fast to 
{ pq.top().change(); pq.adjustTop(); }
instead of 
{ o = pq.pop(); o.change(); pq.push(o); }


    // assert size > 0;
    topHSD.adjust();
    downHeap();
private booleancheckAdjustElsePop(boolean cond)

    if (cond) { // see also adjustTop
      topHSD.doc = topHSD.scorer.doc();
    } else { // see also popNoResult
      heap[1] = heap[size]; // move last to first
      heap[size] = null;
      size--;
    }
    downHeap();
    return cond;
public final voidclear()
Removes all entries from the ScorerDocQueue.

    for (int i = 0; i <= size; i++) {
      heap[i] = null;
    }
    size = 0;
private final voiddownHeap()

    int i = 1;
    HeapedScorerDoc node = heap[i];	          // save top node
    int j = i << 1;				  // find smaller child
    int k = j + 1;
    if ((k <= size) && (heap[k].doc < heap[j].doc)) {
      j = k;
    }
    while ((j <= size) && (heap[j].doc < node.doc)) {
      heap[i] = heap[j];			  // shift up child
      i = j;
      j = i << 1;
      k = j + 1;
      if (k <= size && (heap[k].doc < heap[j].doc)) {
	j = k;
      }
    }
    heap[i] = node;				  // install saved node
    topHSD = heap[1];
public booleaninsert(org.apache.lucene.search.Scorer scorer)
Adds a Scorer to the ScorerDocQueue in log(size) time if either the ScorerDocQueue is not full, or not lessThan(scorer, top()).

param
scorer
return
true if scorer is added, false otherwise.

    if (size < maxSize) {
      put(scorer);
      return true;
    } else {
      int docNr = scorer.doc();
      if ((size > 0) && (! (docNr < topHSD.doc))) { // heap[1] is top()
        heap[1] = new HeapedScorerDoc(scorer, docNr);
        downHeap();
        return true;
      } else {
        return false;
      }
    }
public final org.apache.lucene.search.Scorerpop()
Removes and returns the least scorer of the ScorerDocQueue in log(size) time. Should not be used when the queue is empty.

    // assert size > 0;
    Scorer result = topHSD.scorer;
    popNoResult();
    return result;
private final voidpopNoResult()
Removes the least scorer of the ScorerDocQueue in log(size) time. Should not be used when the queue is empty.

    heap[1] = heap[size]; // move last to first
    heap[size] = null;
    size--;
    downHeap();	// adjust heap
public final voidput(org.apache.lucene.search.Scorer scorer)
Adds a Scorer to a ScorerDocQueue in log(size) time. If one tries to add more Scorers than maxSize a RuntimeException (ArrayIndexOutOfBound) is thrown.

    size++;
    heap[size] = new HeapedScorerDoc(scorer);
    upHeap();
public final intsize()
Returns the number of scorers currently stored in the ScorerDocQueue.

    return size;
public final org.apache.lucene.search.Scorertop()
Returns the least Scorer of the ScorerDocQueue in constant time. Should not be used when the queue is empty.

    // assert size > 0;
    return topHSD.scorer;
public final inttopDoc()
Returns document number of the least Scorer of the ScorerDocQueue in constant time. Should not be used when the queue is empty.

    // assert size > 0;
    return topHSD.doc;
public final booleantopNextAndAdjustElsePop()

    return checkAdjustElsePop( topHSD.scorer.next());
public final floattopScore()

    // assert size > 0;
    return topHSD.scorer.score();
public final booleantopSkipToAndAdjustElsePop(int target)

    return checkAdjustElsePop( topHSD.scorer.skipTo(target));
private final voidupHeap()

    int i = size;
    HeapedScorerDoc node = heap[i];		  // save bottom node
    int j = i >>> 1;
    while ((j > 0) && (node.doc < heap[j].doc)) {
      heap[i] = heap[j];			  // shift parents down
      i = j;
      j = j >>> 1;
    }
    heap[i] = node;				  // install saved node
    topHSD = heap[1];