/*
* 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 Lucene.Net.Support;
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 = Number.URShift(i, 1);
while ((j > 0) && (node.doc < heap[j].doc))
{
heap[i] = heap[j]; // shift parents down
i = j;
j = 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];
}
}
}