KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > lucene > search > FieldSortedHitQueue


1 package org.apache.lucene.search;
2
3 /**
4  * Copyright 2004 The Apache Software Foundation
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18
19 import org.apache.lucene.index.IndexReader;
20 import org.apache.lucene.util.PriorityQueue;
21
22 import java.io.IOException JavaDoc;
23 import java.util.WeakHashMap JavaDoc;
24 import java.util.HashMap JavaDoc;
25 import java.util.Map JavaDoc;
26 import java.util.Locale JavaDoc;
27 import java.text.Collator JavaDoc;
28
29 /**
30  * Expert: A hit queue for sorting by hits by terms in more than one field.
31  * Uses <code>FieldCache.DEFAULT</code> for maintaining internal term lookup tables.
32  *
33  * <p>Created: Dec 8, 2003 12:56:03 PM
34  *
35  * @author Tim Jones (Nacimiento Software)
36  * @since lucene 1.4
37  * @version $Id: FieldSortedHitQueue.java 374436 2006-02-02 16:55:26Z yonik $
38  * @see Searcher#search(Query,Filter,int,Sort)
39  * @see FieldCache
40  */
41 public class FieldSortedHitQueue
42 extends PriorityQueue {
43
44   /**
45    * Creates a hit queue sorted by the given list of fields.
46    * @param reader Index to use.
47    * @param fields Field names, in priority order (highest priority first). Cannot be <code>null</code> or empty.
48    * @param size The number of hits to retain. Must be greater than zero.
49    * @throws IOException
50    */
51   public FieldSortedHitQueue (IndexReader reader, SortField[] fields, int size)
52   throws IOException JavaDoc {
53     final int n = fields.length;
54     comparators = new ScoreDocComparator[n];
55     this.fields = new SortField[n];
56     for (int i=0; i<n; ++i) {
57       String JavaDoc fieldname = fields[i].getField();
58       comparators[i] = getCachedComparator (reader, fieldname, fields[i].getType(), fields[i].getLocale(), fields[i].getFactory());
59       this.fields[i] = new SortField (fieldname, comparators[i].sortType(), fields[i].getReverse());
60     }
61     initialize (size);
62   }
63
64
65   /** Stores a comparator corresponding to each field being sorted by */
66   protected ScoreDocComparator[] comparators;
67
68   /** Stores the sort criteria being used. */
69   protected SortField[] fields;
70
71   /** Stores the maximum score value encountered, needed for normalizing. */
72   protected float maxscore = Float.NEGATIVE_INFINITY;
73
74   /** returns the maximum score encountered by elements inserted via insert()
75    */
76   public float getMaxScore() {
77     return maxscore;
78   }
79
80   // The signature of this method takes a FieldDoc in order to avoid
81 // the unneeded cast to retrieve the score.
82 // inherit javadoc
83 public boolean insert(FieldDoc fdoc) {
84     maxscore = Math.max(maxscore,fdoc.score);
85     return super.insert(fdoc);
86   }
87
88   // This overrides PriorityQueue.insert() so that insert(FieldDoc) that
89 // keeps track of the score isn't accidentally bypassed.
90 // inherit javadoc
91 public boolean insert(Object JavaDoc fdoc) {
92     return insert((FieldDoc)fdoc);
93   }
94
95   /**
96    * Returns whether <code>a</code> is less relevant than <code>b</code>.
97    * @param a ScoreDoc
98    * @param b ScoreDoc
99    * @return <code>true</code> if document <code>a</code> should be sorted after document <code>b</code>.
100    */
101   protected boolean lessThan (final Object JavaDoc a, final Object JavaDoc b) {
102     final ScoreDoc docA = (ScoreDoc) a;
103     final ScoreDoc docB = (ScoreDoc) b;
104
105     // run comparators
106 final int n = comparators.length;
107     int c = 0;
108     for (int i=0; i<n && c==0; ++i) {
109       c = (fields[i].reverse) ? comparators[i].compare (docB, docA)
110                               : comparators[i].compare (docA, docB);
111     }
112     // avoid random sort order that could lead to duplicates (bug #31241):
113 if (c == 0)
114       return docA.doc > docB.doc;
115     return c > 0;
116   }
117
118
119   /**
120    * Given a FieldDoc object, stores the values used
121    * to sort the given document. These values are not the raw
122    * values out of the index, but the internal representation
123    * of them. This is so the given search hit can be collated
124    * by a MultiSearcher with other search hits.
125    * @param doc The FieldDoc to store sort values into.
126    * @return The same FieldDoc passed in.
127    * @see Searchable#search(Weight,Filter,int,Sort)
128    */
129   FieldDoc fillFields (final FieldDoc doc) {
130     final int n = comparators.length;
131     final Comparable JavaDoc[] fields = new Comparable JavaDoc[n];
132     for (int i=0; i<n; ++i)
133       fields[i] = comparators[i].sortValue(doc);
134     doc.fields = fields;
135     //if (maxscore > 1.0f) doc.score /= maxscore; // normalize scores
136 return doc;
137   }
138
139
140   /** Returns the SortFields being used by this hit queue. */
141   SortField[] getFields() {
142     return fields;
143   }
144
145   /** Internal cache of comparators. Similar to FieldCache, only
146    * caches comparators instead of term values. */
147   static final Map JavaDoc Comparators = new WeakHashMap JavaDoc();
148
149   /** Returns a comparator if it is in the cache. */
150   static ScoreDocComparator lookup (IndexReader reader, String JavaDoc field, int type, Object JavaDoc factory) {
151     FieldCacheImpl.Entry entry = (factory != null)
152       ? new FieldCacheImpl.Entry (field, factory)
153       : new FieldCacheImpl.Entry (field, type);
154     synchronized (Comparators) {
155       HashMap JavaDoc readerCache = (HashMap JavaDoc)Comparators.get(reader);
156       if (readerCache == null) return null;
157       return (ScoreDocComparator) readerCache.get (entry);
158     }
159   }
160
161   /** Stores a comparator into the cache. */
162   static Object JavaDoc store (IndexReader reader, String JavaDoc field, int type, Object JavaDoc factory, Object JavaDoc value) {
163     FieldCacheImpl.Entry entry = (factory != null)
164       ? new FieldCacheImpl.Entry (field, factory)
165       : new FieldCacheImpl.Entry (field, type);
166     synchronized (Comparators) {
167       HashMap JavaDoc readerCache = (HashMap JavaDoc)Comparators.get(reader);
168       if (readerCache == null) {
169         readerCache = new HashMap JavaDoc();
170         Comparators.put(reader,readerCache);
171       }
172       return readerCache.put (entry, value);
173     }
174   }
175
176   static ScoreDocComparator getCachedComparator (IndexReader reader, String JavaDoc fieldname, int type, Locale JavaDoc locale, SortComparatorSource factory)
177   throws IOException JavaDoc {
178     if (type == SortField.DOC) return ScoreDocComparator.INDEXORDER;
179     if (type == SortField.SCORE) return ScoreDocComparator.RELEVANCE;
180     ScoreDocComparator comparator = lookup (reader, fieldname, type, factory);
181     if (comparator == null) {
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.STRING:
193           if (locale != null) comparator = comparatorStringLocale (reader, fieldname, locale);
194           else comparator = comparatorString (reader, fieldname);
195           break;
196         case SortField.CUSTOM:
197           comparator = factory.newComparator (reader, fieldname);
198           break;
199         default:
200           throw new RuntimeException JavaDoc ("unknown field type: "+type);
201       }
202       store (reader, fieldname, type, factory, comparator);
203     }
204     return comparator;
205   }
206
207   /**
208    * Returns a comparator for sorting hits according to a field containing integers.
209    * @param reader Index to use.
210    * @param fieldname Field containg integer values.
211    * @return Comparator for sorting hits.
212    * @throws IOException If an error occurs reading the index.
213    */
214   static ScoreDocComparator comparatorInt (final IndexReader reader, final String JavaDoc fieldname)
215   throws IOException JavaDoc {
216     final String JavaDoc field = fieldname.intern();
217     final int[] fieldOrder = FieldCache.DEFAULT.getInts (reader, field);
218     return new ScoreDocComparator() {
219
220       public final int compare (final ScoreDoc i, final ScoreDoc j) {
221         final int fi = fieldOrder[i.doc];
222         final int fj = fieldOrder[j.doc];
223         if (fi < fj) return -1;
224         if (fi > fj) return 1;
225         return 0;
226       }
227
228       public Comparable JavaDoc sortValue (final ScoreDoc i) {
229         return new Integer JavaDoc (fieldOrder[i.doc]);
230       }
231
232       public int sortType() {
233         return SortField.INT;
234       }
235     };
236   }
237
238   /**
239    * Returns a comparator for sorting hits according to a field containing floats.
240    * @param reader Index to use.
241    * @param fieldname Field containg float values.
242    * @return Comparator for sorting hits.
243    * @throws IOException If an error occurs reading the index.
244    */
245   static ScoreDocComparator comparatorFloat (final IndexReader reader, final String JavaDoc fieldname)
246   throws IOException JavaDoc {
247     final String JavaDoc field = fieldname.intern();
248     final float[] fieldOrder = FieldCache.DEFAULT.getFloats (reader, field);
249     return new ScoreDocComparator () {
250
251       public final int compare (final ScoreDoc i, final ScoreDoc j) {
252         final float fi = fieldOrder[i.doc];
253         final float fj = fieldOrder[j.doc];
254         if (fi < fj) return -1;
255         if (fi > fj) return 1;
256         return 0;
257       }
258
259       public Comparable JavaDoc sortValue (final ScoreDoc i) {
260         return new Float JavaDoc (fieldOrder[i.doc]);
261       }
262
263       public int sortType() {
264         return SortField.FLOAT;
265       }
266     };
267   }
268
269   /**
270    * Returns a comparator for sorting hits according to a field containing strings.
271    * @param reader Index to use.
272    * @param fieldname Field containg string values.
273    * @return Comparator for sorting hits.
274    * @throws IOException If an error occurs reading the index.
275    */
276   static ScoreDocComparator comparatorString (final IndexReader reader, final String JavaDoc fieldname)
277   throws IOException JavaDoc {
278     final String JavaDoc field = fieldname.intern();
279     final FieldCache.StringIndex index = FieldCache.DEFAULT.getStringIndex (reader, field);
280     return new ScoreDocComparator () {
281
282       public final int compare (final ScoreDoc i, final ScoreDoc j) {
283         final int fi = index.order[i.doc];
284         final int fj = index.order[j.doc];
285         if (fi < fj) return -1;
286         if (fi > fj) return 1;
287         return 0;
288       }
289
290       public Comparable JavaDoc sortValue (final ScoreDoc i) {
291         return index.lookup[index.order[i.doc]];
292       }
293
294       public int sortType() {
295         return SortField.STRING;
296       }
297     };
298   }
299
300   /**
301    * Returns a comparator for sorting hits according to a field containing strings.
302    * @param reader Index to use.
303    * @param fieldname Field containg string values.
304    * @return Comparator for sorting hits.
305    * @throws IOException If an error occurs reading the index.
306    */
307   static ScoreDocComparator comparatorStringLocale (final IndexReader reader, final String JavaDoc fieldname, final Locale JavaDoc locale)
308   throws IOException JavaDoc {
309     final Collator JavaDoc collator = Collator.getInstance (locale);
310     final String JavaDoc field = fieldname.intern();
311     final String JavaDoc[] index = FieldCache.DEFAULT.getStrings (reader, field);
312     return new ScoreDocComparator() {
313
314       public final int compare (final ScoreDoc i, final ScoreDoc j) {
315         return collator.compare (index[i.doc], index[j.doc]);
316       }
317
318       public Comparable JavaDoc sortValue (final ScoreDoc i) {
319         return index[i.doc];
320       }
321
322       public int sortType() {
323         return SortField.STRING;
324       }
325     };
326   }
327
328   /**
329    * Returns a comparator for sorting hits according to values in the given field.
330    * The terms in the field are looked at to determine whether they contain integers,
331    * floats or strings. Once the type is determined, one of the other static methods
332    * in this class is called to get the comparator.
333    * @param reader Index to use.
334    * @param fieldname Field containg values.
335    * @return Comparator for sorting hits.
336    * @throws IOException If an error occurs reading the index.
337    */
338   static ScoreDocComparator comparatorAuto (final IndexReader reader, final String JavaDoc fieldname)
339   throws IOException JavaDoc {
340     final String JavaDoc field = fieldname.intern();
341     Object JavaDoc lookupArray = FieldCache.DEFAULT.getAuto (reader, field);
342     if (lookupArray instanceof FieldCache.StringIndex) {
343       return comparatorString (reader, field);
344     } else if (lookupArray instanceof int[]) {
345       return comparatorInt (reader, field);
346     } else if (lookupArray instanceof float[]) {
347       return comparatorFloat (reader, field);
348     } else if (lookupArray instanceof String JavaDoc[]) {
349       return comparatorString (reader, field);
350     } else {
351       throw new RuntimeException JavaDoc ("unknown data type in field '"+field+"'");
352     }
353   }
354 }
355
Popular Tags