001: package org.apache.lucene.search;
002:
003: /**
004: * Licensed to the Apache Software Foundation (ASF) under one or more
005: * contributor license agreements. See the NOTICE file distributed with
006: * this work for additional information regarding copyright ownership.
007: * The ASF licenses this file to You under the Apache License, Version 2.0
008: * (the "License"); you may not use this file except in compliance with
009: * the License. You may obtain a copy of the License at
010: *
011: * http://www.apache.org/licenses/LICENSE-2.0
012: *
013: * Unless required by applicable law or agreed to in writing, software
014: * distributed under the License is distributed on an "AS IS" BASIS,
015: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016: * See the License for the specific language governing permissions and
017: * limitations under the License.
018: */
019:
020: import org.apache.lucene.index.IndexReader;
021: import org.apache.lucene.util.PriorityQueue;
022:
023: import java.io.IOException;
024: import java.text.Collator;
025: import java.util.Locale;
026:
027: /**
028: * Expert: A hit queue for sorting by hits by terms in more than one field.
029: * Uses <code>FieldCache.DEFAULT</code> for maintaining internal term lookup tables.
030: *
031: * <p>Created: Dec 8, 2003 12:56:03 PM
032: *
033: * @author Tim Jones (Nacimiento Software)
034: * @since lucene 1.4
035: * @version $Id: FieldSortedHitQueue.java 605225 2007-12-18 15:13:05Z gsingers $
036: * @see Searcher#search(Query,Filter,int,Sort)
037: * @see FieldCache
038: */
039: public class FieldSortedHitQueue extends PriorityQueue {
040:
041: /**
042: * Creates a hit queue sorted by the given list of fields.
043: * @param reader Index to use.
044: * @param fields Fieldable names, in priority order (highest priority first). Cannot be <code>null</code> or empty.
045: * @param size The number of hits to retain. Must be greater than zero.
046: * @throws IOException
047: */
048: public FieldSortedHitQueue(IndexReader reader, SortField[] fields,
049: int size) throws IOException {
050: final int n = fields.length;
051: comparators = new ScoreDocComparator[n];
052: this .fields = new SortField[n];
053: for (int i = 0; i < n; ++i) {
054: String fieldname = fields[i].getField();
055: comparators[i] = getCachedComparator(reader, fieldname,
056: fields[i].getType(), fields[i].getLocale(),
057: fields[i].getFactory());
058:
059: if (comparators[i].sortType() == SortField.STRING) {
060: this .fields[i] = new SortField(fieldname, fields[i]
061: .getLocale(), fields[i].getReverse());
062: } else {
063: this .fields[i] = new SortField(fieldname,
064: comparators[i].sortType(), fields[i]
065: .getReverse());
066: }
067: }
068: initialize(size);
069: }
070:
071: /** Stores a comparator corresponding to each field being sorted by */
072: protected ScoreDocComparator[] comparators;
073:
074: /** Stores the sort criteria being used. */
075: protected SortField[] fields;
076:
077: /** Stores the maximum score value encountered, needed for normalizing. */
078: protected float maxscore = Float.NEGATIVE_INFINITY;
079:
080: /** returns the maximum score encountered by elements inserted via insert()
081: */
082: public float getMaxScore() {
083: return maxscore;
084: }
085:
086: // Update maxscore.
087: private final void updateMaxScore(FieldDoc fdoc) {
088: maxscore = Math.max(maxscore, fdoc.score);
089: }
090:
091: // The signature of this method takes a FieldDoc in order to avoid
092: // the unneeded cast to retrieve the score.
093: // inherit javadoc
094: public boolean insert(FieldDoc fdoc) {
095: updateMaxScore(fdoc);
096: return super .insert(fdoc);
097: }
098:
099: // This overrides PriorityQueue.insert() so that insert(FieldDoc) that
100: // keeps track of the score isn't accidentally bypassed.
101: // inherit javadoc
102: public boolean insert(Object fdoc) {
103: return insert((FieldDoc) fdoc);
104: }
105:
106: // This overrides PriorityQueue.insertWithOverflow() so that
107: // updateMaxScore(FieldDoc) that keeps track of the score isn't accidentally
108: // bypassed.
109: public Object insertWithOverflow(Object element) {
110: updateMaxScore((FieldDoc) element);
111: return super .insertWithOverflow(element);
112: }
113:
114: /**
115: * Returns whether <code>a</code> is less relevant than <code>b</code>.
116: * @param a ScoreDoc
117: * @param b ScoreDoc
118: * @return <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>.
119: */
120: protected boolean lessThan(final Object a, final Object b) {
121: final ScoreDoc docA = (ScoreDoc) a;
122: final ScoreDoc docB = (ScoreDoc) b;
123:
124: // run comparators
125: final int n = comparators.length;
126: int c = 0;
127: for (int i = 0; i < n && c == 0; ++i) {
128: c = (fields[i].reverse) ? comparators[i]
129: .compare(docB, docA) : comparators[i].compare(docA,
130: docB);
131: }
132: // avoid random sort order that could lead to duplicates (bug #31241):
133: if (c == 0)
134: return docA.doc > docB.doc;
135: return c > 0;
136: }
137:
138: /**
139: * Given a FieldDoc object, stores the values used
140: * to sort the given document. These values are not the raw
141: * values out of the index, but the internal representation
142: * of them. This is so the given search hit can be collated
143: * by a MultiSearcher with other search hits.
144: * @param doc The FieldDoc to store sort values into.
145: * @return The same FieldDoc passed in.
146: * @see Searchable#search(Weight,Filter,int,Sort)
147: */
148: FieldDoc fillFields(final FieldDoc doc) {
149: final int n = comparators.length;
150: final Comparable[] fields = new Comparable[n];
151: for (int i = 0; i < n; ++i)
152: fields[i] = comparators[i].sortValue(doc);
153: doc.fields = fields;
154: //if (maxscore > 1.0f) doc.score /= maxscore; // normalize scores
155: return doc;
156: }
157:
158: /** Returns the SortFields being used by this hit queue. */
159: SortField[] getFields() {
160: return fields;
161: }
162:
163: static ScoreDocComparator getCachedComparator(IndexReader reader,
164: String field, int type, Locale locale,
165: SortComparatorSource factory) throws IOException {
166: if (type == SortField.DOC)
167: return ScoreDocComparator.INDEXORDER;
168: if (type == SortField.SCORE)
169: return ScoreDocComparator.RELEVANCE;
170: FieldCacheImpl.Entry entry = (factory != null) ? new FieldCacheImpl.Entry(
171: field, factory)
172: : new FieldCacheImpl.Entry(field, type, locale);
173: return (ScoreDocComparator) Comparators.get(reader, entry);
174: }
175:
176: /** Internal cache of comparators. Similar to FieldCache, only
177: * caches comparators instead of term values. */
178: static final FieldCacheImpl.Cache Comparators = new FieldCacheImpl.Cache() {
179:
180: protected Object createValue(IndexReader reader, Object entryKey)
181: throws IOException {
182: FieldCacheImpl.Entry entry = (FieldCacheImpl.Entry) entryKey;
183: String fieldname = entry.field;
184: int type = entry.type;
185: Locale locale = entry.locale;
186: SortComparatorSource factory = (SortComparatorSource) entry.custom;
187: ScoreDocComparator comparator;
188: switch (type) {
189: case SortField.AUTO:
190: comparator = comparatorAuto(reader, fieldname);
191: break;
192: case SortField.INT:
193: comparator = comparatorInt(reader, fieldname);
194: break;
195: case SortField.FLOAT:
196: comparator = comparatorFloat(reader, fieldname);
197: break;
198: case SortField.LONG:
199: comparator = comparatorLong(reader, fieldname);
200: break;
201: case SortField.DOUBLE:
202: comparator = comparatorDouble(reader, fieldname);
203: break;
204: case SortField.STRING:
205: if (locale != null)
206: comparator = comparatorStringLocale(reader,
207: fieldname, locale);
208: else
209: comparator = comparatorString(reader, fieldname);
210: break;
211: case SortField.CUSTOM:
212: comparator = factory.newComparator(reader, fieldname);
213: break;
214: default:
215: throw new RuntimeException("unknown field type: "
216: + type);
217: }
218: return comparator;
219: }
220: };
221:
222: /**
223: * Returns a comparator for sorting hits according to a field containing integers.
224: * @param reader Index to use.
225: * @param fieldname Fieldable containg integer values.
226: * @return Comparator for sorting hits.
227: * @throws IOException If an error occurs reading the index.
228: */
229: static ScoreDocComparator comparatorInt(final IndexReader reader,
230: final String fieldname) throws IOException {
231: final String field = fieldname.intern();
232: final int[] fieldOrder = FieldCache.DEFAULT.getInts(reader,
233: field);
234: return new ScoreDocComparator() {
235:
236: public final int compare(final ScoreDoc i, final ScoreDoc j) {
237: final int fi = fieldOrder[i.doc];
238: final int fj = fieldOrder[j.doc];
239: if (fi < fj)
240: return -1;
241: if (fi > fj)
242: return 1;
243: return 0;
244: }
245:
246: public Comparable sortValue(final ScoreDoc i) {
247: return new Integer(fieldOrder[i.doc]);
248: }
249:
250: public int sortType() {
251: return SortField.INT;
252: }
253: };
254: }
255:
256: /**
257: * Returns a comparator for sorting hits according to a field containing integers.
258: * @param reader Index to use.
259: * @param fieldname Fieldable containg integer values.
260: * @return Comparator for sorting hits.
261: * @throws IOException If an error occurs reading the index.
262: */
263: static ScoreDocComparator comparatorLong(final IndexReader reader,
264: final String fieldname) throws IOException {
265: final String field = fieldname.intern();
266: final long[] fieldOrder = ExtendedFieldCache.EXT_DEFAULT
267: .getLongs(reader, field);
268: return new ScoreDocComparator() {
269:
270: public final int compare(final ScoreDoc i, final ScoreDoc j) {
271: final long li = fieldOrder[i.doc];
272: final long lj = fieldOrder[j.doc];
273: if (li < lj)
274: return -1;
275: if (li > lj)
276: return 1;
277: return 0;
278: }
279:
280: public Comparable sortValue(final ScoreDoc i) {
281: return new Long(fieldOrder[i.doc]);
282: }
283:
284: public int sortType() {
285: return SortField.LONG;
286: }
287: };
288: }
289:
290: /**
291: * Returns a comparator for sorting hits according to a field containing floats.
292: * @param reader Index to use.
293: * @param fieldname Fieldable containg float values.
294: * @return Comparator for sorting hits.
295: * @throws IOException If an error occurs reading the index.
296: */
297: static ScoreDocComparator comparatorFloat(final IndexReader reader,
298: final String fieldname) throws IOException {
299: final String field = fieldname.intern();
300: final float[] fieldOrder = FieldCache.DEFAULT.getFloats(reader,
301: field);
302: return new ScoreDocComparator() {
303:
304: public final int compare(final ScoreDoc i, final ScoreDoc j) {
305: final float fi = fieldOrder[i.doc];
306: final float fj = fieldOrder[j.doc];
307: if (fi < fj)
308: return -1;
309: if (fi > fj)
310: return 1;
311: return 0;
312: }
313:
314: public Comparable sortValue(final ScoreDoc i) {
315: return new Float(fieldOrder[i.doc]);
316: }
317:
318: public int sortType() {
319: return SortField.FLOAT;
320: }
321: };
322: }
323:
324: /**
325: * Returns a comparator for sorting hits according to a field containing doubles.
326: * @param reader Index to use.
327: * @param fieldname Fieldable containg float values.
328: * @return Comparator for sorting hits.
329: * @throws IOException If an error occurs reading the index.
330: */
331: static ScoreDocComparator comparatorDouble(
332: final IndexReader reader, final String fieldname)
333: throws IOException {
334: final String field = fieldname.intern();
335: final double[] fieldOrder = ExtendedFieldCache.EXT_DEFAULT
336: .getDoubles(reader, field);
337: return new ScoreDocComparator() {
338:
339: public final int compare(final ScoreDoc i, final ScoreDoc j) {
340: final double di = fieldOrder[i.doc];
341: final double dj = fieldOrder[j.doc];
342: if (di < dj)
343: return -1;
344: if (di > dj)
345: return 1;
346: return 0;
347: }
348:
349: public Comparable sortValue(final ScoreDoc i) {
350: return new Double(fieldOrder[i.doc]);
351: }
352:
353: public int sortType() {
354: return SortField.DOUBLE;
355: }
356: };
357: }
358:
359: /**
360: * Returns a comparator for sorting hits according to a field containing strings.
361: * @param reader Index to use.
362: * @param fieldname Fieldable containg string values.
363: * @return Comparator for sorting hits.
364: * @throws IOException If an error occurs reading the index.
365: */
366: static ScoreDocComparator comparatorString(
367: final IndexReader reader, final String fieldname)
368: throws IOException {
369: final String field = fieldname.intern();
370: final FieldCache.StringIndex index = FieldCache.DEFAULT
371: .getStringIndex(reader, field);
372: return new ScoreDocComparator() {
373:
374: public final int compare(final ScoreDoc i, final ScoreDoc j) {
375: final int fi = index.order[i.doc];
376: final int fj = index.order[j.doc];
377: if (fi < fj)
378: return -1;
379: if (fi > fj)
380: return 1;
381: return 0;
382: }
383:
384: public Comparable sortValue(final ScoreDoc i) {
385: return index.lookup[index.order[i.doc]];
386: }
387:
388: public int sortType() {
389: return SortField.STRING;
390: }
391: };
392: }
393:
394: /**
395: * Returns a comparator for sorting hits according to a field containing strings.
396: * @param reader Index to use.
397: * @param fieldname Fieldable containg string values.
398: * @return Comparator for sorting hits.
399: * @throws IOException If an error occurs reading the index.
400: */
401: static ScoreDocComparator comparatorStringLocale(
402: final IndexReader reader, final String fieldname,
403: final Locale locale) throws IOException {
404: final Collator collator = Collator.getInstance(locale);
405: final String field = fieldname.intern();
406: final String[] index = FieldCache.DEFAULT.getStrings(reader,
407: field);
408: return new ScoreDocComparator() {
409:
410: public final int compare(final ScoreDoc i, final ScoreDoc j) {
411: String is = index[i.doc];
412: String js = index[j.doc];
413: if (is == js) {
414: return 0;
415: } else if (is == null) {
416: return -1;
417: } else if (js == null) {
418: return 1;
419: } else {
420: return collator.compare(is, js);
421: }
422: }
423:
424: public Comparable sortValue(final ScoreDoc i) {
425: return index[i.doc];
426: }
427:
428: public int sortType() {
429: return SortField.STRING;
430: }
431: };
432: }
433:
434: /**
435: * Returns a comparator for sorting hits according to values in the given field.
436: * The terms in the field are looked at to determine whether they contain integers,
437: * floats or strings. Once the type is determined, one of the other static methods
438: * in this class is called to get the comparator.
439: * @param reader Index to use.
440: * @param fieldname Fieldable containg values.
441: * @return Comparator for sorting hits.
442: * @throws IOException If an error occurs reading the index.
443: */
444: static ScoreDocComparator comparatorAuto(final IndexReader reader,
445: final String fieldname) throws IOException {
446: final String field = fieldname.intern();
447: Object lookupArray = ExtendedFieldCache.EXT_DEFAULT.getAuto(
448: reader, field);
449: if (lookupArray instanceof FieldCache.StringIndex) {
450: return comparatorString(reader, field);
451: } else if (lookupArray instanceof int[]) {
452: return comparatorInt(reader, field);
453: } else if (lookupArray instanceof long[]) {
454: return comparatorLong(reader, field);
455: } else if (lookupArray instanceof float[]) {
456: return comparatorFloat(reader, field);
457: } else if (lookupArray instanceof String[]) {
458: return comparatorString(reader, field);
459: } else {
460: throw new RuntimeException("unknown data type in field '"
461: + field + "'");
462: }
463: }
464: }
|