beagled/Lucene.Net/Search/DisjunctionMaxScorer.cs

   1 /*
   2  * Copyright 2005 The Apache Software Foundation
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 using System;
  18
  19 namespace Lucene.Net.Search
  20 {
  21
  22         /// <summary> The Scorer for DisjunctionMaxQuery's.  The union of all documents generated by the the subquery scorers
  23         /// is generated in document number order.  The score for each document is the maximum of the scores computed
  24         /// by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
  25         /// for the other subqueries that generate the document.
  26         /// </summary>
  27         /// <author>  Chuck Williams
  28         /// </author>
  29         class DisjunctionMaxScorer : Scorer
  30         {
  31
  32                 /* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
  33                 private System.Collections.ArrayList subScorers = new System.Collections.ArrayList();
  34
  35                 /* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
  36                 private float tieBreakerMultiplier;
  37
  38                 private bool more = false; // True iff there is a next document
  39                 private bool firstTime = true; // True iff next() has not yet been called
  40
  41                 /// <summary>Creates a new instance of DisjunctionMaxScorer</summary>
  42                 /// <param name="tieBreakerMultiplier">Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result.
  43                 /// </param>
  44                 /// <param name="similarity">-- not used since our definition involves neither coord nor terms directly
  45                 /// </param>
  46                 public DisjunctionMaxScorer(float tieBreakerMultiplier, Similarity similarity) : base(similarity)
  47                 {
  48                         this.tieBreakerMultiplier = tieBreakerMultiplier;
  49                 }
  50
  51                 /// <summary>Add the scorer for a subquery</summary>
  52                 /// <param name="scorer">the scorer of a subquery of our associated DisjunctionMaxQuery
  53                 /// </param>
  54                 public virtual void  Add(Scorer scorer)
  55                 {
  56                         if (scorer.Next())
  57                         {
  58                                 // Initialize and retain only if it produces docs
  59                                 subScorers.Add(scorer);
  60                                 more = true;
  61                         }
  62                 }
  63
  64                 /// <summary>Generate the next document matching our associated DisjunctionMaxQuery.</summary>
  65                 /// <returns> true iff there is a next document
  66                 /// </returns>
  67                 public override bool Next()
  68                 {
  69                         if (!more)
  70                                 return false;
  71                         if (firstTime)
  72                         {
  73                                 Heapify();
  74                                 firstTime = false;
  75                                 return true; // more would have been false if no subScorers had any docs
  76                         }
  77                         // Increment all generators that generated the last doc and adjust the heap.
  78                         int lastdoc = ((Scorer) subScorers[0]).Doc();
  79                         do
  80                         {
  81                                 if (((Scorer) subScorers[0]).Next())
  82                                         HeapAdjust(0);
  83                                 else
  84                                 {
  85                                         HeapRemoveRoot();
  86                                         if ((subScorers.Count == 0))
  87                                                 return (more = false);
  88                                 }
  89                         }
  90                         while (((Scorer) subScorers[0]).Doc() == lastdoc);
  91                         return true;
  92                 }
  93
  94                 /// <summary>Determine the current document number.  Initially invalid, until {@link #Next()} is called the first time.</summary>
  95                 /// <returns> the document number of the currently generated document
  96                 /// </returns>
  97                 public override int Doc()
  98                 {
  99                         return ((Scorer) subScorers[0]).Doc();
 100                 }
 101
 102                 /// <summary>Determine the current document score.  Initially invalid, until {@link #Next()} is called the first time.</summary>
 103                 /// <returns> the score of the current generated document
 104                 /// </returns>
 105                 public override float Score()
 106                 {
 107                         int doc = ((Scorer) subScorers[0]).Doc();
 108                         float[] sum = new float[]{((Scorer) subScorers[0]).Score()}, max = new float[]{sum[0]};
 109                         int size = subScorers.Count;
 110                         ScoreAll(1, size, doc, sum, max);
 111                         ScoreAll(2, size, doc, sum, max);
 112                         return max[0] + (sum[0] - max[0]) * tieBreakerMultiplier;
 113                 }
 114
 115                 // Recursively iterate all subScorers that generated last doc computing sum and max
 116                 private void  ScoreAll(int root, int size, int doc, float[] sum, float[] max)
 117                 {
 118                         if (root < size && ((Scorer) subScorers[root]).Doc() == doc)
 119                         {
 120                                 float sub = ((Scorer) subScorers[root]).Score();
 121                                 sum[0] += sub;
 122                                 max[0] = System.Math.Max(max[0], sub);
 123                                 ScoreAll((root << 1) + 1, size, doc, sum, max);
 124                                 ScoreAll((root << 1) + 2, size, doc, sum, max);
 125                         }
 126                 }
 127
 128                 /// <summary>Advance to the first document beyond the current whose number is greater than or equal to target.</summary>
 129                 /// <param name="target">the minimum number of the next desired document
 130                 /// </param>
 131                 /// <returns> true iff there is a document to be generated whose number is at least target
 132                 /// </returns>
 133                 public override bool SkipTo(int target)
 134                 {
 135                         while (subScorers.Count > 0 && ((Scorer) subScorers[0]).Doc() < target)
 136                         {
 137                                 if (((Scorer) subScorers[0]).SkipTo(target))
 138                                         HeapAdjust(0);
 139                                 else
 140                                         HeapRemoveRoot();
 141                         }
 142                         if ((subScorers.Count == 0))
 143                                 return (more = false);
 144                         return true;
 145                 }
 146
 147                 /// <summary>Explain a score that we computed.  UNSUPPORTED -- see explanation capability in DisjunctionMaxQuery.</summary>
 148                 /// <param name="doc">the number of a document we scored
 149                 /// </param>
 150                 /// <returns> the Explanation for our score
 151                 /// </returns>
 152                 public override Explanation Explain(int doc)
 153                 {
 154                         throw new System.NotSupportedException();
 155                 }
 156
 157                 // Organize subScorers into a min heap with scorers generating the earlest document on top.
 158                 private void  Heapify()
 159                 {
 160                         int size = subScorers.Count;
 161                         for (int i = (size >> 1) - 1; i >= 0; i--)
 162                                 HeapAdjust(i);
 163                 }
 164
 165                 /* The subtree of subScorers at root is a min heap except possibly for its root element.
 166                 * Bubble the root down as required to make the subtree a heap.
 167                 */
 168                 private void  HeapAdjust(int root)
 169                 {
 170                         Scorer scorer = (Scorer) subScorers[root];
 171                         int doc = scorer.Doc();
 172                         int i = root, size = subScorers.Count;
 173                         while (i <= (size >> 1) - 1)
 174                         {
 175                                 int lchild = (i << 1) + 1;
 176                                 Scorer lscorer = (Scorer) subScorers[lchild];
 177                                 int ldoc = lscorer.Doc();
 178                                 int rdoc = System.Int32.MaxValue, rchild = (i << 1) + 2;
 179                                 Scorer rscorer = null;
 180                                 if (rchild < size)
 181                                 {
 182                                         rscorer = (Scorer) subScorers[rchild];
 183                                         rdoc = rscorer.Doc();
 184                                 }
 185                                 if (ldoc < doc)
 186                                 {
 187                                         if (rdoc < ldoc)
 188                                         {
 189                                                 subScorers[i] = rscorer;
 190                                                 subScorers[rchild] = scorer;
 191                                                 i = rchild;
 192                                         }
 193                                         else
 194                                         {
 195                                                 subScorers[i] = lscorer;
 196                                                 subScorers[lchild] = scorer;
 197                                                 i = lchild;
 198                                         }
 199                                 }
 200                                 else if (rdoc < doc)
 201                                 {
 202                                         subScorers[i] = rscorer;
 203                                         subScorers[rchild] = scorer;
 204                                         i = rchild;
 205                                 }
 206                                 else
 207                                         return ;
 208                         }
 209                 }
 210
 211                 // Remove the root Scorer from subScorers and re-establish it as a heap
 212                 private void  HeapRemoveRoot()
 213                 {
 214                         int size = subScorers.Count;
 215                         if (size == 1)
 216                                 subScorers.RemoveAt(0);
 217                         else
 218                         {
 219                                 subScorers[0] = subScorers[size - 1];
 220                                 subScorers.RemoveAt(size - 1);
 221                                 HeapAdjust(0);
 222                         }
 223                 }
 224         }
 225 }