beagled/Lucene.Net/Search/BooleanScorer.cs

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