| package org.apache.lucene.search; |
| |
| /** |
| * Copyright 2004 The Apache Software Foundation |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| import org.apache.lucene.index.IndexReader; |
| import org.apache.lucene.util.PriorityQueue; |
| |
| import java.io.IOException; |
| import java.util.WeakHashMap; |
| import java.util.HashMap; |
| import java.util.Map; |
| import java.util.Locale; |
| import java.text.Collator; |
| |
| /** |
| * Expert: A hit queue for sorting by hits by terms in more than one field. |
| * Uses <code>FieldCache.DEFAULT</code> for maintaining internal term lookup tables. |
| * |
| * <p>Created: Dec 8, 2003 12:56:03 PM |
| * |
| * @author Tim Jones (Nacimiento Software) |
| * @since lucene 1.4 |
| * @version $Id$ |
| * @see Searchable#search(Query,Filter,int,Sort) |
| * @see FieldCache |
| */ |
| class FieldSortedHitQueue |
| extends PriorityQueue { |
| |
| /** |
| * Creates a hit queue sorted by the given list of fields. |
| * @param reader Index to use. |
| * @param fields Field names, in priority order (highest priority first). Cannot be <code>null</code> or empty. |
| * @param size The number of hits to retain. Must be greater than zero. |
| * @throws IOException |
| */ |
| FieldSortedHitQueue (IndexReader reader, SortField[] fields, int size) |
| throws IOException { |
| final int n = fields.length; |
| comparators = new ScoreDocComparator[n]; |
| this.fields = new SortField[n]; |
| for (int i=0; i<n; ++i) { |
| String fieldname = fields[i].getField(); |
| comparators[i] = getCachedComparator (reader, fieldname, fields[i].getType(), fields[i].getLocale(), fields[i].getFactory()); |
| this.fields[i] = new SortField (fieldname, comparators[i].sortType(), fields[i].getReverse()); |
| } |
| initialize (size); |
| } |
| |
| |
| /** Stores a comparator corresponding to each field being sorted by */ |
| protected ScoreDocComparator[] comparators; |
| |
| /** Stores the sort criteria being used. */ |
| protected SortField[] fields; |
| |
| /** Stores the maximum score value encountered, for normalizing. |
| * we only care about scores greater than 1.0 - if all the scores |
| * are less than 1.0, we don't have to normalize. */ |
| protected float maxscore = 1.0f; |
| |
| |
| /** |
| * Returns whether <code>a</code> is less relevant than <code>b</code>. |
| * @param a ScoreDoc |
| * @param b ScoreDoc |
| * @return <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>. |
| */ |
| protected final boolean lessThan (final Object a, final Object b) { |
| final ScoreDoc docA = (ScoreDoc) a; |
| final ScoreDoc docB = (ScoreDoc) b; |
| |
| // keep track of maximum score |
| if (docA.score > maxscore) maxscore = docA.score; |
| if (docB.score > maxscore) maxscore = docB.score; |
| |
| // run comparators |
| final int n = comparators.length; |
| int c = 0; |
| for (int i=0; i<n && c==0; ++i) { |
| c = (fields[i].reverse) ? comparators[i].compare (docB, docA) |
| : comparators[i].compare (docA, docB); |
| } |
| // avoid random sort order that could lead to duplicates (bug #31241): |
| if (c == 0) |
| return docA.doc > docB.doc; |
| return c > 0; |
| } |
| |
| |
| /** |
| * Given a FieldDoc object, stores the values used |
| * to sort the given document. These values are not the raw |
| * values out of the index, but the internal representation |
| * of them. This is so the given search hit can be collated |
| * by a MultiSearcher with other search hits. |
| * @param doc The FieldDoc to store sort values into. |
| * @return The same FieldDoc passed in. |
| * @see Searchable#search(Query,Filter,int,Sort) |
| */ |
| FieldDoc fillFields (final FieldDoc doc) { |
| final int n = comparators.length; |
| final Comparable[] fields = new Comparable[n]; |
| for (int i=0; i<n; ++i) |
| fields[i] = comparators[i].sortValue(doc); |
| doc.fields = fields; |
| if (maxscore > 1.0f) doc.score /= maxscore; // normalize scores |
| return doc; |
| } |
| |
| |
| /** Returns the SortFields being used by this hit queue. */ |
| SortField[] getFields() { |
| return fields; |
| } |
| |
| /** Internal cache of comparators. Similar to FieldCache, only |
| * caches comparators instead of term values. */ |
| static final Map Comparators = new WeakHashMap(); |
| |
| /** Returns a comparator if it is in the cache. */ |
| static ScoreDocComparator lookup (IndexReader reader, String field, int type, Object factory) { |
| FieldCacheImpl.Entry entry = (factory != null) |
| ? new FieldCacheImpl.Entry (field, factory) |
| : new FieldCacheImpl.Entry (field, type); |
| synchronized (Comparators) { |
| HashMap readerCache = (HashMap)Comparators.get(reader); |
| if (readerCache == null) return null; |
| return (ScoreDocComparator) readerCache.get (entry); |
| } |
| } |
| |
| /** Stores a comparator into the cache. */ |
| static Object store (IndexReader reader, String field, int type, Object factory, Object value) { |
| FieldCacheImpl.Entry entry = (factory != null) |
| ? new FieldCacheImpl.Entry (field, factory) |
| : new FieldCacheImpl.Entry (field, type); |
| synchronized (Comparators) { |
| HashMap readerCache = (HashMap)Comparators.get(reader); |
| if (readerCache == null) { |
| readerCache = new HashMap(); |
| Comparators.put(reader,readerCache); |
| } |
| return readerCache.put (entry, value); |
| } |
| } |
| |
| static ScoreDocComparator getCachedComparator (IndexReader reader, String fieldname, int type, Locale locale, SortComparatorSource factory) |
| throws IOException { |
| if (type == SortField.DOC) return ScoreDocComparator.INDEXORDER; |
| if (type == SortField.SCORE) return ScoreDocComparator.RELEVANCE; |
| ScoreDocComparator comparator = lookup (reader, fieldname, type, factory); |
| if (comparator == null) { |
| switch (type) { |
| case SortField.AUTO: |
| comparator = comparatorAuto (reader, fieldname); |
| break; |
| case SortField.INT: |
| comparator = comparatorInt (reader, fieldname); |
| break; |
| case SortField.FLOAT: |
| comparator = comparatorFloat (reader, fieldname); |
| break; |
| case SortField.STRING: |
| if (locale != null) comparator = comparatorStringLocale (reader, fieldname, locale); |
| else comparator = comparatorString (reader, fieldname); |
| break; |
| case SortField.CUSTOM: |
| comparator = factory.newComparator (reader, fieldname); |
| break; |
| default: |
| throw new RuntimeException ("unknown field type: "+type); |
| } |
| store (reader, fieldname, type, factory, comparator); |
| } |
| return comparator; |
| } |
| |
| /** |
| * Returns a comparator for sorting hits according to a field containing integers. |
| * @param reader Index to use. |
| * @param fieldname Field containg integer values. |
| * @return Comparator for sorting hits. |
| * @throws IOException If an error occurs reading the index. |
| */ |
| static ScoreDocComparator comparatorInt (final IndexReader reader, final String fieldname) |
| throws IOException { |
| final String field = fieldname.intern(); |
| final int[] fieldOrder = FieldCache.DEFAULT.getInts (reader, field); |
| return new ScoreDocComparator() { |
| |
| public final int compare (final ScoreDoc i, final ScoreDoc j) { |
| final int fi = fieldOrder[i.doc]; |
| final int fj = fieldOrder[j.doc]; |
| if (fi < fj) return -1; |
| if (fi > fj) return 1; |
| return 0; |
| } |
| |
| public Comparable sortValue (final ScoreDoc i) { |
| return new Integer (fieldOrder[i.doc]); |
| } |
| |
| public int sortType() { |
| return SortField.INT; |
| } |
| }; |
| } |
| |
| /** |
| * Returns a comparator for sorting hits according to a field containing floats. |
| * @param reader Index to use. |
| * @param fieldname Field containg float values. |
| * @return Comparator for sorting hits. |
| * @throws IOException If an error occurs reading the index. |
| */ |
| static ScoreDocComparator comparatorFloat (final IndexReader reader, final String fieldname) |
| throws IOException { |
| final String field = fieldname.intern(); |
| final float[] fieldOrder = FieldCache.DEFAULT.getFloats (reader, field); |
| return new ScoreDocComparator () { |
| |
| public final int compare (final ScoreDoc i, final ScoreDoc j) { |
| final float fi = fieldOrder[i.doc]; |
| final float fj = fieldOrder[j.doc]; |
| if (fi < fj) return -1; |
| if (fi > fj) return 1; |
| return 0; |
| } |
| |
| public Comparable sortValue (final ScoreDoc i) { |
| return new Float (fieldOrder[i.doc]); |
| } |
| |
| public int sortType() { |
| return SortField.FLOAT; |
| } |
| }; |
| } |
| |
| /** |
| * Returns a comparator for sorting hits according to a field containing strings. |
| * @param reader Index to use. |
| * @param fieldname Field containg string values. |
| * @return Comparator for sorting hits. |
| * @throws IOException If an error occurs reading the index. |
| */ |
| static ScoreDocComparator comparatorString (final IndexReader reader, final String fieldname) |
| throws IOException { |
| final String field = fieldname.intern(); |
| final FieldCache.StringIndex index = FieldCache.DEFAULT.getStringIndex (reader, field); |
| return new ScoreDocComparator () { |
| |
| public final int compare (final ScoreDoc i, final ScoreDoc j) { |
| final int fi = index.order[i.doc]; |
| final int fj = index.order[j.doc]; |
| if (fi < fj) return -1; |
| if (fi > fj) return 1; |
| return 0; |
| } |
| |
| public Comparable sortValue (final ScoreDoc i) { |
| return index.lookup[index.order[i.doc]]; |
| } |
| |
| public int sortType() { |
| return SortField.STRING; |
| } |
| }; |
| } |
| |
| /** |
| * Returns a comparator for sorting hits according to a field containing strings. |
| * @param reader Index to use. |
| * @param fieldname Field containg string values. |
| * @return Comparator for sorting hits. |
| * @throws IOException If an error occurs reading the index. |
| */ |
| static ScoreDocComparator comparatorStringLocale (final IndexReader reader, final String fieldname, final Locale locale) |
| throws IOException { |
| final Collator collator = Collator.getInstance (locale); |
| final String field = fieldname.intern(); |
| final String[] index = FieldCache.DEFAULT.getStrings (reader, field); |
| return new ScoreDocComparator() { |
| |
| public final int compare (final ScoreDoc i, final ScoreDoc j) { |
| return collator.compare (index[i.doc], index[j.doc]); |
| } |
| |
| public Comparable sortValue (final ScoreDoc i) { |
| return index[i.doc]; |
| } |
| |
| public int sortType() { |
| return SortField.STRING; |
| } |
| }; |
| } |
| |
| /** |
| * Returns a comparator for sorting hits according to values in the given field. |
| * The terms in the field are looked at to determine whether they contain integers, |
| * floats or strings. Once the type is determined, one of the other static methods |
| * in this class is called to get the comparator. |
| * @param reader Index to use. |
| * @param fieldname Field containg values. |
| * @return Comparator for sorting hits. |
| * @throws IOException If an error occurs reading the index. |
| */ |
| static ScoreDocComparator comparatorAuto (final IndexReader reader, final String fieldname) |
| throws IOException { |
| final String field = fieldname.intern(); |
| Object lookupArray = FieldCache.DEFAULT.getAuto (reader, field); |
| if (lookupArray instanceof FieldCache.StringIndex) { |
| return comparatorString (reader, field); |
| } else if (lookupArray instanceof int[]) { |
| return comparatorInt (reader, field); |
| } else if (lookupArray instanceof float[]) { |
| return comparatorFloat (reader, field); |
| } else if (lookupArray instanceof String[]) { |
| return comparatorString (reader, field); |
| } else { |
| throw new RuntimeException ("unknown data type in field '"+field+"'"); |
| } |
| } |
| } |