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 int Doc()
  97                 {
  98                         return current.doc;
  99                 }
 100
 101                 public override bool Next()
 102                 {
 103                         bool more;
 104                         do
 105                         {
 106                                 while (bucketTable.first != null)
 107                                 {
 108                                         // more queued
 109                                         current = bucketTable.first;
 110                                         bucketTable.first = current.next; // pop the queue
 111
 112                                         // check prohibited & required
 113                                         if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask)
 114                                         {
 115                                                 return true;
 116                                         }
 117                 }
 118
 119                                 // refill the queue
 120                                 more = false;
 121                                 end += BucketTable.SIZE;
 122                                 for (SubScorer sub = scorers; sub != null; sub = sub.next)
 123                                 {
 124                                         Scorer scorer = sub.scorer;
 125                                         while (!sub.done && scorer.Doc() < end)
 126                                         {
 127                                                 sub.collector.Collect(scorer.Doc(), scorer.Score());
 128                                                 sub.done = !scorer.Next();
 129                                         }
 130                                         if (!sub.done)
 131                                         {
 132                                                 more = true;
 133                                         }
 134                                 }
 135                         }
 136                         while (bucketTable.first != null | more);
 137
 138                         return false;
 139                 }
 140
 141                 public override float Score()
 142                 {
 143                         if (coordFactors == null)
 144                                 ComputeCoordFactors();
 145                         return current.score * coordFactors[current.coord];
 146                 }
 147
 148                 internal sealed class Bucket
 149                 {
 150                         internal int doc = - 1; // tells if bucket is valid
 151                         internal float score; // incremental score
 152                         internal int bits; // used for bool constraints
 153                         internal int coord; // count of terms in score
 154                         internal Bucket next; // next valid bucket
 155                 }
 156
 157                 /// <summary>A simple hash table of document scores within a range. </summary>
 158                 internal sealed class BucketTable
 159                 {
 160                         private void  InitBlock()
 161                         {
 162                                 buckets = new Bucket[SIZE];
 163                         }
 164                         public const int SIZE = 1 << 10;
 165                         public static readonly int MASK;
 166
 167                         internal Bucket[] buckets;
 168                         internal Bucket first = null; // head of valid list
 169
 170                         private BooleanScorer scorer;
 171
 172                         public BucketTable(BooleanScorer scorer)
 173                         {
 174                 InitBlock();
 175                                 this.scorer = scorer;
 176                         }
 177
 178                         public int Size()
 179                         {
 180                                 return SIZE;
 181                         }
 182
 183                         public HitCollector NewCollector(int mask)
 184                         {
 185                                 return new Collector(mask, this);
 186                         }
 187                         static BucketTable()
 188                         {
 189                                 MASK = SIZE - 1;
 190                         }
 191                 }
 192
 193                 internal sealed class Collector : HitCollector
 194                 {
 195                         private BucketTable bucketTable;
 196                         private int mask;
 197                         public Collector(int mask, BucketTable bucketTable)
 198                         {
 199                                 this.mask = mask;
 200                                 this.bucketTable = bucketTable;
 201                         }
 202                         public override void  Collect(int doc, float score)
 203                         {
 204                                 BucketTable table = bucketTable;
 205                                 int i = doc & Lucene.Net.Search.BooleanScorer.BucketTable.MASK;
 206                                 Bucket bucket = table.buckets[i];
 207                                 if (bucket == null)
 208                                         table.buckets[i] = bucket = new Bucket();
 209
 210                                 if (bucket.doc != doc)
 211                                 {
 212                                         // invalid bucket
 213                                         bucket.doc = doc; // set doc
 214                                         bucket.score = score; // initialize score
 215                                         bucket.bits = mask; // initialize mask
 216                                         bucket.coord = 1; // initialize coord
 217
 218                                         bucket.next = table.first; // push onto valid list
 219                                         table.first = bucket;
 220                                 }
 221                                 else
 222                                 {
 223                                         // valid bucket
 224                                         bucket.score += score; // increment score
 225                                         bucket.bits |= mask; // add bits in mask
 226                                         bucket.coord++; // increment coord
 227                                 }
 228                         }
 229                 }
 230
 231                 public override bool SkipTo(int target)
 232                 {
 233                         throw new System.NotSupportedException();
 234                 }
 235
 236                 public override Explanation Explain(int doc)
 237                 {
 238                         throw new System.NotSupportedException();
 239                 }
 240
 241                 public override System.String ToString()
 242                 {
 243                         System.Text.StringBuilder buffer = new System.Text.StringBuilder();
 244                         buffer.Append("boolean(");
 245                         for (SubScorer sub = scorers; sub != null; sub = sub.next)
 246                         {
 247                                 buffer.Append(sub.scorer.ToString());
 248                                 buffer.Append(" ");
 249                         }
 250                         buffer.Append(")");
 251                         return buffer.ToString();
 252                 }
 253         }
 254 }