lucene-java-3.4.0/lucene/src/java/org/apache/lucene/search/FieldComparator.java

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