001: package org.apache.lucene.search.spans;
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: import java.util.List;
023: import java.util.ArrayList;
024:
025: import org.apache.lucene.index.IndexReader;
026: import org.apache.lucene.util.PriorityQueue;
027:
028: class NearSpansUnordered implements Spans {
029: private SpanNearQuery query;
030:
031: private List ordered = new ArrayList(); // spans in query order
032: private int slop; // from query
033:
034: private SpansCell first; // linked list of spans
035: private SpansCell last; // sorted by doc only
036:
037: private int totalLength; // sum of current lengths
038:
039: private CellQueue queue; // sorted queue of spans
040: private SpansCell max; // max element in queue
041:
042: private boolean more = true; // true iff not done
043: private boolean firstTime = true; // true before first next()
044:
045: private class CellQueue extends PriorityQueue {
046: public CellQueue(int size) {
047: initialize(size);
048: }
049:
050: protected final boolean lessThan(Object o1, Object o2) {
051: SpansCell spans1 = (SpansCell) o1;
052: SpansCell spans2 = (SpansCell) o2;
053: if (spans1.doc() == spans2.doc()) {
054: return NearSpansOrdered.docSpansOrdered(spans1, spans2);
055: } else {
056: return spans1.doc() < spans2.doc();
057: }
058: }
059: }
060:
061: /** Wraps a Spans, and can be used to form a linked list. */
062: private class SpansCell implements Spans {
063: private Spans spans;
064: private SpansCell next;
065: private int length = -1;
066: private int index;
067:
068: public SpansCell(Spans spans, int index) {
069: this .spans = spans;
070: this .index = index;
071: }
072:
073: public boolean next() throws IOException {
074: return adjust(spans.next());
075: }
076:
077: public boolean skipTo(int target) throws IOException {
078: return adjust(spans.skipTo(target));
079: }
080:
081: private boolean adjust(boolean condition) {
082: if (length != -1) {
083: totalLength -= length; // subtract old length
084: }
085: if (condition) {
086: length = end() - start();
087: totalLength += length; // add new length
088:
089: if (max == null || doc() > max.doc()
090: || (doc() == max.doc()) && (end() > max.end())) {
091: max = this ;
092: }
093: }
094: more = condition;
095: return condition;
096: }
097:
098: public int doc() {
099: return spans.doc();
100: }
101:
102: public int start() {
103: return spans.start();
104: }
105:
106: public int end() {
107: return spans.end();
108: }
109:
110: public String toString() {
111: return spans.toString() + "#" + index;
112: }
113: }
114:
115: public NearSpansUnordered(SpanNearQuery query, IndexReader reader)
116: throws IOException {
117: this .query = query;
118: this .slop = query.getSlop();
119:
120: SpanQuery[] clauses = query.getClauses();
121: queue = new CellQueue(clauses.length);
122: for (int i = 0; i < clauses.length; i++) {
123: SpansCell cell = new SpansCell(clauses[i].getSpans(reader),
124: i);
125: ordered.add(cell);
126: }
127: }
128:
129: public boolean next() throws IOException {
130: if (firstTime) {
131: initList(true);
132: listToQueue(); // initialize queue
133: firstTime = false;
134: } else if (more) {
135: if (min().next()) { // trigger further scanning
136: queue.adjustTop(); // maintain queue
137: } else {
138: more = false;
139: }
140: }
141:
142: while (more) {
143:
144: boolean queueStale = false;
145:
146: if (min().doc() != max.doc()) { // maintain list
147: queueToList();
148: queueStale = true;
149: }
150:
151: // skip to doc w/ all clauses
152:
153: while (more && first.doc() < last.doc()) {
154: more = first.skipTo(last.doc()); // skip first upto last
155: firstToLast(); // and move it to the end
156: queueStale = true;
157: }
158:
159: if (!more)
160: return false;
161:
162: // found doc w/ all clauses
163:
164: if (queueStale) { // maintain the queue
165: listToQueue();
166: queueStale = false;
167: }
168:
169: if (atMatch()) {
170: return true;
171: }
172:
173: more = min().next();
174: if (more) {
175: queue.adjustTop(); // maintain queue
176: }
177: }
178: return false; // no more matches
179: }
180:
181: public boolean skipTo(int target) throws IOException {
182: if (firstTime) { // initialize
183: initList(false);
184: for (SpansCell cell = first; more && cell != null; cell = cell.next) {
185: more = cell.skipTo(target); // skip all
186: }
187: if (more) {
188: listToQueue();
189: }
190: firstTime = false;
191: } else { // normal case
192: while (more && min().doc() < target) { // skip as needed
193: if (min().skipTo(target)) {
194: queue.adjustTop();
195: } else {
196: more = false;
197: }
198: }
199: }
200: return more && (atMatch() || next());
201: }
202:
203: private SpansCell min() {
204: return (SpansCell) queue.top();
205: }
206:
207: public int doc() {
208: return min().doc();
209: }
210:
211: public int start() {
212: return min().start();
213: }
214:
215: public int end() {
216: return max.end();
217: }
218:
219: public String toString() {
220: return getClass().getName()
221: + "("
222: + query.toString()
223: + ")@"
224: + (firstTime ? "START" : (more ? (doc() + ":" + start()
225: + "-" + end()) : "END"));
226: }
227:
228: private void initList(boolean next) throws IOException {
229: for (int i = 0; more && i < ordered.size(); i++) {
230: SpansCell cell = (SpansCell) ordered.get(i);
231: if (next)
232: more = cell.next(); // move to first entry
233: if (more) {
234: addToList(cell); // add to list
235: }
236: }
237: }
238:
239: private void addToList(SpansCell cell) {
240: if (last != null) { // add next to end of list
241: last.next = cell;
242: } else
243: first = cell;
244: last = cell;
245: cell.next = null;
246: }
247:
248: private void firstToLast() {
249: last.next = first; // move first to end of list
250: last = first;
251: first = first.next;
252: last.next = null;
253: }
254:
255: private void queueToList() {
256: last = first = null;
257: while (queue.top() != null) {
258: addToList((SpansCell) queue.pop());
259: }
260: }
261:
262: private void listToQueue() {
263: queue.clear(); // rebuild queue
264: for (SpansCell cell = first; cell != null; cell = cell.next) {
265: queue.put(cell); // add to queue from list
266: }
267: }
268:
269: private boolean atMatch() {
270: return (min().doc() == max.doc())
271: && ((max.end() - min().start() - totalLength) <= slop);
272: }
273: }
|