/*
* 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.
*/
using System;
namespace Lucene.Net.Search
{
/// The Scorer for DisjunctionMaxQuery's. The union of all documents generated by the the subquery scorers
/// is generated in document number order. The score for each document is the maximum of the scores computed
/// by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
/// for the other subqueries that generate the document.
///
/// Chuck Williams
///
class DisjunctionMaxScorer : Scorer
{
/* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
private System.Collections.ArrayList subScorers = new System.Collections.ArrayList();
/* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
private float tieBreakerMultiplier;
private bool more = false; // True iff there is a next document
private bool firstTime = true; // True iff next() has not yet been called
/// Creates a new instance of DisjunctionMaxScorer
/// Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result.
///
/// -- not used since our definition involves neither coord nor terms directly
///
public DisjunctionMaxScorer(float tieBreakerMultiplier, Similarity similarity) : base(similarity)
{
this.tieBreakerMultiplier = tieBreakerMultiplier;
}
/// Add the scorer for a subquery
/// the scorer of a subquery of our associated DisjunctionMaxQuery
///
public virtual void Add(Scorer scorer)
{
if (scorer.Next())
{
// Initialize and retain only if it produces docs
subScorers.Add(scorer);
more = true;
}
}
/// Generate the next document matching our associated DisjunctionMaxQuery.
/// true iff there is a next document
///
public override bool Next()
{
if (!more)
return false;
if (firstTime)
{
Heapify();
firstTime = false;
return true; // more would have been false if no subScorers had any docs
}
// Increment all generators that generated the last doc and adjust the heap.
int lastdoc = ((Scorer) subScorers[0]).Doc();
do
{
if (((Scorer) subScorers[0]).Next())
HeapAdjust(0);
else
{
HeapRemoveRoot();
if ((subScorers.Count == 0))
return (more = false);
}
}
while (((Scorer) subScorers[0]).Doc() == lastdoc);
return true;
}
/// Determine the current document number. Initially invalid, until {@link #Next()} is called the first time.
/// the document number of the currently generated document
///
public override int Doc()
{
return ((Scorer) subScorers[0]).Doc();
}
/// Determine the current document score. Initially invalid, until {@link #Next()} is called the first time.
/// the score of the current generated document
///
public override float Score()
{
int doc = ((Scorer) subScorers[0]).Doc();
float[] sum = new float[]{((Scorer) subScorers[0]).Score()}, max = new float[]{sum[0]};
int size = subScorers.Count;
ScoreAll(1, size, doc, sum, max);
ScoreAll(2, size, doc, sum, max);
return max[0] + (sum[0] - max[0]) * tieBreakerMultiplier;
}
// Recursively iterate all subScorers that generated last doc computing sum and max
private void ScoreAll(int root, int size, int doc, float[] sum, float[] max)
{
if (root < size && ((Scorer) subScorers[root]).Doc() == doc)
{
float sub = ((Scorer) subScorers[root]).Score();
sum[0] += sub;
max[0] = System.Math.Max(max[0], sub);
ScoreAll((root << 1) + 1, size, doc, sum, max);
ScoreAll((root << 1) + 2, size, doc, sum, max);
}
}
/// Advance to the first document beyond the current whose number is greater than or equal to target.
/// the minimum number of the next desired document
///
/// true iff there is a document to be generated whose number is at least target
///
public override bool SkipTo(int target)
{
if (firstTime)
{
if (!more)
return false;
Heapify();
firstTime = false;
}
while (subScorers.Count > 0 && ((Scorer) subScorers[0]).Doc() < target)
{
if (((Scorer) subScorers[0]).SkipTo(target))
HeapAdjust(0);
else
HeapRemoveRoot();
}
if ((subScorers.Count == 0))
return (more = false);
return true;
}
/// Explain a score that we computed. UNSUPPORTED -- see explanation capability in DisjunctionMaxQuery.
/// the number of a document we scored
///
/// the Explanation for our score
///
public override Explanation Explain(int doc)
{
throw new System.NotSupportedException();
}
// Organize subScorers into a min heap with scorers generating the earlest document on top.
private void Heapify()
{
int size = subScorers.Count;
for (int i = (size >> 1) - 1; i >= 0; i--)
HeapAdjust(i);
}
/* The subtree of subScorers at root is a min heap except possibly for its root element.
* Bubble the root down as required to make the subtree a heap.
*/
private void HeapAdjust(int root)
{
Scorer scorer = (Scorer) subScorers[root];
int doc = scorer.Doc();
int i = root, size = subScorers.Count;
while (i <= (size >> 1) - 1)
{
int lchild = (i << 1) + 1;
Scorer lscorer = (Scorer) subScorers[lchild];
int ldoc = lscorer.Doc();
int rdoc = System.Int32.MaxValue, rchild = (i << 1) + 2;
Scorer rscorer = null;
if (rchild < size)
{
rscorer = (Scorer) subScorers[rchild];
rdoc = rscorer.Doc();
}
if (ldoc < doc)
{
if (rdoc < ldoc)
{
subScorers[i] = rscorer;
subScorers[rchild] = scorer;
i = rchild;
}
else
{
subScorers[i] = lscorer;
subScorers[lchild] = scorer;
i = lchild;
}
}
else if (rdoc < doc)
{
subScorers[i] = rscorer;
subScorers[rchild] = scorer;
i = rchild;
}
else
return ;
}
}
// Remove the root Scorer from subScorers and re-establish it as a heap
private void HeapRemoveRoot()
{
int size = subScorers.Count;
if (size == 1)
subScorers.RemoveAt(0);
else
{
subScorers[0] = subScorers[size - 1];
subScorers.RemoveAt(size - 1);
HeapAdjust(0);
}
}
}
}