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 org.apache.lucene.index.IndexReader;
21 import org.apache.lucene.util.PriorityQueue;
22
23 import java.io.IOException;
24 import java.text.Collator;
25 import java.util.Locale;
26
27 /**
28 * Expert: A hit queue for sorting by hits by terms in more than one field.
29 * Uses <code>FieldCache.DEFAULT</code> for maintaining internal term lookup tables.
30 *
31 * <p>Created: Dec 8, 2003 12:56:03 PM
32 *
33 * @since lucene 1.4
34 * @version $Id: FieldSortedHitQueue.java 695514 2008-09-15 15:42:11Z otis $
35 * @see Searcher#search(Query,Filter,int,Sort)
36 * @see FieldCache
37 */
38 public class FieldSortedHitQueue
39 extends PriorityQueue {
40
41 /**
42 * Creates a hit queue sorted by the given list of fields.
43 * @param reader Index to use.
44 * @param fields Fieldable names, in priority order (highest priority first). Cannot be <code>null</code> or empty.
45 * @param size The number of hits to retain. Must be greater than zero.
46 * @throws IOException
47 */
48 public FieldSortedHitQueue (IndexReader reader, SortField[] fields, int size)
49 throws IOException {
50 final int n = fields.length;
51 comparators = new ScoreDocComparator[n];
52 this.fields = new SortField[n];
53 for (int i=0; i<n; ++i) {
54 String fieldname = fields[i].getField();
55 comparators[i] = getCachedComparator (reader, fieldname, fields[i].getType(), fields[i].getLocale(), fields[i].getFactory());
56
57 if (comparators[i].sortType() == SortField.STRING) {
58 this.fields[i] = new SortField (fieldname, fields[i].getLocale(), fields[i].getReverse());
59 } else {
60 this.fields[i] = new SortField (fieldname, comparators[i].sortType(), fields[i].getReverse());
61 }
62 }
63 initialize (size);
64 }
65
66
67 /** Stores a comparator corresponding to each field being sorted by */
68 protected ScoreDocComparator[] comparators;
69
70 /** Stores the sort criteria being used. */
71 protected SortField[] fields;
72
73 /** Stores the maximum score value encountered, needed for normalizing. */
74 protected float maxscore = Float.NEGATIVE_INFINITY;
75
76 /** returns the maximum score encountered by elements inserted via insert()
77 */
78 public float getMaxScore() {
79 return maxscore;
80 }
81
82 // Update maxscore.
83 private final void updateMaxScore(FieldDoc fdoc) {
84 maxscore = Math.max(maxscore, fdoc.score);
85 }
86
87 // The signature of this method takes a FieldDoc in order to avoid
88 // the unneeded cast to retrieve the score.
89 // inherit javadoc
90 public boolean insert(FieldDoc fdoc) {
91 updateMaxScore(fdoc);
92 return super.insert(fdoc);
93 }
94
95 // This overrides PriorityQueue.insert() so that insert(FieldDoc) that
96 // keeps track of the score isn't accidentally bypassed.
97 // inherit javadoc
98 public boolean insert(Object fdoc) {
99 return insert((FieldDoc)fdoc);
100 }
101
102 // This overrides PriorityQueue.insertWithOverflow() so that
103 // updateMaxScore(FieldDoc) that keeps track of the score isn't accidentally
104 // bypassed.
105 public Object insertWithOverflow(Object element) {
106 updateMaxScore((FieldDoc) element);
107 return super.insertWithOverflow(element);
108 }
109
110 /**
111 * Returns whether <code>a</code> is less relevant than <code>b</code>.
112 * @param a ScoreDoc
113 * @param b ScoreDoc
114 * @return <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>.
115 */
116 protected boolean lessThan (final Object a, final Object b) {
117 final ScoreDoc docA = (ScoreDoc) a;
118 final ScoreDoc docB = (ScoreDoc) b;
119
120 // run comparators
121 final int n = comparators.length;
122 int c = 0;
123 for (int i=0; i<n && c==0; ++i) {
124 c = (fields[i].reverse) ? comparators[i].compare (docB, docA)
125 : comparators[i].compare (docA, docB);
126 }
127 // avoid random sort order that could lead to duplicates (bug #31241):
128 if (c == 0)
129 return docA.doc > docB.doc;
130 return c > 0;
131 }
132
133
134 /**
135 * Given a FieldDoc object, stores the values used
136 * to sort the given document. These values are not the raw
137 * values out of the index, but the internal representation
138 * of them. This is so the given search hit can be collated
139 * by a MultiSearcher with other search hits.
140 * @param doc The FieldDoc to store sort values into.
141 * @return The same FieldDoc passed in.
142 * @see Searchable#search(Weight,Filter,int,Sort)
143 */
144 FieldDoc fillFields (final FieldDoc doc) {
145 final int n = comparators.length;
146 final Comparable[] fields = new Comparable[n];
147 for (int i=0; i<n; ++i)
148 fields[i] = comparators[i].sortValue(doc);
149 doc.fields = fields;
150 //if (maxscore > 1.0f) doc.score /= maxscore; // normalize scores
151 return doc;
152 }
153
154
155 /** Returns the SortFields being used by this hit queue. */
156 SortField[] getFields() {
157 return fields;
158 }
159
160 static ScoreDocComparator getCachedComparator (IndexReader reader, String field, int type, Locale locale, SortComparatorSource factory)
161 throws IOException {
162 if (type == SortField.DOC) return ScoreDocComparator.INDEXORDER;
163 if (type == SortField.SCORE) return ScoreDocComparator.RELEVANCE;
164 FieldCacheImpl.Entry entry = (factory != null)
165 ? new FieldCacheImpl.Entry (field, factory)
166 : new FieldCacheImpl.Entry (field, type, locale);
167 return (ScoreDocComparator)Comparators.get(reader, entry);
168 }
169
170 /** Internal cache of comparators. Similar to FieldCache, only
171 * caches comparators instead of term values. */
172 static final FieldCacheImpl.Cache Comparators = new FieldCacheImpl.Cache() {
173
174 protected Object createValue(IndexReader reader, Object entryKey)
175 throws IOException {
176 FieldCacheImpl.Entry entry = (FieldCacheImpl.Entry) entryKey;
177 String fieldname = entry.field;
178 int type = entry.type;
179 Locale locale = entry.locale;
180 SortComparatorSource factory = (SortComparatorSource) entry.custom;
181 ScoreDocComparator comparator;
182 switch (type) {
183 case SortField.AUTO:
184 comparator = comparatorAuto (reader, fieldname);
185 break;
186 case SortField.INT:
187 comparator = comparatorInt (reader, fieldname);
188 break;
189 case SortField.FLOAT:
190 comparator = comparatorFloat (reader, fieldname);
191 break;
192 case SortField.LONG:
193 comparator = comparatorLong(reader, fieldname);
194 break;
195 case SortField.DOUBLE:
196 comparator = comparatorDouble(reader, fieldname);
197 break;
198 case SortField.SHORT:
199 comparator = comparatorShort(reader, fieldname);
200 break;
201 case SortField.BYTE:
202 comparator = comparatorByte(reader, fieldname);
203 break;
204 case SortField.STRING:
205 if (locale != null) comparator = comparatorStringLocale (reader, fieldname, locale);
206 else comparator = comparatorString (reader, fieldname);
207 break;
208 case SortField.CUSTOM:
209 comparator = factory.newComparator (reader, fieldname);
210 break;
211 default:
212 throw new RuntimeException ("unknown field type: "+type);
213 }
214 return comparator;
215 }
216 };
217
218 /**
219 * Returns a comparator for sorting hits according to a field containing bytes.
220 * @param reader Index to use.
221 * @param fieldname Fieldable containg integer values.
222 * @return Comparator for sorting hits.
223 * @throws IOException If an error occurs reading the index.
224 */
225 static ScoreDocComparator comparatorByte(final IndexReader reader, final String fieldname)
226 throws IOException {
227 final String field = fieldname.intern();
228 final byte[] fieldOrder = FieldCache.DEFAULT.getBytes(reader, field);
229 return new ScoreDocComparator() {
230
231 public final int compare (final ScoreDoc i, final ScoreDoc j) {
232 final int fi = fieldOrder[i.doc];
233 final int fj = fieldOrder[j.doc];
234 if (fi < fj) return -1;
235 if (fi > fj) return 1;
236 return 0;
237 }
238
239 public Comparable sortValue (final ScoreDoc i) {
240 return new Byte(fieldOrder[i.doc]);
241 }
242
243 public int sortType() {
244 return SortField.INT;
245 }
246 };
247 }
248
249 /**
250 * Returns a comparator for sorting hits according to a field containing shorts.
251 * @param reader Index to use.
252 * @param fieldname Fieldable containg integer values.
253 * @return Comparator for sorting hits.
254 * @throws IOException If an error occurs reading the index.
255 */
256 static ScoreDocComparator comparatorShort(final IndexReader reader, final String fieldname)
257 throws IOException {
258 final String field = fieldname.intern();
259 final short[] fieldOrder = FieldCache.DEFAULT.getShorts(reader, field);
260 return new ScoreDocComparator() {
261
262 public final int compare (final ScoreDoc i, final ScoreDoc j) {
263 final int fi = fieldOrder[i.doc];
264 final int fj = fieldOrder[j.doc];
265 if (fi < fj) return -1;
266 if (fi > fj) return 1;
267 return 0;
268 }
269
270 public Comparable sortValue (final ScoreDoc i) {
271 return new Short(fieldOrder[i.doc]);
272 }
273
274 public int sortType() {
275 return SortField.SHORT;
276 }
277 };
278 }
279
280 /**
281 * Returns a comparator for sorting hits according to a field containing integers.
282 * @param reader Index to use.
283 * @param fieldname Fieldable containg integer values.
284 * @return Comparator for sorting hits.
285 * @throws IOException If an error occurs reading the index.
286 */
287 static ScoreDocComparator comparatorInt (final IndexReader reader, final String fieldname)
288 throws IOException {
289 final String field = fieldname.intern();
290 final int[] fieldOrder = FieldCache.DEFAULT.getInts (reader, field);
291 return new ScoreDocComparator() {
292
293 public final int compare (final ScoreDoc i, final ScoreDoc j) {
294 final int fi = fieldOrder[i.doc];
295 final int fj = fieldOrder[j.doc];
296 if (fi < fj) return -1;
297 if (fi > fj) return 1;
298 return 0;
299 }
300
301 public Comparable sortValue (final ScoreDoc i) {
302 return new Integer (fieldOrder[i.doc]);
303 }
304
305 public int sortType() {
306 return SortField.INT;
307 }
308 };
309 }
310
311 /**
312 * Returns a comparator for sorting hits according to a field containing integers.
313 * @param reader Index to use.
314 * @param fieldname Fieldable containg integer values.
315 * @return Comparator for sorting hits.
316 * @throws IOException If an error occurs reading the index.
317 */
318 static ScoreDocComparator comparatorLong (final IndexReader reader, final String fieldname)
319 throws IOException {
320 final String field = fieldname.intern();
321 final long[] fieldOrder = ExtendedFieldCache.EXT_DEFAULT.getLongs (reader, field);
322 return new ScoreDocComparator() {
323
324 public final int compare (final ScoreDoc i, final ScoreDoc j) {
325 final long li = fieldOrder[i.doc];
326 final long lj = fieldOrder[j.doc];
327 if (li < lj) return -1;
328 if (li > lj) return 1;
329 return 0;
330 }
331
332 public Comparable sortValue (final ScoreDoc i) {
333 return new Long(fieldOrder[i.doc]);
334 }
335
336 public int sortType() {
337 return SortField.LONG;
338 }
339 };
340 }
341
342
343 /**
344 * Returns a comparator for sorting hits according to a field containing floats.
345 * @param reader Index to use.
346 * @param fieldname Fieldable containg float values.
347 * @return Comparator for sorting hits.
348 * @throws IOException If an error occurs reading the index.
349 */
350 static ScoreDocComparator comparatorFloat (final IndexReader reader, final String fieldname)
351 throws IOException {
352 final String field = fieldname.intern();
353 final float[] fieldOrder = FieldCache.DEFAULT.getFloats (reader, field);
354 return new ScoreDocComparator () {
355
356 public final int compare (final ScoreDoc i, final ScoreDoc j) {
357 final float fi = fieldOrder[i.doc];
358 final float fj = fieldOrder[j.doc];
359 if (fi < fj) return -1;
360 if (fi > fj) return 1;
361 return 0;
362 }
363
364 public Comparable sortValue (final ScoreDoc i) {
365 return new Float (fieldOrder[i.doc]);
366 }
367
368 public int sortType() {
369 return SortField.FLOAT;
370 }
371 };
372 }
373
374 /**
375 * Returns a comparator for sorting hits according to a field containing doubles.
376 * @param reader Index to use.
377 * @param fieldname Fieldable containg float values.
378 * @return Comparator for sorting hits.
379 * @throws IOException If an error occurs reading the index.
380 */
381 static ScoreDocComparator comparatorDouble(final IndexReader reader, final String fieldname)
382 throws IOException {
383 final String field = fieldname.intern();
384 final double[] fieldOrder = ExtendedFieldCache.EXT_DEFAULT.getDoubles (reader, field);
385 return new ScoreDocComparator () {
386
387 public final int compare (final ScoreDoc i, final ScoreDoc j) {
388 final double di = fieldOrder[i.doc];
389 final double dj = fieldOrder[j.doc];
390 if (di < dj) return -1;
391 if (di > dj) return 1;
392 return 0;
393 }
394
395 public Comparable sortValue (final ScoreDoc i) {
396 return new Double (fieldOrder[i.doc]);
397 }
398
399 public int sortType() {
400 return SortField.DOUBLE;
401 }
402 };
403 }
404
405 /**
406 * Returns a comparator for sorting hits according to a field containing strings.
407 * @param reader Index to use.
408 * @param fieldname Fieldable containg string values.
409 * @return Comparator for sorting hits.
410 * @throws IOException If an error occurs reading the index.
411 */
412 static ScoreDocComparator comparatorString (final IndexReader reader, final String fieldname)
413 throws IOException {
414 final String field = fieldname.intern();
415 final FieldCache.StringIndex index = FieldCache.DEFAULT.getStringIndex (reader, field);
416 return new ScoreDocComparator () {
417
418 public final int compare (final ScoreDoc i, final ScoreDoc j) {
419 final int fi = index.order[i.doc];
420 final int fj = index.order[j.doc];
421 if (fi < fj) return -1;
422 if (fi > fj) return 1;
423 return 0;
424 }
425
426 public Comparable sortValue (final ScoreDoc i) {
427 return index.lookup[index.order[i.doc]];
428 }
429
430 public int sortType() {
431 return SortField.STRING;
432 }
433 };
434 }
435
436 /**
437 * Returns a comparator for sorting hits according to a field containing strings.
438 * @param reader Index to use.
439 * @param fieldname Fieldable containg string values.
440 * @return Comparator for sorting hits.
441 * @throws IOException If an error occurs reading the index.
442 */
443 static ScoreDocComparator comparatorStringLocale (final IndexReader reader, final String fieldname, final Locale locale)
444 throws IOException {
445 final Collator collator = Collator.getInstance (locale);
446 final String field = fieldname.intern();
447 final String[] index = FieldCache.DEFAULT.getStrings (reader, field);
448 return new ScoreDocComparator() {
449
450 public final int compare(final ScoreDoc i, final ScoreDoc j) {
451 String is = index[i.doc];
452 String js = index[j.doc];
453 if (is == js) {
454 return 0;
455 } else if (is == null) {
456 return -1;
457 } else if (js == null) {
458 return 1;
459 } else {
460 return collator.compare(is, js);
461 }
462 }
463
464 public Comparable sortValue (final ScoreDoc i) {
465 return index[i.doc];
466 }
467
468 public int sortType() {
469 return SortField.STRING;
470 }
471 };
472 }
473
474 /**
475 * Returns a comparator for sorting hits according to values in the given field.
476 * The terms in the field are looked at to determine whether they contain integers,
477 * floats or strings. Once the type is determined, one of the other static methods
478 * in this class is called to get the comparator.
479 * @param reader Index to use.
480 * @param fieldname Fieldable containg values.
481 * @return Comparator for sorting hits.
482 * @throws IOException If an error occurs reading the index.
483 */
484 static ScoreDocComparator comparatorAuto (final IndexReader reader, final String fieldname)
485 throws IOException {
486 final String field = fieldname.intern();
487 Object lookupArray = ExtendedFieldCache.EXT_DEFAULT.getAuto (reader, field);
488 if (lookupArray instanceof FieldCache.StringIndex) {
489 return comparatorString (reader, field);
490 } else if (lookupArray instanceof int[]) {
491 return comparatorInt (reader, field);
492 } else if (lookupArray instanceof long[]) {
493 return comparatorLong (reader, field);
494 } else if (lookupArray instanceof float[]) {
495 return comparatorFloat (reader, field);
496 } else if (lookupArray instanceof String[]) {
497 return comparatorString (reader, field);
498 } else {
499 throw new RuntimeException ("unknown data type in field '"+field+"'");
500 }
501 }
502 }
Save This Page