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