mcs/tools/monkeydoc/Lucene.Net/Lucene.Net/Search/FieldComparator.cs

   1 /*
   2  * Licensed to the Apache Software Foundation (ASF) under one or more
   3  * contributor license agreements.  See the NOTICE file distributed with
   4  * this work for additional information regarding copyright ownership.
   5  * The ASF licenses this file to You under the Apache License, Version 2.0
   6  * (the "License"); you may not use this file except in compliance with
   7  * the License.  You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 using System;
  19
  20 using IndexReader = Mono.Lucene.Net.Index.IndexReader;
  21 using ByteParser = Mono.Lucene.Net.Search.ByteParser;
  22 using DoubleParser = Mono.Lucene.Net.Search.DoubleParser;
  23 using FloatParser = Mono.Lucene.Net.Search.FloatParser;
  24 using IntParser = Mono.Lucene.Net.Search.IntParser;
  25 using LongParser = Mono.Lucene.Net.Search.LongParser;
  26 using ShortParser = Mono.Lucene.Net.Search.ShortParser;
  27 using StringIndex = Mono.Lucene.Net.Search.StringIndex;
  28
  29 namespace Mono.Lucene.Net.Search
  30 {
  31
  32         /// <summary> Expert: a FieldComparator compares hits so as to determine their
  33         /// sort order when collecting the top results with {@link
  34         /// TopFieldCollector}.  The concrete public FieldComparator
  35         /// classes here correspond to the SortField types.
  36         ///
  37         /// <p/>This API is designed to achieve high performance
  38         /// sorting, by exposing a tight interaction with {@link
  39         /// FieldValueHitQueue} as it visits hits.  Whenever a hit is
  40         /// competitive, it's enrolled into a virtual slot, which is
  41         /// an int ranging from 0 to numHits-1.  The {@link
  42         /// FieldComparator} is made aware of segment transitions
  43         /// during searching in case any internal state it's tracking
  44         /// needs to be recomputed during these transitions.<p/>
  45         ///
  46         /// <p/>A comparator must define these functions:<p/>
  47         ///
  48         /// <ul>
  49         ///
  50         /// <li> {@link #compare} Compare a hit at 'slot a'
  51         /// with hit 'slot b'.</li>
  52         ///
  53         /// <li> {@link #setBottom} This method is called by
  54         /// {@link FieldValueHitQueue} to notify the
  55         /// FieldComparator of the current weakest ("bottom")
  56         /// slot.  Note that this slot may not hold the weakest
  57         /// value according to your comparator, in cases where
  58         /// your comparator is not the primary one (ie, is only
  59         /// used to break ties from the comparators before it).</li>
  60         ///
  61         /// <li> {@link #compareBottom} Compare a new hit (docID)
  62         /// against the "weakest" (bottom) entry in the queue.</li>
  63         ///
  64         /// <li> {@link #copy} Installs a new hit into the
  65         /// priority queue.  The {@link FieldValueHitQueue}
  66         /// calls this method when a new hit is competitive.</li>
  67         ///
  68         /// <li> {@link #setNextReader} Invoked
  69         /// when the search is switching to the next segment.
  70         /// You may need to update internal state of the
  71         /// comparator, for example retrieving new values from
  72         /// the {@link FieldCache}.</li>
  73         ///
  74         /// <li> {@link #value} Return the sort value stored in
  75         /// the specified slot.  This is only called at the end
  76         /// of the search, in order to populate {@link
  77         /// FieldDoc#fields} when returning the top results.</li>
  78         /// </ul>
  79         ///
  80         /// <b>NOTE:</b> This API is experimental and might change in
  81         /// incompatible ways in the next release.
  82         /// </summary>
  83         public abstract class FieldComparator
  84         {
  85
  86                 /// <summary>Parses field's values as byte (using {@link
  87                 /// FieldCache#getBytes} and sorts by ascending value
  88                 /// </summary>
  89                 public sealed class ByteComparator:FieldComparator
  90                 {
  91                         private sbyte[] values;
  92                         private sbyte[] currentReaderValues;
  93                         private System.String field;
  94                         private ByteParser parser;
  95                         private sbyte bottom;
  96
  97                         internal ByteComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
  98                         {
  99                                 values = new sbyte[numHits];
 100                                 this.field = field;
 101                                 this.parser = (ByteParser) parser;
 102                         }
 103
 104                         public override int Compare(int slot1, int slot2)
 105                         {
 106                                 return values[slot1] - values[slot2];
 107                         }
 108
 109                         public override int CompareBottom(int doc)
 110                         {
 111                                 return bottom - currentReaderValues[doc];
 112                         }
 113
 114                         public override void  Copy(int slot, int doc)
 115                         {
 116                                 values[slot] = currentReaderValues[doc];
 117                         }
 118
 119                         public override void  SetNextReader(IndexReader reader, int docBase)
 120                         {
 121                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetBytes(reader, field, parser);
 122                         }
 123
 124                         public override void  SetBottom(int bottom)
 125                         {
 126                                 this.bottom = values[bottom];
 127                         }
 128
 129                         public override System.IComparable Value(int slot)
 130                         {
 131                                 return (sbyte) values[slot];
 132                         }
 133                 }
 134
 135                 /// <summary>Sorts by ascending docID </summary>
 136                 public sealed class DocComparator:FieldComparator
 137                 {
 138                         private int[] docIDs;
 139                         private int docBase;
 140                         private int bottom;
 141
 142                         internal DocComparator(int numHits)
 143                         {
 144                                 docIDs = new int[numHits];
 145                         }
 146
 147                         public override int Compare(int slot1, int slot2)
 148                         {
 149                                 // No overflow risk because docIDs are non-negative
 150                                 return docIDs[slot1] - docIDs[slot2];
 151                         }
 152
 153                         public override int CompareBottom(int doc)
 154                         {
 155                                 // No overflow risk because docIDs are non-negative
 156                                 return bottom - (docBase + doc);
 157                         }
 158
 159                         public override void  Copy(int slot, int doc)
 160                         {
 161                                 docIDs[slot] = docBase + doc;
 162                         }
 163
 164                         public override void  SetNextReader(IndexReader reader, int docBase)
 165                         {
 166                                 // TODO: can we "map" our docIDs to the current
 167                                 // reader? saves having to then subtract on every
 168                                 // compare call
 169                                 this.docBase = docBase;
 170                         }
 171
 172                         public override void  SetBottom(int bottom)
 173                         {
 174                                 this.bottom = docIDs[bottom];
 175                         }
 176
 177                         public override System.IComparable Value(int slot)
 178                         {
 179                                 return (System.Int32) docIDs[slot];
 180                         }
 181                 }
 182
 183                 /// <summary>Parses field's values as double (using {@link
 184                 /// FieldCache#getDoubles} and sorts by ascending value
 185                 /// </summary>
 186                 public sealed class DoubleComparator:FieldComparator
 187                 {
 188                         private double[] values;
 189                         private double[] currentReaderValues;
 190                         private System.String field;
 191                         private DoubleParser parser;
 192                         private double bottom;
 193
 194                         internal DoubleComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
 195                         {
 196                                 values = new double[numHits];
 197                                 this.field = field;
 198                                 this.parser = (DoubleParser) parser;
 199                         }
 200
 201                         public override int Compare(int slot1, int slot2)
 202                         {
 203                                 double v1 = values[slot1];
 204                                 double v2 = values[slot2];
 205                                 if (v1 > v2)
 206                                 {
 207                                         return 1;
 208                                 }
 209                                 else if (v1 < v2)
 210                                 {
 211                                         return - 1;
 212                                 }
 213                                 else
 214                                 {
 215                                         return 0;
 216                                 }
 217                         }
 218
 219                         public override int CompareBottom(int doc)
 220                         {
 221                                 double v2 = currentReaderValues[doc];
 222                                 if (bottom > v2)
 223                                 {
 224                                         return 1;
 225                                 }
 226                                 else if (bottom < v2)
 227                                 {
 228                                         return - 1;
 229                                 }
 230                                 else
 231                                 {
 232                                         return 0;
 233                                 }
 234                         }
 235
 236                         public override void  Copy(int slot, int doc)
 237                         {
 238                                 values[slot] = currentReaderValues[doc];
 239                         }
 240
 241                         public override void  SetNextReader(IndexReader reader, int docBase)
 242                         {
 243                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetDoubles(reader, field, parser);
 244                         }
 245
 246                         public override void  SetBottom(int bottom)
 247                         {
 248                                 this.bottom = values[bottom];
 249                         }
 250
 251                         public override System.IComparable Value(int slot)
 252                         {
 253                                 return (double) values[slot];
 254                         }
 255                 }
 256
 257                 /// <summary>Parses field's values as float (using {@link
 258                 /// FieldCache#getFloats} and sorts by ascending value
 259                 /// </summary>
 260                 public sealed class FloatComparator:FieldComparator
 261                 {
 262                         private float[] values;
 263                         private float[] currentReaderValues;
 264                         private System.String field;
 265                         private FloatParser parser;
 266                         private float bottom;
 267
 268                         internal FloatComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
 269                         {
 270                                 values = new float[numHits];
 271                                 this.field = field;
 272                                 this.parser = (FloatParser) parser;
 273                         }
 274
 275                         public override int Compare(int slot1, int slot2)
 276                         {
 277                                 // TODO: are there sneaky non-branch ways to compute
 278                                 // sign of float?
 279                                 float v1 = values[slot1];
 280                                 float v2 = values[slot2];
 281                                 if (v1 > v2)
 282                                 {
 283                                         return 1;
 284                                 }
 285                                 else if (v1 < v2)
 286                                 {
 287                                         return - 1;
 288                                 }
 289                                 else
 290                                 {
 291                                         return 0;
 292                                 }
 293                         }
 294
 295                         public override int CompareBottom(int doc)
 296                         {
 297                                 // TODO: are there sneaky non-branch ways to compute
 298                                 // sign of float?
 299                                 float v2 = currentReaderValues[doc];
 300                                 if (bottom > v2)
 301                                 {
 302                                         return 1;
 303                                 }
 304                                 else if (bottom < v2)
 305                                 {
 306                                         return - 1;
 307                                 }
 308                                 else
 309                                 {
 310                                         return 0;
 311                                 }
 312                         }
 313
 314                         public override void  Copy(int slot, int doc)
 315                         {
 316                                 values[slot] = currentReaderValues[doc];
 317                         }
 318
 319                         public override void  SetNextReader(IndexReader reader, int docBase)
 320                         {
 321                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetFloats(reader, field, parser);
 322                         }
 323
 324                         public override void  SetBottom(int bottom)
 325                         {
 326                                 this.bottom = values[bottom];
 327                         }
 328
 329                         public override System.IComparable Value(int slot)
 330                         {
 331                                 return (float) values[slot];
 332                         }
 333                 }
 334
 335                 /// <summary>Parses field's values as int (using {@link
 336                 /// FieldCache#getInts} and sorts by ascending value
 337                 /// </summary>
 338                 public sealed class IntComparator:FieldComparator
 339                 {
 340                         private int[] values;
 341                         private int[] currentReaderValues;
 342                         private System.String field;
 343                         private IntParser parser;
 344                         private int bottom; // Value of bottom of queue
 345
 346                         internal IntComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
 347                         {
 348                                 values = new int[numHits];
 349                                 this.field = field;
 350                                 this.parser = (IntParser) parser;
 351                         }
 352
 353                         public override int Compare(int slot1, int slot2)
 354                         {
 355                                 // TODO: there are sneaky non-branch ways to compute
 356                                 // -1/+1/0 sign
 357                                 // Cannot return values[slot1] - values[slot2] because that
 358                                 // may overflow
 359                                 int v1 = values[slot1];
 360                                 int v2 = values[slot2];
 361                                 if (v1 > v2)
 362                                 {
 363                                         return 1;
 364                                 }
 365                                 else if (v1 < v2)
 366                                 {
 367                                         return - 1;
 368                                 }
 369                                 else
 370                                 {
 371                                         return 0;
 372                                 }
 373                         }
 374
 375                         public override int CompareBottom(int doc)
 376                         {
 377                                 // TODO: there are sneaky non-branch ways to compute
 378                                 // -1/+1/0 sign
 379                                 // Cannot return bottom - values[slot2] because that
 380                                 // may overflow
 381                                 int v2 = currentReaderValues[doc];
 382                                 if (bottom > v2)
 383                                 {
 384                                         return 1;
 385                                 }
 386                                 else if (bottom < v2)
 387                                 {
 388                                         return - 1;
 389                                 }
 390                                 else
 391                                 {
 392                                         return 0;
 393                                 }
 394                         }
 395
 396                         public override void  Copy(int slot, int doc)
 397                         {
 398                                 values[slot] = currentReaderValues[doc];
 399                         }
 400
 401                         public override void  SetNextReader(IndexReader reader, int docBase)
 402                         {
 403                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetInts(reader, field, parser);
 404                         }
 405
 406                         public override void  SetBottom(int bottom)
 407                         {
 408                                 this.bottom = values[bottom];
 409                         }
 410
 411                         public override System.IComparable Value(int slot)
 412                         {
 413                                 return (System.Int32) values[slot];
 414                         }
 415                 }
 416
 417                 /// <summary>Parses field's values as long (using {@link
 418                 /// FieldCache#getLongs} and sorts by ascending value
 419                 /// </summary>
 420                 public sealed class LongComparator:FieldComparator
 421                 {
 422                         private long[] values;
 423                         private long[] currentReaderValues;
 424                         private System.String field;
 425                         private LongParser parser;
 426                         private long bottom;
 427
 428                         internal LongComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
 429                         {
 430                                 values = new long[numHits];
 431                                 this.field = field;
 432                                 this.parser = (LongParser) parser;
 433                         }
 434
 435                         public override int Compare(int slot1, int slot2)
 436                         {
 437                                 // TODO: there are sneaky non-branch ways to compute
 438                                 // -1/+1/0 sign
 439                                 long v1 = values[slot1];
 440                                 long v2 = values[slot2];
 441                                 if (v1 > v2)
 442                                 {
 443                                         return 1;
 444                                 }
 445                                 else if (v1 < v2)
 446                                 {
 447                                         return - 1;
 448                                 }
 449                                 else
 450                                 {
 451                                         return 0;
 452                                 }
 453                         }
 454
 455                         public override int CompareBottom(int doc)
 456                         {
 457                                 // TODO: there are sneaky non-branch ways to compute
 458                                 // -1/+1/0 sign
 459                                 long v2 = currentReaderValues[doc];
 460                                 if (bottom > v2)
 461                                 {
 462                                         return 1;
 463                                 }
 464                                 else if (bottom < v2)
 465                                 {
 466                                         return - 1;
 467                                 }
 468                                 else
 469                                 {
 470                                         return 0;
 471                                 }
 472                         }
 473
 474                         public override void  Copy(int slot, int doc)
 475                         {
 476                                 values[slot] = currentReaderValues[doc];
 477                         }
 478
 479                         public override void  SetNextReader(IndexReader reader, int docBase)
 480                         {
 481                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetLongs(reader, field, parser);
 482                         }
 483
 484                         public override void  SetBottom(int bottom)
 485                         {
 486                                 this.bottom = values[bottom];
 487                         }
 488
 489                         public override System.IComparable Value(int slot)
 490                         {
 491                                 return (long) values[slot];
 492                         }
 493                 }
 494
 495                 /// <summary>Sorts by descending relevance.  NOTE: if you are
 496                 /// sorting only by descending relevance and then
 497                 /// secondarily by ascending docID, peformance is faster
 498                 /// using {@link TopScoreDocCollector} directly (which {@link
 499                 /// IndexSearcher#search} uses when no {@link Sort} is
 500                 /// specified).
 501                 /// </summary>
 502                 public sealed class RelevanceComparator:FieldComparator
 503                 {
 504                         private float[] scores;
 505                         private float bottom;
 506                         private Scorer scorer;
 507
 508                         internal RelevanceComparator(int numHits)
 509                         {
 510                                 scores = new float[numHits];
 511                         }
 512
 513                         public override int Compare(int slot1, int slot2)
 514                         {
 515                                 float score1 = scores[slot1];
 516                                 float score2 = scores[slot2];
 517                                 return score1 > score2?- 1:(score1 < score2?1:0);
 518                         }
 519
 520                         public override int CompareBottom(int doc)
 521                         {
 522                                 float score = scorer.Score();
 523                                 return bottom > score?- 1:(bottom < score?1:0);
 524                         }
 525
 526                         public override void  Copy(int slot, int doc)
 527                         {
 528                                 scores[slot] = scorer.Score();
 529                         }
 530
 531                         public override void  SetNextReader(IndexReader reader, int docBase)
 532                         {
 533                         }
 534
 535                         public override void  SetBottom(int bottom)
 536                         {
 537                                 this.bottom = scores[bottom];
 538                         }
 539
 540                         public override void  SetScorer(Scorer scorer)
 541                         {
 542                                 // wrap with a ScoreCachingWrappingScorer so that successive calls to
 543                                 // score() will not incur score computation over and over again.
 544                                 this.scorer = new ScoreCachingWrappingScorer(scorer);
 545                         }
 546
 547                         public override System.IComparable Value(int slot)
 548                         {
 549                                 return (float) scores[slot];
 550                         }
 551                 }
 552
 553                 /// <summary>Parses field's values as short (using {@link
 554                 /// FieldCache#getShorts} and sorts by ascending value
 555                 /// </summary>
 556                 public sealed class ShortComparator:FieldComparator
 557                 {
 558                         private short[] values;
 559                         private short[] currentReaderValues;
 560                         private System.String field;
 561                         private ShortParser parser;
 562                         private short bottom;
 563
 564                         internal ShortComparator(int numHits, System.String field, Mono.Lucene.Net.Search.Parser parser)
 565                         {
 566                                 values = new short[numHits];
 567                                 this.field = field;
 568                                 this.parser = (ShortParser) parser;
 569                         }
 570
 571                         public override int Compare(int slot1, int slot2)
 572                         {
 573                                 return values[slot1] - values[slot2];
 574                         }
 575
 576                         public override int CompareBottom(int doc)
 577                         {
 578                                 return bottom - currentReaderValues[doc];
 579                         }
 580
 581                         public override void  Copy(int slot, int doc)
 582                         {
 583                                 values[slot] = currentReaderValues[doc];
 584                         }
 585
 586                         public override void  SetNextReader(IndexReader reader, int docBase)
 587                         {
 588                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetShorts(reader, field, parser);
 589                         }
 590
 591                         public override void  SetBottom(int bottom)
 592                         {
 593                                 this.bottom = values[bottom];
 594                         }
 595
 596                         public override System.IComparable Value(int slot)
 597                         {
 598                                 return (short) values[slot];
 599                         }
 600                 }
 601
 602                 /// <summary>Sorts by a field's value using the Collator for a
 603                 /// given Locale.
 604                 /// </summary>
 605                 public sealed class StringComparatorLocale:FieldComparator
 606                 {
 607
 608                         private System.String[] values;
 609                         private System.String[] currentReaderValues;
 610                         private System.String field;
 611                         internal System.Globalization.CompareInfo collator;
 612                         private System.String bottom;
 613
 614                         internal StringComparatorLocale(int numHits, System.String field, System.Globalization.CultureInfo locale)
 615                         {
 616                                 values = new System.String[numHits];
 617                                 this.field = field;
 618                                 collator = locale.CompareInfo;
 619                         }
 620
 621                         public override int Compare(int slot1, int slot2)
 622                         {
 623                                 System.String val1 = values[slot1];
 624                                 System.String val2 = values[slot2];
 625                                 if (val1 == null)
 626                                 {
 627                                         if (val2 == null)
 628                                         {
 629                                                 return 0;
 630                                         }
 631                                         return - 1;
 632                                 }
 633                                 else if (val2 == null)
 634                                 {
 635                                         return 1;
 636                                 }
 637                                 return collator.Compare(val1.ToString(), val2.ToString());
 638                         }
 639
 640                         public override int CompareBottom(int doc)
 641                         {
 642                                 System.String val2 = currentReaderValues[doc];
 643                                 if (bottom == null)
 644                                 {
 645                                         if (val2 == null)
 646                                         {
 647                                                 return 0;
 648                                         }
 649                                         return - 1;
 650                                 }
 651                                 else if (val2 == null)
 652                                 {
 653                                         return 1;
 654                                 }
 655                                 return collator.Compare(bottom.ToString(), val2.ToString());
 656                         }
 657
 658                         public override void  Copy(int slot, int doc)
 659                         {
 660                                 values[slot] = currentReaderValues[doc];
 661                         }
 662
 663                         public override void  SetNextReader(IndexReader reader, int docBase)
 664                         {
 665                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetStrings(reader, field);
 666                         }
 667
 668                         public override void  SetBottom(int bottom)
 669                         {
 670                                 this.bottom = values[bottom];
 671                         }
 672
 673                         public override System.IComparable Value(int slot)
 674                         {
 675                                 return values[slot];
 676                         }
 677                 }
 678
 679                 /// <summary>Sorts by field's natural String sort order, using
 680                 /// ordinals.  This is functionally equivalent to {@link
 681                 /// StringValComparator}, but it first resolves the string
 682                 /// to their relative ordinal positions (using the index
 683                 /// returned by {@link FieldCache#getStringIndex}), and
 684                 /// does most comparisons using the ordinals.  For medium
 685                 /// to large results, this comparator will be much faster
 686                 /// than {@link StringValComparator}.  For very small
 687                 /// result sets it may be slower.
 688                 /// </summary>
 689                 public sealed class StringOrdValComparator:FieldComparator
 690                 {
 691
 692                         private int[] ords;
 693                         private System.String[] values;
 694                         private int[] readerGen;
 695
 696                         private int currentReaderGen = - 1;
 697                         private System.String[] lookup;
 698                         private int[] order;
 699                         private System.String field;
 700
 701                         private int bottomSlot = - 1;
 702                         private int bottomOrd;
 703                         private System.String bottomValue;
 704                         private bool reversed;
 705                         private int sortPos;
 706
 707                         public StringOrdValComparator(int numHits, System.String field, int sortPos, bool reversed)
 708                         {
 709                                 ords = new int[numHits];
 710                                 values = new System.String[numHits];
 711                                 readerGen = new int[numHits];
 712                                 this.sortPos = sortPos;
 713                                 this.reversed = reversed;
 714                                 this.field = field;
 715                         }
 716
 717                         public override int Compare(int slot1, int slot2)
 718                         {
 719                                 if (readerGen[slot1] == readerGen[slot2])
 720                                 {
 721                                         int cmp = ords[slot1] - ords[slot2];
 722                                         if (cmp != 0)
 723                                         {
 724                                                 return cmp;
 725                                         }
 726                                 }
 727
 728                                 System.String val1 = values[slot1];
 729                                 System.String val2 = values[slot2];
 730                                 if (val1 == null)
 731                                 {
 732                                         if (val2 == null)
 733                                         {
 734                                                 return 0;
 735                                         }
 736                                         return - 1;
 737                                 }
 738                                 else if (val2 == null)
 739                                 {
 740                                         return 1;
 741                                 }
 742                                 return String.CompareOrdinal(val1, val2);
 743                         }
 744
 745                         public override int CompareBottom(int doc)
 746                         {
 747                                 System.Diagnostics.Debug.Assert(bottomSlot != - 1);
 748                                 int order = this.order[doc];
 749                                 int cmp = bottomOrd - order;
 750                                 if (cmp != 0)
 751                                 {
 752                                         return cmp;
 753                                 }
 754
 755                                 System.String val2 = lookup[order];
 756                                 if (bottomValue == null)
 757                                 {
 758                                         if (val2 == null)
 759                                         {
 760                                                 return 0;
 761                                         }
 762                                         // bottom wins
 763                                         return - 1;
 764                                 }
 765                                 else if (val2 == null)
 766                                 {
 767                                         // doc wins
 768                                         return 1;
 769                                 }
 770                                 return String.CompareOrdinal(bottomValue, val2);
 771                         }
 772
 773                         private void  Convert(int slot)
 774                         {
 775                                 readerGen[slot] = currentReaderGen;
 776                                 int index = 0;
 777                                 System.String value_Renamed = values[slot];
 778                                 if (value_Renamed == null)
 779                                 {
 780                                         ords[slot] = 0;
 781                                         return ;
 782                                 }
 783
 784                                 if (sortPos == 0 && bottomSlot != - 1 && bottomSlot != slot)
 785                                 {
 786                                         // Since we are the primary sort, the entries in the
 787                                         // queue are bounded by bottomOrd:
 788                                         System.Diagnostics.Debug.Assert(bottomOrd < lookup.Length);
 789                                         if (reversed)
 790                                         {
 791                                                 index = BinarySearch(lookup, value_Renamed, bottomOrd, lookup.Length - 1);
 792                                         }
 793                                         else
 794                                         {
 795                                                 index = BinarySearch(lookup, value_Renamed, 0, bottomOrd);
 796                                         }
 797                                 }
 798                                 else
 799                                 {
 800                                         // Full binary search
 801                                         index = BinarySearch(lookup, value_Renamed);
 802                                 }
 803
 804                                 if (index < 0)
 805                                 {
 806                                         index = - index - 2;
 807                                 }
 808                                 ords[slot] = index;
 809                         }
 810
 811                         public override void  Copy(int slot, int doc)
 812                         {
 813                                 int ord = order[doc];
 814                                 ords[slot] = ord;
 815                                 System.Diagnostics.Debug.Assert(ord >= 0);
 816                                 values[slot] = lookup[ord];
 817                                 readerGen[slot] = currentReaderGen;
 818                         }
 819
 820                         public override void  SetNextReader(IndexReader reader, int docBase)
 821                         {
 822                                 StringIndex currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetStringIndex(reader, field);
 823                                 currentReaderGen++;
 824                                 order = currentReaderValues.order;
 825                                 lookup = currentReaderValues.lookup;
 826                                 System.Diagnostics.Debug.Assert(lookup.Length > 0);
 827                                 if (bottomSlot != - 1)
 828                                 {
 829                                         Convert(bottomSlot);
 830                                         bottomOrd = ords[bottomSlot];
 831                                 }
 832                         }
 833
 834                         public override void  SetBottom(int bottom)
 835                         {
 836                                 bottomSlot = bottom;
 837                                 if (readerGen[bottom] != currentReaderGen)
 838                                 {
 839                                         Convert(bottomSlot);
 840                                 }
 841                                 bottomOrd = ords[bottom];
 842                                 System.Diagnostics.Debug.Assert(bottomOrd >= 0);
 843                                 System.Diagnostics.Debug.Assert(bottomOrd < lookup.Length);
 844                                 bottomValue = values[bottom];
 845                         }
 846
 847                         public override System.IComparable Value(int slot)
 848                         {
 849                                 return values[slot];
 850                         }
 851
 852                         public System.String[] GetValues()
 853                         {
 854                                 return values;
 855                         }
 856
 857                         public int GetBottomSlot()
 858                         {
 859                                 return bottomSlot;
 860                         }
 861
 862                         public System.String GetField()
 863                         {
 864                                 return field;
 865                         }
 866                 }
 867
 868                 /// <summary>Sorts by field's natural String sort order.  All
 869                 /// comparisons are done using String.compareTo, which is
 870                 /// slow for medium to large result sets but possibly
 871                 /// very fast for very small results sets.
 872                 /// </summary>
 873                 public sealed class StringValComparator:FieldComparator
 874                 {
 875
 876                         private System.String[] values;
 877                         private System.String[] currentReaderValues;
 878                         private System.String field;
 879                         private System.String bottom;
 880
 881                         internal StringValComparator(int numHits, System.String field)
 882                         {
 883                                 values = new System.String[numHits];
 884                                 this.field = field;
 885                         }
 886
 887                         public override int Compare(int slot1, int slot2)
 888                         {
 889                                 System.String val1 = values[slot1];
 890                                 System.String val2 = values[slot2];
 891                                 if (val1 == null)
 892                                 {
 893                                         if (val2 == null)
 894                                         {
 895                                                 return 0;
 896                                         }
 897                                         return - 1;
 898                                 }
 899                                 else if (val2 == null)
 900                                 {
 901                                         return 1;
 902                                 }
 903
 904                                 return String.CompareOrdinal(val1, val2);
 905                         }
 906
 907                         public override int CompareBottom(int doc)
 908                         {
 909                                 System.String val2 = currentReaderValues[doc];
 910                                 if (bottom == null)
 911                                 {
 912                                         if (val2 == null)
 913                                         {
 914                                                 return 0;
 915                                         }
 916                                         return - 1;
 917                                 }
 918                                 else if (val2 == null)
 919                                 {
 920                                         return 1;
 921                                 }
 922                                 return String.CompareOrdinal(bottom, val2);
 923                         }
 924
 925                         public override void  Copy(int slot, int doc)
 926                         {
 927                                 values[slot] = currentReaderValues[doc];
 928                         }
 929
 930                         public override void  SetNextReader(IndexReader reader, int docBase)
 931                         {
 932                                 currentReaderValues = Mono.Lucene.Net.Search.FieldCache_Fields.DEFAULT.GetStrings(reader, field);
 933                         }
 934
 935                         public override void  SetBottom(int bottom)
 936                         {
 937                                 this.bottom = values[bottom];
 938                         }
 939
 940                         public override System.IComparable Value(int slot)
 941                         {
 942                                 return values[slot];
 943                         }
 944                 }
 945
 946                 protected internal static int BinarySearch(System.String[] a, System.String key)
 947                 {
 948                         return BinarySearch(a, key, 0, a.Length - 1);
 949                 }
 950
 951                 protected internal static int BinarySearch(System.String[] a, System.String key, int low, int high)
 952                 {
 953
 954                         while (low <= high)
 955                         {
 956                                 int mid = SupportClass.Number.URShift((low + high), 1);
 957                                 System.String midVal = a[mid];
 958                                 int cmp;
 959                                 if (midVal != null)
 960                                 {
 961                                         cmp = String.CompareOrdinal(midVal, key);
 962                                 }
 963                                 else
 964                                 {
 965                                         cmp = - 1;
 966                                 }
 967
 968                                 if (cmp < 0)
 969                                         low = mid + 1;
 970                                 else if (cmp > 0)
 971                                         high = mid - 1;
 972                                 else
 973                                         return mid;
 974                         }
 975                         return - (low + 1);
 976                 }
 977
 978                 /// <summary> Compare hit at slot1 with hit at slot2.
 979                 ///
 980                 /// </summary>
 981                 /// <param name="slot1">first slot to compare
 982                 /// </param>
 983                 /// <param name="slot2">second slot to compare
 984                 /// </param>
 985         /// <returns> any N &lt; 0 if slot2's value is sorted after
 986                 /// slot1, any N > 0 if the slot2's value is sorted before
 987                 /// slot1 and 0 if they are equal
 988                 /// </returns>
 989                 public abstract int Compare(int slot1, int slot2);
 990
 991                 /// <summary> Set the bottom slot, ie the "weakest" (sorted last)
 992                 /// entry in the queue.  When {@link #compareBottom} is
 993                 /// called, you should compare against this slot.  This
 994                 /// will always be called before {@link #compareBottom}.
 995                 ///
 996                 /// </summary>
 997                 /// <param name="slot">the currently weakest (sorted last) slot in the queue
 998                 /// </param>
 999                 public abstract void  SetBottom(int slot);
1000
1001                 /// <summary> Compare the bottom of the queue with doc.  This will
1002                 /// only invoked after setBottom has been called.  This
1003                 /// should return the same result as {@link
1004                 /// #Compare(int,int)}} as if bottom were slot1 and the new
1005                 /// document were slot 2.
1006                 ///
1007                 /// <p/>For a search that hits many results, this method
1008                 /// will be the hotspot (invoked by far the most
1009                 /// frequently).<p/>
1010                 ///
1011                 /// </summary>
1012                 /// <param name="doc">that was hit
1013                 /// </param>
1014         /// <returns> any N &lt; 0 if the doc's value is sorted after
1015                 /// the bottom entry (not competitive), any N > 0 if the
1016                 /// doc's value is sorted before the bottom entry and 0 if
1017                 /// they are equal.
1018                 /// </returns>
1019                 public abstract int CompareBottom(int doc);
1020
1021                 /// <summary> This method is called when a new hit is competitive.
1022                 /// You should copy any state associated with this document
1023                 /// that will be required for future comparisons, into the
1024                 /// specified slot.
1025                 ///
1026                 /// </summary>
1027                 /// <param name="slot">which slot to copy the hit to
1028                 /// </param>
1029                 /// <param name="doc">docID relative to current reader
1030                 /// </param>
1031                 public abstract void  Copy(int slot, int doc);
1032
1033                 /// <summary> Set a new Reader. All doc correspond to the current Reader.
1034                 ///
1035                 /// </summary>
1036                 /// <param name="reader">current reader
1037                 /// </param>
1038                 /// <param name="docBase">docBase of this reader
1039                 /// </param>
1040                 /// <throws>  IOException </throws>
1041                 /// <throws>  IOException </throws>
1042                 public abstract void  SetNextReader(IndexReader reader, int docBase);
1043
1044                 /// <summary>Sets the Scorer to use in case a document's score is
1045                 /// needed.
1046                 ///
1047                 /// </summary>
1048                 /// <param name="scorer">Scorer instance that you should use to
1049                 /// obtain the current hit's score, if necessary.
1050                 /// </param>
1051                 public virtual void  SetScorer(Scorer scorer)
1052                 {
1053                         // Empty implementation since most comparators don't need the score. This
1054                         // can be overridden by those that need it.
1055                 }
1056
1057                 /// <summary> Return the actual value in the slot.
1058                 ///
1059                 /// </summary>
1060                 /// <param name="slot">the value
1061                 /// </param>
1062                 /// <returns> value in this slot upgraded to Comparable
1063                 /// </returns>
1064                 public abstract System.IComparable Value(int slot);
1065         }
1066 }