KickJava   Java API By Example, From Geeks To Geeks.

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


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 java.io.IOException JavaDoc;
20 import java.util.ArrayList JavaDoc;
21 import java.util.Arrays JavaDoc;
22 import java.util.Comparator JavaDoc;
23
24 /**
25  * The Scorer for DisjunctionMaxQuery's. The union of all documents generated by the the subquery scorers
26  * is generated in document number order. The score for each document is the maximum of the scores computed
27  * by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
28  * for the other subqueries that generate the document.
29  * @author Chuck Williams
30  */
31 class DisjunctionMaxScorer extends Scorer {
32
33     /* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
34     private ArrayList JavaDoc subScorers = new ArrayList JavaDoc();
35
36     /* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
37     private float tieBreakerMultiplier;
38
39     private boolean more = false; // True iff there is a next document
40 private boolean firstTime = true; // True iff next() has not yet been called
41
42     /** Creates a new instance of DisjunctionMaxScorer
43      * @param tieBreakerMultiplier Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result.
44      * @param similarity -- not used since our definition involves neither coord nor terms directly */
45     public DisjunctionMaxScorer(float tieBreakerMultiplier, Similarity similarity) {
46         super(similarity);
47         this.tieBreakerMultiplier = tieBreakerMultiplier;
48     }
49
50     /** Add the scorer for a subquery
51      * @param scorer the scorer of a subquery of our associated DisjunctionMaxQuery
52      */
53     public void add(Scorer scorer) throws IOException JavaDoc {
54         if (scorer.next()) { // Initialize and retain only if it produces docs
55 subScorers.add(scorer);
56             more = true;
57         }
58     }
59
60     /** Generate the next document matching our associated DisjunctionMaxQuery.
61      * @return true iff there is a next document
62      */
63     public boolean next() throws IOException JavaDoc {
64         if (!more) return false;
65         if (firstTime) {
66             heapify();
67             firstTime = false;
68             return true; // more would have been false if no subScorers had any docs
69 }
70         // Increment all generators that generated the last doc and adjust the heap.
71 int lastdoc = ((Scorer) subScorers.get(0)).doc();
72         do {
73             if (((Scorer) subScorers.get(0)).next())
74                 heapAdjust(0);
75             else {
76                 heapRemoveRoot();
77                 if (subScorers.isEmpty()) return (more = false);
78             }
79         } while ( ((Scorer) subScorers.get(0)).doc()==lastdoc );
80         return true;
81     }
82
83     /** Determine the current document number. Initially invalid, until {@link #next()} is called the first time.
84      * @return the document number of the currently generated document
85      */
86     public int doc() {
87         return ((Scorer) subScorers.get(0)).doc();
88     }
89
90     /** Determine the current document score. Initially invalid, until {@link #next()} is called the first time.
91      * @return the score of the current generated document
92      */
93     public float score() throws IOException JavaDoc {
94         int doc = ((Scorer) subScorers.get(0)).doc();
95         float[] sum = {((Scorer) subScorers.get(0)).score()}, max = {sum[0]};
96         int size = subScorers.size();
97         scoreAll(1, size, doc, sum, max);
98         scoreAll(2, size, doc, sum, max);
99         return max[0] + (sum[0] - max[0])*tieBreakerMultiplier;
100     }
101
102     // Recursively iterate all subScorers that generated last doc computing sum and max
103 private void scoreAll(int root, int size, int doc, float[] sum, float[] max) throws IOException JavaDoc {
104         if (root<size && ((Scorer) subScorers.get(root)).doc() == doc) {
105             float sub = ((Scorer) subScorers.get(root)).score();
106             sum[0] += sub;
107             max[0] = Math.max(max[0], sub);
108             scoreAll((root<<1)+1, size, doc, sum, max);
109             scoreAll((root<<1)+2, size, doc, sum, max);
110         }
111     }
112
113     /** Advance to the first document beyond the current whose number is greater than or equal to target.
114      * @param target the minimum number of the next desired document
115      * @return true iff there is a document to be generated whose number is at least target
116      */
117     public boolean skipTo(int target) throws IOException JavaDoc {
118         while (subScorers.size()>0 && ((Scorer)subScorers.get(0)).doc()<target) {
119             if (((Scorer)subScorers.get(0)).skipTo(target))
120                 heapAdjust(0);
121             else
122                 heapRemoveRoot();
123         }
124         if ((subScorers.size()==0))
125             return (more = false);
126         return true;
127     }
128
129     /** Explain a score that we computed. UNSUPPORTED -- see explanation capability in DisjunctionMaxQuery.
130      * @param doc the number of a document we scored
131      * @return the Explanation for our score
132      */
133     public Explanation explain(int doc) throws IOException JavaDoc {
134         throw new UnsupportedOperationException JavaDoc();
135     }
136
137     // Organize subScorers into a min heap with scorers generating the earlest document on top.
138 private void heapify() {
139         int size = subScorers.size();
140         for (int i=(size>>1)-1; i>=0; i--)
141             heapAdjust(i);
142     }
143
144     /* The subtree of subScorers at root is a min heap except possibly for its root element.
145      * Bubble the root down as required to make the subtree a heap.
146      */
147     private void heapAdjust(int root) {
148         Scorer scorer=(Scorer)subScorers.get(root);
149         int doc=scorer.doc();
150         int i=root, size=subScorers.size();
151         while (i<=(size>>1)-1) {
152             int lchild=(i<<1)+1;
153             Scorer lscorer=(Scorer)subScorers.get(lchild);
154             int ldoc=lscorer.doc();
155             int rdoc=Integer.MAX_VALUE, rchild=(i<<1)+2;
156             Scorer rscorer=null;
157             if (rchild<size) {
158                 rscorer=(Scorer)subScorers.get(rchild);
159                 rdoc=rscorer.doc();
160             }
161             if (ldoc<doc) {
162                 if (rdoc<ldoc) {
163                     subScorers.set(i, rscorer);
164                     subScorers.set(rchild, scorer);
165                     i=rchild;
166                 } else {
167                     subScorers.set(i, lscorer);
168                     subScorers.set(lchild, scorer);
169                     i=lchild;
170                 }
171             } else if (rdoc<doc) {
172                 subScorers.set(i, rscorer);
173                 subScorers.set(rchild, scorer);
174                 i=rchild;
175             } else return;
176         }
177     }
178
179     // Remove the root Scorer from subScorers and re-establish it as a heap
180 private void heapRemoveRoot() {
181         int size=subScorers.size();
182         if (size==1)
183             subScorers.remove(0);
184         else {
185             subScorers.set(0, subScorers.get(size-1));
186             subScorers.remove(size-1);
187             heapAdjust(0);
188         }
189     }
190
191 }
192
Popular Tags