lucene-java-3.4.0/lucene/src/java/org/apache/lucene/search/FieldValueHitQueue.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
  22 import org.apache.lucene.util.PriorityQueue;
  23
  24 /**
  25  * Expert: A hit queue for sorting by hits by terms in more than one field.
  26  * Uses <code>FieldCache.DEFAULT</code> for maintaining
  27  * internal term lookup tables.
  28  *
  29  * @lucene.experimental
  30  * @since 2.9
  31  * @see Searcher#search(Query,Filter,int,Sort)
  32  * @see FieldCache
  33  */
  34 public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry> extends PriorityQueue<T> {
  35
  36   public static class Entry extends ScoreDoc {
  37     public int slot;
  38
  39     public Entry(int slot, int doc, float score) {
  40       super(doc, score);
  41       this.slot = slot;
  42     }
  43
  44     @Override
  45     public String toString() {
  46       return "slot:" + slot + " " + super.toString();
  47     }
  48   }
  49
  50   /**
  51    * An implementation of {@link FieldValueHitQueue} which is optimized in case
  52    * there is just one comparator.
  53    */
  54   private static final class OneComparatorFieldValueHitQueue<T extends FieldValueHitQueue.Entry> extends FieldValueHitQueue<T> {
  55
  56     private final FieldComparator comparator;
  57     private final int oneReverseMul;
  58
  59     public OneComparatorFieldValueHitQueue(SortField[] fields, int size)
  60         throws IOException {
  61       super(fields);
  62
  63       SortField field = fields[0];
  64       comparator = field.getComparator(size, 0);
  65       oneReverseMul = field.reverse ? -1 : 1;
  66
  67       comparators[0] = comparator;
  68       reverseMul[0] = oneReverseMul;
  69
  70       initialize(size);
  71     }
  72
  73     /**
  74      * Returns whether <code>a</code> is less relevant than <code>b</code>.
  75      * @param a ScoreDoc
  76      * @param b ScoreDoc
  77      * @return <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>.
  78      */
  79     @Override
  80     protected boolean lessThan(final Entry hitA, final Entry hitB) {
  81
  82       assert hitA != hitB;
  83       assert hitA.slot != hitB.slot;
  84
  85       final int c = oneReverseMul * comparator.compare(hitA.slot, hitB.slot);
  86       if (c != 0) {
  87         return c > 0;
  88       }
  89
  90       // avoid random sort order that could lead to duplicates (bug #31241):
  91       return hitA.doc > hitB.doc;
  92     }
  93
  94   }
  95
  96   /**
  97    * An implementation of {@link FieldValueHitQueue} which is optimized in case
  98    * there is more than one comparator.
  99    */
 100   private static final class MultiComparatorsFieldValueHitQueue<T extends FieldValueHitQueue.Entry> extends FieldValueHitQueue<T> {
 101
 102     public MultiComparatorsFieldValueHitQueue(SortField[] fields, int size)
 103         throws IOException {
 104       super(fields);
 105
 106       int numComparators = comparators.length;
 107       for (int i = 0; i < numComparators; ++i) {
 108         SortField field = fields[i];
 109
 110         reverseMul[i] = field.reverse ? -1 : 1;
 111         comparators[i] = field.getComparator(size, i);
 112       }
 113
 114       initialize(size);
 115     }
 116
 117     @Override
 118     protected boolean lessThan(final Entry hitA, final Entry hitB) {
 119
 120       assert hitA != hitB;
 121       assert hitA.slot != hitB.slot;
 122
 123       int numComparators = comparators.length;
 124       for (int i = 0; i < numComparators; ++i) {
 125         final int c = reverseMul[i] * comparators[i].compare(hitA.slot, hitB.slot);
 126         if (c != 0) {
 127           // Short circuit
 128           return c > 0;
 129         }
 130       }
 131
 132       // avoid random sort order that could lead to duplicates (bug #31241):
 133       return hitA.doc > hitB.doc;
 134     }
 135
 136   }
 137
 138   // prevent instantiation and extension.
 139   private FieldValueHitQueue(SortField[] fields) {
 140     // When we get here, fields.length is guaranteed to be > 0, therefore no
 141     // need to check it again.
 142
 143     // All these are required by this class's API - need to return arrays.
 144     // Therefore even in the case of a single comparator, create an array
 145     // anyway.
 146     this.fields = fields;
 147     int numComparators = fields.length;
 148     comparators = new FieldComparator[numComparators];
 149     reverseMul = new int[numComparators];
 150   }
 151
 152   /**
 153    * Creates a hit queue sorted by the given list of fields.
 154    *
 155    * <p><b>NOTE</b>: The instances returned by this method
 156    * pre-allocate a full array of length <code>numHits</code>.
 157    *
 158    * @param fields
 159    *          SortField array we are sorting by in priority order (highest
 160    *          priority first); cannot be <code>null</code> or empty
 161    * @param size
 162    *          The number of hits to retain. Must be greater than zero.
 163    * @throws IOException
 164    */
 165   public static <T extends FieldValueHitQueue.Entry> FieldValueHitQueue<T> create(SortField[] fields, int size) throws IOException {
 166
 167     if (fields.length == 0) {
 168       throw new IllegalArgumentException("Sort must contain at least one field");
 169     }
 170
 171     if (fields.length == 1) {
 172       return new OneComparatorFieldValueHitQueue<T>(fields, size);
 173     } else {
 174       return new MultiComparatorsFieldValueHitQueue<T>(fields, size);
 175     }
 176   }
 177
 178   public FieldComparator[] getComparators() {
 179     return comparators;
 180   }
 181
 182   public int[] getReverseMul() {
 183     return reverseMul;
 184   }
 185
 186   /** Stores the sort criteria being used. */
 187   protected final SortField[] fields;
 188   protected final FieldComparator[] comparators;
 189   protected final int[] reverseMul;
 190
 191   @Override
 192   protected abstract boolean lessThan (final Entry a, final Entry b);
 193
 194   /**
 195    * Given a queue Entry, creates a corresponding FieldDoc
 196    * that contains the values used to sort the given document.
 197    * These values are not the raw values out of the index, but the internal
 198    * representation of them. This is so the given search hit can be collated by
 199    * a MultiSearcher with other search hits.
 200    *
 201    * @param entry The Entry used to create a FieldDoc
 202    * @return The newly created FieldDoc
 203    * @see Searchable#search(Weight,Filter,int,Sort)
 204    */
 205   FieldDoc fillFields(final Entry entry) {
 206     final int n = comparators.length;
 207     final Object[] fields = new Object[n];
 208     for (int i = 0; i < n; ++i) {
 209       fields[i] = comparators[i].value(entry.slot);
 210     }
 211     //if (maxscore > 1.0f) doc.score /= maxscore;   // normalize scores
 212     return new FieldDoc(entry.doc, entry.score, fields);
 213   }
 214
 215   /** Returns the SortFields being used by this hit queue. */
 216   SortField[] getFields() {
 217     return fields;
 218   }
 219 }