beagled/Lucene.Net/Search/BooleanScorer.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         sealed class BooleanScorer : Scorer
  23         {
  24                 private void  InitBlock()
  25                 {
  26                         bucketTable = new BucketTable(this);
  27                 }
  28                 private SubScorer scorers = null;
  29                 private BucketTable bucketTable;
  30
  31                 private int maxCoord = 1;
  32                 private float[] coordFactors = null;
  33
  34                 private int requiredMask = 0;
  35                 private int prohibitedMask = 0;
  36                 private int nextMask = 1;
  37
  38                 internal BooleanScorer(Similarity similarity) : base(similarity)
  39                 {
  40                         InitBlock();
  41                 }
  42
  43                 internal sealed class SubScorer
  44                 {
  45                         public Scorer scorer;
  46                         public bool done;
  47                         public bool required = false;
  48                         public bool prohibited = false;
  49                         public HitCollector collector;
  50                         public SubScorer next;
  51
  52                         public SubScorer(Scorer scorer, bool required, bool prohibited, HitCollector collector, SubScorer next)
  53                         {
  54                                 this.scorer = scorer;
  55                                 this.done = !scorer.Next();
  56                                 this.required = required;
  57                                 this.prohibited = prohibited;
  58                                 this.collector = collector;
  59                                 this.next = next;
  60                         }
  61                 }
  62
  63                 internal void  Add(Scorer scorer, bool required, bool prohibited)
  64                 {
  65                         int mask = 0;
  66                         if (required || prohibited)
  67                         {
  68                                 if (nextMask == 0)
  69                                         throw new System.IndexOutOfRangeException("More than 32 required/prohibited clauses in query.");
  70                                 mask = nextMask;
  71                                 nextMask = nextMask << 1;
  72                         }
  73                         else
  74                                 mask = 0;
  75
  76                         if (!prohibited)
  77                                 maxCoord++;
  78
  79                         if (prohibited)
  80                                 prohibitedMask |= mask;
  81                         // update prohibited mask
  82                         else if (required)
  83                                 requiredMask |= mask; // update required mask
  84
  85                         scorers = new SubScorer(scorer, required, prohibited, bucketTable.NewCollector(mask), scorers);
  86                 }
  87
  88                 private void  ComputeCoordFactors()
  89                 {
  90                         coordFactors = new float[maxCoord];
  91                         for (int i = 0; i < maxCoord; i++)
  92                                 coordFactors[i] = GetSimilarity().Coord(i, maxCoord - 1);
  93                 }
  94
  95                 private int end;
  96                 private Bucket current;
  97
  98                 public override void  Score(HitCollector hc)
  99                 {
 100                         Next();
 101                         Score(hc, System.Int32.MaxValue);
 102                 }
 103
 104                 protected internal override bool Score(HitCollector hc, int max)
 105                 {
 106                         if (coordFactors == null)
 107                                 ComputeCoordFactors();
 108
 109                         bool more;
 110                         Bucket tmp;
 111
 112                         do
 113                         {
 114                                 bucketTable.first = null;
 115
 116                                 while (current != null)
 117                                 {
 118                                         // more queued
 119
 120                                         // check prohibited & required
 121                                         if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask)
 122                                         {
 123
 124                                                 if (current.doc >= max)
 125                                                 {
 126                                                         tmp = current;
 127                                                         current = current.next;
 128                                                         tmp.next = bucketTable.first;
 129                                                         bucketTable.first = tmp;
 130                                                         continue;
 131                                                 }
 132
 133                                                 hc.Collect(current.doc, current.score * coordFactors[current.coord]);
 134                                         }
 135
 136                                         current = current.next; // pop the queue
 137                                 }
 138
 139                                 if (bucketTable.first != null)
 140                                 {
 141                                         current = bucketTable.first;
 142                                         bucketTable.first = current.next;
 143                                         return true;
 144                                 }
 145
 146                                 // refill the queue
 147                                 more = false;
 148                                 end += BucketTable.SIZE;
 149                                 for (SubScorer sub = scorers; sub != null; sub = sub.next)
 150                                 {
 151                                         if (!sub.done)
 152                                         {
 153                                                 sub.done = !sub.scorer.Score(sub.collector, end);
 154                                                 if (!sub.done)
 155                                                         more = true;
 156                                         }
 157                                 }
 158                                 current = bucketTable.first;
 159                         }
 160                         while (current != null || more);
 161
 162                         return false;
 163                 }
 164
 165                 public override int Doc()
 166                 {
 167                         return current.doc;
 168                 }
 169
 170                 public override bool Next()
 171                 {
 172                         bool more;
 173                         do
 174                         {
 175                                 while (bucketTable.first != null)
 176                                 {
 177                                         // more queued
 178                                         current = bucketTable.first;
 179                                         bucketTable.first = current.next; // pop the queue
 180
 181                                         // check prohibited & required
 182                                         if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask)
 183                                         {
 184                                                 return true;
 185                                         }
 186                                 }
 187
 188                                 // refill the queue
 189                                 more = false;
 190                                 end += BucketTable.SIZE;
 191                                 for (SubScorer sub = scorers; sub != null; sub = sub.next)
 192                                 {
 193                                         Scorer scorer = sub.scorer;
 194                                         while (!sub.done && scorer.Doc() < end)
 195                                         {
 196                                                 sub.collector.Collect(scorer.Doc(), scorer.Score());
 197                                                 sub.done = !scorer.Next();
 198                                         }
 199                                         if (!sub.done)
 200                                         {
 201                                                 more = true;
 202                                         }
 203                                 }
 204                         }
 205                         while (bucketTable.first != null || more);
 206
 207                         return false;
 208                 }
 209
 210                 public override float Score()
 211                 {
 212                         if (coordFactors == null)
 213                                 ComputeCoordFactors();
 214                         return current.score * coordFactors[current.coord];
 215                 }
 216
 217                 internal sealed class Bucket
 218                 {
 219                         internal int doc = - 1; // tells if bucket is valid
 220                         internal float score; // incremental score
 221                         internal int bits; // used for bool constraints
 222                         internal int coord; // count of terms in score
 223                         internal Bucket next; // next valid bucket
 224                 }
 225
 226                 /// <summary>A simple hash table of document scores within a range. </summary>
 227                 internal sealed class BucketTable
 228                 {
 229                         private void  InitBlock()
 230                         {
 231                                 buckets = new Bucket[SIZE];
 232                         }
 233                         public const int SIZE = 1 << 11;
 234                         public static readonly int MASK;
 235
 236                         internal Bucket[] buckets;
 237                         internal Bucket first = null; // head of valid list
 238
 239                         private BooleanScorer scorer;
 240
 241                         public BucketTable(BooleanScorer scorer)
 242                         {
 243                 InitBlock();
 244                                 this.scorer = scorer;
 245                         }
 246
 247                         public int Size()
 248                         {
 249                                 return SIZE;
 250                         }
 251
 252                         public HitCollector NewCollector(int mask)
 253                         {
 254                                 return new Collector(mask, this);
 255                         }
 256                         static BucketTable()
 257                         {
 258                                 MASK = SIZE - 1;
 259                         }
 260                 }
 261
 262                 internal sealed class Collector : HitCollector
 263                 {
 264                         private BucketTable bucketTable;
 265                         private int mask;
 266                         public Collector(int mask, BucketTable bucketTable)
 267                         {
 268                                 this.mask = mask;
 269                                 this.bucketTable = bucketTable;
 270                         }
 271                         public override void  Collect(int doc, float score)
 272                         {
 273                                 BucketTable table = bucketTable;
 274                                 int i = doc & Lucene.Net.Search.BooleanScorer.BucketTable.MASK;
 275                                 Bucket bucket = table.buckets[i];
 276                                 if (bucket == null)
 277                                         table.buckets[i] = bucket = new Bucket();
 278
 279                                 if (bucket.doc != doc)
 280                                 {
 281                                         // invalid bucket
 282                                         bucket.doc = doc; // set doc
 283                                         bucket.score = score; // initialize score
 284                                         bucket.bits = mask; // initialize mask
 285                                         bucket.coord = 1; // initialize coord
 286
 287                                         bucket.next = table.first; // push onto valid list
 288                                         table.first = bucket;
 289                                 }
 290                                 else
 291                                 {
 292                                         // valid bucket
 293                                         bucket.score += score; // increment score
 294                                         bucket.bits |= mask; // add bits in mask
 295                                         bucket.coord++; // increment coord
 296                                 }
 297                         }
 298                 }
 299
 300                 public override bool SkipTo(int target)
 301                 {
 302                         throw new System.NotSupportedException();
 303                 }
 304
 305                 public override Explanation Explain(int doc)
 306                 {
 307                         throw new System.NotSupportedException();
 308                 }
 309
 310                 public override System.String ToString()
 311                 {
 312                         System.Text.StringBuilder buffer = new System.Text.StringBuilder();
 313                         buffer.Append("boolean(");
 314                         for (SubScorer sub = scorers; sub != null; sub = sub.next)
 315                         {
 316                                 buffer.Append(sub.scorer.ToString());
 317                                 buffer.Append(" ");
 318                         }
 319                         buffer.Append(")");
 320                         return buffer.ToString();
 321                 }
 322         }
 323 }