/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /* Derived from Lucene.Net.Util.PriorityQueue of March 2005 */ using System; using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator; using Scorer = Lucene.Net.Search.Scorer; namespace Lucene.Net.Util { /// 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(). /// public class ScorerDocQueue { // later: SpansQueue for spans with doc and term positions private HeapedScorerDoc[] heap; private int maxSize; private int size; private class HeapedScorerDoc { private void InitBlock(ScorerDocQueue enclosingInstance) { this.enclosingInstance = enclosingInstance; } private ScorerDocQueue enclosingInstance; public ScorerDocQueue Enclosing_Instance { get { return enclosingInstance; } } internal Scorer scorer; internal int doc; internal HeapedScorerDoc(ScorerDocQueue enclosingInstance, Scorer s):this(enclosingInstance, s, s.DocID()) { } internal HeapedScorerDoc(ScorerDocQueue enclosingInstance, Scorer scorer, int doc) { InitBlock(enclosingInstance); this.scorer = scorer; this.doc = doc; } internal virtual void Adjust() { doc = scorer.DocID(); } } private HeapedScorerDoc topHSD; // same as heap[1], only for speed /// Create a ScorerDocQueue with a maximum size. public ScorerDocQueue(int maxSize) { // assert maxSize >= 0; size = 0; int heapSize = maxSize + 1; heap = new HeapedScorerDoc[heapSize]; this.maxSize = maxSize; topHSD = heap[1]; // initially null } /// Adds a Scorer to a ScorerDocQueue in log(size) time. /// If one tries to add more Scorers than maxSize /// a RuntimeException (ArrayIndexOutOfBound) is thrown. /// public void Put(Scorer scorer) { size++; heap[size] = new HeapedScorerDoc(this, scorer); UpHeap(); } /// Adds a Scorer to the ScorerDocQueue in log(size) time if either /// the ScorerDocQueue is not full, or not lessThan(scorer, top()). /// /// /// /// true if scorer is added, false otherwise. /// public virtual bool Insert(Scorer scorer) { if (size < maxSize) { Put(scorer); return true; } else { int docNr = scorer.DocID(); if ((size > 0) && (!(docNr < topHSD.doc))) { // heap[1] is top() heap[1] = new HeapedScorerDoc(this, scorer, docNr); DownHeap(); return true; } else { return false; } } } /// Returns the least Scorer of the ScorerDocQueue in constant time. /// Should not be used when the queue is empty. /// public Scorer Top() { // assert size > 0; return topHSD.scorer; } /// Returns document number of the least Scorer of the ScorerDocQueue /// in constant time. /// Should not be used when the queue is empty. /// public int TopDoc() { // assert size > 0; return topHSD.doc; } public float TopScore() { // assert size > 0; return topHSD.scorer.Score(); } public bool TopNextAndAdjustElsePop() { return CheckAdjustElsePop(topHSD.scorer.NextDoc() != DocIdSetIterator.NO_MORE_DOCS); } public bool TopSkipToAndAdjustElsePop(int target) { return CheckAdjustElsePop(topHSD.scorer.Advance(target) != DocIdSetIterator.NO_MORE_DOCS); } private bool CheckAdjustElsePop(bool cond) { if (cond) { // see also adjustTop topHSD.doc = topHSD.scorer.DocID(); } else { // see also popNoResult heap[1] = heap[size]; // move last to first heap[size] = null; size--; } DownHeap(); return cond; } /// Removes and returns the least scorer of the ScorerDocQueue in log(size) /// time. /// Should not be used when the queue is empty. /// public Scorer Pop() { // assert size > 0; Scorer result = topHSD.scorer; PopNoResult(); return result; } /// Removes the least scorer of the ScorerDocQueue in log(size) time. /// Should not be used when the queue is empty. /// private void PopNoResult() { heap[1] = heap[size]; // move last to first heap[size] = null; size--; DownHeap(); // adjust heap } /// 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); }
		/// 
///
public void AdjustTop() { // assert size > 0; topHSD.Adjust(); DownHeap(); } /// Returns the number of scorers currently stored in the ScorerDocQueue. public int Size() { return size; } /// Removes all entries from the ScorerDocQueue. public void Clear() { for (int i = 0; i <= size; i++) { heap[i] = null; } size = 0; } private void UpHeap() { int i = size; HeapedScorerDoc node = heap[i]; // save bottom node int j = SupportClass.Number.URShift(i, 1); while ((j > 0) && (node.doc < heap[j].doc)) { heap[i] = heap[j]; // shift parents down i = j; j = SupportClass.Number.URShift(j, 1); } heap[i] = node; // install saved node topHSD = heap[1]; } private void DownHeap() { 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]; } } }