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 java.io.IOException;
021:
022: final class BooleanScorer extends Scorer {
023: private SubScorer scorers = null;
024: private BucketTable bucketTable = new BucketTable();
025:
026: private int maxCoord = 1;
027: private float[] coordFactors = null;
028:
029: private int requiredMask = 0;
030: private int prohibitedMask = 0;
031: private int nextMask = 1;
032:
033: private final int minNrShouldMatch;
034:
035: BooleanScorer(Similarity similarity) {
036: this (similarity, 1);
037: }
038:
039: BooleanScorer(Similarity similarity, int minNrShouldMatch) {
040: super (similarity);
041: this .minNrShouldMatch = minNrShouldMatch;
042: }
043:
044: static final class SubScorer {
045: public Scorer scorer;
046: public boolean done;
047: public boolean required = false;
048: public boolean prohibited = false;
049: public HitCollector collector;
050: public SubScorer next;
051:
052: public SubScorer(Scorer scorer, boolean required,
053: boolean prohibited, HitCollector collector,
054: SubScorer next) throws IOException {
055: this .scorer = scorer;
056: this .done = !scorer.next();
057: this .required = required;
058: this .prohibited = prohibited;
059: this .collector = collector;
060: this .next = next;
061: }
062: }
063:
064: final void add(Scorer scorer, boolean required, boolean prohibited)
065: throws IOException {
066: int mask = 0;
067: if (required || prohibited) {
068: if (nextMask == 0)
069: throw new IndexOutOfBoundsException(
070: "More than 32 required/prohibited clauses in query.");
071: mask = nextMask;
072: nextMask = nextMask << 1;
073: } else
074: mask = 0;
075:
076: if (!prohibited)
077: maxCoord++;
078:
079: if (prohibited)
080: prohibitedMask |= mask; // update prohibited mask
081: else if (required)
082: requiredMask |= mask; // update required mask
083:
084: scorers = new SubScorer(scorer, required, prohibited,
085: bucketTable.newCollector(mask), scorers);
086: }
087:
088: private final void computeCoordFactors() {
089: coordFactors = new float[maxCoord];
090: for (int i = 0; i < maxCoord; i++)
091: coordFactors[i] = getSimilarity().coord(i, maxCoord - 1);
092: }
093:
094: private int end;
095: private Bucket current;
096:
097: public void score(HitCollector hc) throws IOException {
098: next();
099: score(hc, Integer.MAX_VALUE);
100: }
101:
102: protected boolean score(HitCollector hc, int max)
103: throws IOException {
104: if (coordFactors == null)
105: computeCoordFactors();
106:
107: boolean more;
108: Bucket tmp;
109:
110: do {
111: bucketTable.first = null;
112:
113: while (current != null) { // more queued
114:
115: // check prohibited & required
116: if ((current.bits & prohibitedMask) == 0
117: && (current.bits & requiredMask) == requiredMask) {
118:
119: if (current.doc >= max) {
120: tmp = current;
121: current = current.next;
122: tmp.next = bucketTable.first;
123: bucketTable.first = tmp;
124: continue;
125: }
126:
127: if (current.coord >= minNrShouldMatch) {
128: hc.collect(current.doc, current.score
129: * coordFactors[current.coord]);
130: }
131: }
132:
133: current = current.next; // pop the queue
134: }
135:
136: if (bucketTable.first != null) {
137: current = bucketTable.first;
138: bucketTable.first = current.next;
139: return true;
140: }
141:
142: // refill the queue
143: more = false;
144: end += BucketTable.SIZE;
145: for (SubScorer sub = scorers; sub != null; sub = sub.next) {
146: if (!sub.done) {
147: sub.done = !sub.scorer.score(sub.collector, end);
148: if (!sub.done)
149: more = true;
150: }
151: }
152: current = bucketTable.first;
153:
154: } while (current != null || more);
155:
156: return false;
157: }
158:
159: public int doc() {
160: return current.doc;
161: }
162:
163: public boolean next() throws IOException {
164: boolean more;
165: do {
166: while (bucketTable.first != null) { // more queued
167: current = bucketTable.first;
168: bucketTable.first = current.next; // pop the queue
169:
170: // check prohibited & required, and minNrShouldMatch
171: if ((current.bits & prohibitedMask) == 0
172: && (current.bits & requiredMask) == requiredMask
173: && current.coord >= minNrShouldMatch) {
174: return true;
175: }
176: }
177:
178: // refill the queue
179: more = false;
180: end += BucketTable.SIZE;
181: for (SubScorer sub = scorers; sub != null; sub = sub.next) {
182: Scorer scorer = sub.scorer;
183: while (!sub.done && scorer.doc() < end) {
184: sub.collector.collect(scorer.doc(), scorer.score());
185: sub.done = !scorer.next();
186: }
187: if (!sub.done) {
188: more = true;
189: }
190: }
191: } while (bucketTable.first != null || more);
192:
193: return false;
194: }
195:
196: public float score() {
197: if (coordFactors == null)
198: computeCoordFactors();
199: return current.score * coordFactors[current.coord];
200: }
201:
202: static final class Bucket {
203: int doc = -1; // tells if bucket is valid
204: float score; // incremental score
205: int bits; // used for bool constraints
206: int coord; // count of terms in score
207: Bucket next; // next valid bucket
208: }
209:
210: /** A simple hash table of document scores within a range. */
211: static final class BucketTable {
212: public static final int SIZE = 1 << 11;
213: public static final int MASK = SIZE - 1;
214:
215: final Bucket[] buckets = new Bucket[SIZE];
216: Bucket first = null; // head of valid list
217:
218: public BucketTable() {
219: }
220:
221: public final int size() {
222: return SIZE;
223: }
224:
225: public HitCollector newCollector(int mask) {
226: return new Collector(mask, this );
227: }
228: }
229:
230: static final class Collector extends HitCollector {
231: private BucketTable bucketTable;
232: private int mask;
233:
234: public Collector(int mask, BucketTable bucketTable) {
235: this .mask = mask;
236: this .bucketTable = bucketTable;
237: }
238:
239: public final void collect(final int doc, final float score) {
240: final BucketTable table = bucketTable;
241: final int i = doc & BucketTable.MASK;
242: Bucket bucket = table.buckets[i];
243: if (bucket == null)
244: table.buckets[i] = bucket = new Bucket();
245:
246: if (bucket.doc != doc) { // invalid bucket
247: bucket.doc = doc; // set doc
248: bucket.score = score; // initialize score
249: bucket.bits = mask; // initialize mask
250: bucket.coord = 1; // initialize coord
251:
252: bucket.next = table.first; // push onto valid list
253: table.first = bucket;
254: } else { // valid bucket
255: bucket.score += score; // increment score
256: bucket.bits |= mask; // add bits in mask
257: bucket.coord++; // increment coord
258: }
259: }
260: }
261:
262: public boolean skipTo(int target) {
263: throw new UnsupportedOperationException();
264: }
265:
266: public Explanation explain(int doc) {
267: throw new UnsupportedOperationException();
268: }
269:
270: public String toString() {
271: StringBuffer buffer = new StringBuffer();
272: buffer.append("boolean(");
273: for (SubScorer sub = scorers; sub != null; sub = sub.next) {
274: buffer.append(sub.scorer.toString());
275: buffer.append(" ");
276: }
277: buffer.append(")");
278: return buffer.toString();
279: }
280:
281: }
|