beagled/Lucene.Net/Search/FieldSortedHitQueue.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
  17 using System;
  18 using IndexReader = Lucene.Net.Index.IndexReader;
  19 using PriorityQueue = Lucene.Net.Util.PriorityQueue;
  20
  21 namespace Lucene.Net.Search
  22 {
  23
  24         /// <summary> Expert: A hit queue for sorting by hits by terms in more than one field.
  25         /// Uses <code>FieldCache.DEFAULT</code> for maintaining internal term lookup tables.
  26         ///
  27         /// <p>Created: Dec 8, 2003 12:56:03 PM
  28         ///
  29         /// </summary>
  30         /// <author>   Tim Jones (Nacimiento Software)
  31         /// </author>
  32         /// <since>   lucene 1.4
  33         /// </since>
  34         /// <version>  $Id: FieldSortedHitQueue.cs,v 1.3 2006/10/02 17:09:04 joeshaw Exp $
  35         /// </version>
  36         /// <seealso cref="Searcher.Search(Query,Filter,int,Sort)">
  37         /// </seealso>
  38         /// <seealso cref="FieldCache">
  39         /// </seealso>
  40         class FieldSortedHitQueue : PriorityQueue
  41         {
  42                 private class AnonymousClassScoreDocComparator : ScoreDocComparator
  43                 {
  44                         public AnonymousClassScoreDocComparator(int[] fieldOrder)
  45                         {
  46                                 InitBlock(fieldOrder);
  47                         }
  48                         private void  InitBlock(int[] fieldOrder)
  49                         {
  50                                 this.fieldOrder = fieldOrder;
  51                         }
  52
  53             private int[] fieldOrder;
  54
  55                         public int Compare(ScoreDoc i, ScoreDoc j)
  56                         {
  57                                 int fi = fieldOrder[i.doc];
  58                                 int fj = fieldOrder[j.doc];
  59                                 if (fi < fj)
  60                                         return - 1;
  61                                 if (fi > fj)
  62                                         return 1;
  63                                 return 0;
  64                         }
  65
  66                         public virtual System.IComparable SortValue(ScoreDoc i)
  67                         {
  68                                 return (System.Int32) fieldOrder[i.doc];
  69                         }
  70
  71                         public virtual int SortType()
  72                         {
  73                                 return SortField.INT;
  74                         }
  75                 }
  76                 private class AnonymousClassScoreDocComparator1 : ScoreDocComparator
  77                 {
  78                         public AnonymousClassScoreDocComparator1(float[] fieldOrder)
  79                         {
  80                                 InitBlock(fieldOrder);
  81                         }
  82                         private void  InitBlock(float[] fieldOrder)
  83                         {
  84                                 this.fieldOrder = fieldOrder;
  85                         }
  86                         private float[] fieldOrder;
  87
  88                         public int Compare(ScoreDoc i, ScoreDoc j)
  89                         {
  90                                 float fi = fieldOrder[i.doc];
  91                                 float fj = fieldOrder[j.doc];
  92                                 if (fi < fj)
  93                                         return - 1;
  94                                 if (fi > fj)
  95                                         return 1;
  96                                 return 0;
  97                         }
  98
  99                         public virtual System.IComparable SortValue(ScoreDoc i)
 100                         {
 101                                 return (float) fieldOrder[i.doc];
 102                         }
 103
 104                         public virtual int SortType()
 105                         {
 106                                 return SortField.FLOAT;
 107                         }
 108                 }
 109                 private class AnonymousClassScoreDocComparator2 : ScoreDocComparator
 110                 {
 111                         public AnonymousClassScoreDocComparator2(Lucene.Net.Search.StringIndex index)
 112                         {
 113                                 InitBlock(index);
 114                         }
 115                         private void  InitBlock(Lucene.Net.Search.StringIndex index)
 116                         {
 117                                 this.index = index;
 118                         }
 119                         private Lucene.Net.Search.StringIndex index;
 120
 121                         public int Compare(ScoreDoc i, ScoreDoc j)
 122                         {
 123                                 int fi = index.order[i.doc];
 124                                 int fj = index.order[j.doc];
 125                                 if (fi < fj)
 126                                         return - 1;
 127                                 if (fi > fj)
 128                                         return 1;
 129                                 return 0;
 130                         }
 131
 132                         public virtual System.IComparable SortValue(ScoreDoc i)
 133                         {
 134                                 return index.lookup[index.order[i.doc]];
 135                         }
 136
 137                         public virtual int SortType()
 138                         {
 139                                 return SortField.STRING;
 140                         }
 141                 }
 142                 private class AnonymousClassScoreDocComparator3 : ScoreDocComparator
 143                 {
 144                         public AnonymousClassScoreDocComparator3(System.Globalization.CompareInfo collator, System.String[] index)
 145                         {
 146                                 InitBlock(collator, index);
 147                         }
 148                         private void  InitBlock(System.Globalization.CompareInfo collator, System.String[] index)
 149                         {
 150                                 this.collator = collator;
 151                                 this.index = index;
 152                         }
 153                         private System.Globalization.CompareInfo collator;
 154                         private System.String[] index;
 155
 156                         public int Compare(ScoreDoc i, ScoreDoc j)
 157                         {
 158                                 return collator.Compare(index[i.doc].ToString(), index[j.doc].ToString());
 159                         }
 160
 161                         public virtual System.IComparable SortValue(ScoreDoc i)
 162                         {
 163                                 return index[i.doc];
 164                         }
 165
 166                         public virtual int SortType()
 167                         {
 168                                 return SortField.STRING;
 169                         }
 170                 }
 171
 172                 /// <summary> Creates a hit queue sorted by the given list of fields.</summary>
 173                 /// <param name="reader"> Index to use.
 174                 /// </param>
 175                 /// <param name="fields">Field names, in priority order (highest priority first).  Cannot be <code>null</code> or empty.
 176                 /// </param>
 177                 /// <param name="size"> The number of hits to retain.  Must be greater than zero.
 178                 /// </param>
 179                 /// <throws>  IOException </throws>
 180                 internal FieldSortedHitQueue(IndexReader reader, SortField[] fields, int size)
 181                 {
 182                         int n = fields.Length;
 183                         comparators = new ScoreDocComparator[n];
 184                         this.fields = new SortField[n];
 185                         for (int i = 0; i < n; ++i)
 186                         {
 187                                 System.String fieldname = fields[i].GetField();
 188                                 comparators[i] = GetCachedComparator(reader, fieldname, fields[i].GetType(), fields[i].GetLocale(), fields[i].GetFactory());
 189                                 this.fields[i] = new SortField(fieldname, comparators[i].SortType(), fields[i].GetReverse());
 190                         }
 191                         Initialize(size);
 192                 }
 193
 194
 195                 /// <summary>Stores a comparator corresponding to each field being sorted by </summary>
 196                 protected internal ScoreDocComparator[] comparators;
 197
 198                 /// <summary>Stores the sort criteria being used. </summary>
 199                 protected internal SortField[] fields;
 200
 201                 /// <summary>Stores the maximum score value encountered, needed for normalizing. </summary>
 202                 protected internal float maxscore = System.Single.NegativeInfinity;
 203
 204                 /// <summary>returns the maximum score encountered by elements inserted via insert()</summary>
 205                 public virtual float GetMaxScore()
 206                 {
 207                         return maxscore;
 208                 }
 209
 210                 // The signature of this method takes a FieldDoc in order to avoid
 211                 // the unneeded cast to retrieve the score.
 212                 // inherit javadoc
 213                 public virtual bool Insert(FieldDoc fdoc)
 214                 {
 215                         maxscore = System.Math.Max(maxscore, fdoc.score);
 216                         return base.Insert(fdoc);
 217                 }
 218
 219                 // This overrides PriorityQueue.insert() so that insert(FieldDoc) that
 220                 // keeps track of the score isn't accidentally bypassed.
 221                 // inherit javadoc
 222                 public override bool Insert(System.Object fdoc)
 223                 {
 224                         return Insert((FieldDoc) fdoc);
 225                 }
 226
 227                 /// <summary> Returns whether <code>a</code> is less relevant than <code>b</code>.</summary>
 228                 /// <param name="a">ScoreDoc
 229                 /// </param>
 230                 /// <param name="b">ScoreDoc
 231                 /// </param>
 232                 /// <returns> <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>.
 233                 /// </returns>
 234                 public override bool LessThan(System.Object a, System.Object b)
 235                 {
 236                         ScoreDoc docA = (ScoreDoc) a;
 237                         ScoreDoc docB = (ScoreDoc) b;
 238
 239                         // run comparators
 240                         int n = comparators.Length;
 241                         int c = 0;
 242                         for (int i = 0; i < n && c == 0; ++i)
 243                         {
 244                                 c = (fields[i].reverse)?comparators[i].Compare(docB, docA):comparators[i].Compare(docA, docB);
 245                         }
 246                         // avoid random sort order that could lead to duplicates (bug #31241):
 247                         if (c == 0)
 248                                 return docA.doc > docB.doc;
 249                         return c > 0;
 250                 }
 251
 252
 253                 /// <summary> Given a FieldDoc object, stores the values used
 254                 /// to sort the given document.  These values are not the raw
 255                 /// values out of the index, but the internal representation
 256                 /// of them.  This is so the given search hit can be collated
 257                 /// by a MultiSearcher with other search hits.
 258                 /// </summary>
 259                 /// <param name="doc"> The FieldDoc to store sort values into.
 260                 /// </param>
 261                 /// <returns>  The same FieldDoc passed in.
 262                 /// </returns>
 263                 /// <seealso cref="Searchable.Search(Weight,Filter,int,Sort)">
 264                 /// </seealso>
 265                 internal virtual FieldDoc FillFields(FieldDoc doc)
 266                 {
 267                         int n = comparators.Length;
 268                         System.IComparable[] fields = new System.IComparable[n];
 269                         for (int i = 0; i < n; ++i)
 270                                 fields[i] = comparators[i].SortValue(doc);
 271                         doc.fields = fields;
 272                         //if (maxscore > 1.0f) doc.score /= maxscore;   // normalize scores
 273                         return doc;
 274                 }
 275
 276
 277                 /// <summary>Returns the SortFields being used by this hit queue. </summary>
 278                 internal virtual SortField[] GetFields()
 279                 {
 280                         return fields;
 281                 }
 282
 283                 /// <summary>Internal cache of comparators. Similar to FieldCache, only
 284                 /// caches comparators instead of term values.
 285                 /// </summary>
 286                 internal static readonly System.Collections.IDictionary Comparators = new System.Collections.Hashtable();
 287
 288                 /// <summary>Returns a comparator if it is in the cache. </summary>
 289                 internal static ScoreDocComparator Lookup(IndexReader reader, System.String field, int type, System.Object factory)
 290                 {
 291                         FieldCacheImpl.Entry entry = (factory != null) ? new FieldCacheImpl.Entry(field, factory) : new FieldCacheImpl.Entry(field, type);
 292                         lock (Comparators.SyncRoot)
 293                         {
 294                                 System.Collections.Hashtable readerCache = (System.Collections.Hashtable) Comparators[reader];
 295                                 if (readerCache == null)
 296                                         return null;
 297                                 return (ScoreDocComparator) readerCache[entry];
 298                         }
 299                 }
 300
 301                 /// <summary>Stores a comparator into the cache. </summary>
 302                 internal static System.Object Store(IndexReader reader, System.String field, int type, System.Object factory, System.Object value_Renamed)
 303                 {
 304                         FieldCacheImpl.Entry entry = (factory != null) ? new FieldCacheImpl.Entry(field, factory) : new FieldCacheImpl.Entry(field, type);
 305                         lock (Comparators.SyncRoot)
 306                         {
 307                                 System.Collections.Hashtable readerCache = (System.Collections.Hashtable) Comparators[reader];
 308                                 if (readerCache == null)
 309                                 {
 310                                         readerCache = new System.Collections.Hashtable();
 311                                         Comparators[reader] = readerCache;
 312                                 }
 313                                 System.Object tempObject;
 314                                 tempObject = readerCache[entry];
 315                                 readerCache[entry] = value_Renamed;
 316                                 return tempObject;
 317                         }
 318                 }
 319
 320                 internal static ScoreDocComparator GetCachedComparator(IndexReader reader, System.String fieldname, int type, System.Globalization.CultureInfo locale, SortComparatorSource factory)
 321                 {
 322                         if (type == SortField.DOC)
 323                                 return Lucene.Net.Search.ScoreDocComparator_Fields.INDEXORDER;
 324                         if (type == SortField.SCORE)
 325                                 return Lucene.Net.Search.ScoreDocComparator_Fields.RELEVANCE;
 326                         ScoreDocComparator comparator = Lookup(reader, fieldname, type, factory);
 327                         if (comparator == null)
 328                         {
 329                                 switch (type)
 330                                 {
 331
 332                                         case SortField.AUTO:
 333                                                 comparator = ComparatorAuto(reader, fieldname);
 334                                                 break;
 335
 336                                         case SortField.INT:
 337                                                 comparator = ComparatorInt(reader, fieldname);
 338                                                 break;
 339
 340                                         case SortField.FLOAT:
 341                                                 comparator = ComparatorFloat(reader, fieldname);
 342                                                 break;
 343
 344                                         case SortField.STRING:
 345                                                 if (locale != null)
 346                                                         comparator = ComparatorStringLocale(reader, fieldname, locale);
 347                                                 else
 348                                                         comparator = ComparatorString(reader, fieldname);
 349                                                 break;
 350
 351                                         case SortField.CUSTOM:
 352                                                 comparator = factory.NewComparator(reader, fieldname);
 353                                                 break;
 354
 355                                         default:
 356                                                 throw new System.SystemException("unknown field type: " + type);
 357
 358                                 }
 359                                 Store(reader, fieldname, type, factory, comparator);
 360                         }
 361                         return comparator;
 362                 }
 363
 364                 /// <summary> Returns a comparator for sorting hits according to a field containing integers.</summary>
 365                 /// <param name="reader"> Index to use.
 366                 /// </param>
 367                 /// <param name="fieldname"> Field containg integer values.
 368                 /// </param>
 369                 /// <returns>  Comparator for sorting hits.
 370                 /// </returns>
 371                 /// <throws>  IOException If an error occurs reading the index. </throws>
 372                 internal static ScoreDocComparator ComparatorInt(IndexReader reader, System.String fieldname)
 373                 {
 374                         System.String field = String.Intern(fieldname);
 375                         int[] fieldOrder = Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetInts(reader, field);
 376                         return new AnonymousClassScoreDocComparator(fieldOrder);
 377                 }
 378
 379                 /// <summary> Returns a comparator for sorting hits according to a field containing floats.</summary>
 380                 /// <param name="reader"> Index to use.
 381                 /// </param>
 382                 /// <param name="fieldname"> Field containg float values.
 383                 /// </param>
 384                 /// <returns>  Comparator for sorting hits.
 385                 /// </returns>
 386                 /// <throws>  IOException If an error occurs reading the index. </throws>
 387                 internal static ScoreDocComparator ComparatorFloat(IndexReader reader, System.String fieldname)
 388                 {
 389                         System.String field = String.Intern(fieldname);
 390                         float[] fieldOrder = Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetFloats(reader, field);
 391                         return new AnonymousClassScoreDocComparator1(fieldOrder);
 392                 }
 393
 394                 /// <summary> Returns a comparator for sorting hits according to a field containing strings.</summary>
 395                 /// <param name="reader"> Index to use.
 396                 /// </param>
 397                 /// <param name="fieldname"> Field containg string values.
 398                 /// </param>
 399                 /// <returns>  Comparator for sorting hits.
 400                 /// </returns>
 401                 /// <throws>  IOException If an error occurs reading the index. </throws>
 402                 internal static ScoreDocComparator ComparatorString(IndexReader reader, System.String fieldname)
 403                 {
 404                         System.String field = String.Intern(fieldname);
 405                         Lucene.Net.Search.StringIndex index = Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetStringIndex(reader, field);
 406                         return new AnonymousClassScoreDocComparator2(index);
 407                 }
 408
 409                 /// <summary> Returns a comparator for sorting hits according to a field containing strings.</summary>
 410                 /// <param name="reader"> Index to use.
 411                 /// </param>
 412                 /// <param name="fieldname"> Field containg string values.
 413                 /// </param>
 414                 /// <returns>  Comparator for sorting hits.
 415                 /// </returns>
 416                 /// <throws>  IOException If an error occurs reading the index. </throws>
 417                 internal static ScoreDocComparator ComparatorStringLocale(IndexReader reader, System.String fieldname, System.Globalization.CultureInfo locale)
 418                 {
 419                         System.Globalization.CompareInfo collator = locale.CompareInfo;
 420                         System.String field = String.Intern(fieldname);
 421                         System.String[] index = Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetStrings(reader, field);
 422                         return new AnonymousClassScoreDocComparator3(collator, index);
 423                 }
 424
 425                 /// <summary> Returns a comparator for sorting hits according to values in the given field.
 426                 /// The terms in the field are looked at to determine whether they contain integers,
 427                 /// floats or strings.  Once the type is determined, one of the other static methods
 428                 /// in this class is called to get the comparator.
 429                 /// </summary>
 430                 /// <param name="reader"> Index to use.
 431                 /// </param>
 432                 /// <param name="fieldname"> Field containg values.
 433                 /// </param>
 434                 /// <returns>  Comparator for sorting hits.
 435                 /// </returns>
 436                 /// <throws>  IOException If an error occurs reading the index. </throws>
 437                 internal static ScoreDocComparator ComparatorAuto(IndexReader reader, System.String fieldname)
 438                 {
 439                         System.String field = String.Intern(fieldname);
 440                         System.Object lookupArray = Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetAuto(reader, field);
 441                         if (lookupArray is Lucene.Net.Search.StringIndex)
 442                         {
 443                                 return ComparatorString(reader, field);
 444                         }
 445                         else if (lookupArray is int[])
 446                         {
 447                                 return ComparatorInt(reader, field);
 448                         }
 449                         else if (lookupArray is float[])
 450                         {
 451                                 return ComparatorFloat(reader, field);
 452                         }
 453                         else if (lookupArray is System.String[])
 454                         {
 455                                 return ComparatorString(reader, field);
 456                         }
 457                         else
 458                         {
 459                                 throw new System.SystemException("unknown data type in field '" + field + "'");
 460                         }
 461                 }
 462         }
 463 }