1 package org.apache.lucene.search.spans;
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
20 import org.apache.lucene.index.IndexReader;
21 import org.apache.lucene.util.PriorityQueue;
23 import java.io.IOException;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.List;
28 import java.util.HashSet;
31 * Similar to {@link NearSpansOrdered}, but for the unordered case.
34 * Only public for subclassing. Most implementations should not need this class
36 public class NearSpansUnordered extends Spans {
37 private SpanNearQuery query;
39 private List<SpansCell> ordered = new ArrayList<SpansCell>(); // spans in query order
40 private Spans[] subSpans;
41 private int slop; // from query
43 private SpansCell first; // linked list of spans
44 private SpansCell last; // sorted by doc only
46 private int totalLength; // sum of current lengths
48 private CellQueue queue; // sorted queue of spans
49 private SpansCell max; // max element in queue
51 private boolean more = true; // true iff not done
52 private boolean firstTime = true; // true before first next()
54 private class CellQueue extends PriorityQueue<SpansCell> {
55 public CellQueue(int size) {
60 protected final boolean lessThan(SpansCell spans1, SpansCell spans2) {
61 if (spans1.doc() == spans2.doc()) {
62 return NearSpansOrdered.docSpansOrdered(spans1, spans2);
64 return spans1.doc() < spans2.doc();
70 /** Wraps a Spans, and can be used to form a linked list. */
71 private class SpansCell extends Spans {
73 private SpansCell next;
74 private int length = -1;
77 public SpansCell(Spans spans, int index) {
83 public boolean next() throws IOException {
84 return adjust(spans.next());
88 public boolean skipTo(int target) throws IOException {
89 return adjust(spans.skipTo(target));
92 private boolean adjust(boolean condition) {
94 totalLength -= length; // subtract old length
97 length = end() - start();
98 totalLength += length; // add new length
100 if (max == null || doc() > max.doc()
101 || (doc() == max.doc()) && (end() > max.end())) {
110 public int doc() { return spans.doc(); }
113 public int start() { return spans.start(); }
116 public int end() { return spans.end(); }
117 // TODO: Remove warning after API has been finalized
119 public Collection<byte[]> getPayload() throws IOException {
120 return new ArrayList<byte[]>(spans.getPayload());
123 // TODO: Remove warning after API has been finalized
125 public boolean isPayloadAvailable() {
126 return spans.isPayloadAvailable();
130 public String toString() { return spans.toString() + "#" + index; }
134 public NearSpansUnordered(SpanNearQuery query, IndexReader reader)
137 this.slop = query.getSlop();
139 SpanQuery[] clauses = query.getClauses();
140 queue = new CellQueue(clauses.length);
141 subSpans = new Spans[clauses.length];
142 for (int i = 0; i < clauses.length; i++) {
144 new SpansCell(clauses[i].getSpans(reader), i);
146 subSpans[i] = cell.spans;
149 public Spans[] getSubSpans() {
153 public boolean next() throws IOException {
156 listToQueue(); // initialize queue
159 if (min().next()) { // trigger further scanning
160 queue.updateTop(); // maintain queue
168 boolean queueStale = false;
170 if (min().doc() != max.doc()) { // maintain list
175 // skip to doc w/ all clauses
177 while (more && first.doc() < last.doc()) {
178 more = first.skipTo(last.doc()); // skip first upto last
179 firstToLast(); // and move it to the end
183 if (!more) return false;
185 // found doc w/ all clauses
187 if (queueStale) { // maintain the queue
198 queue.updateTop(); // maintain queue
201 return false; // no more matches
205 public boolean skipTo(int target) throws IOException {
206 if (firstTime) { // initialize
208 for (SpansCell cell = first; more && cell!=null; cell=cell.next) {
209 more = cell.skipTo(target); // skip all
215 } else { // normal case
216 while (more && min().doc() < target) { // skip as needed
217 if (min().skipTo(target)) {
224 return more && (atMatch() || next());
227 private SpansCell min() { return queue.top(); }
230 public int doc() { return min().doc(); }
232 public int start() { return min().start(); }
234 public int end() { return max.end(); }
236 // TODO: Remove warning after API has been finalized
238 * WARNING: The List is not necessarily in order of the the positions
239 * @return Collection of <code>byte[]</code> payloads
240 * @throws IOException
243 public Collection<byte[]> getPayload() throws IOException {
244 Set<byte[]> matchPayload = new HashSet<byte[]>();
245 for (SpansCell cell = first; cell != null; cell = cell.next) {
246 if (cell.isPayloadAvailable()) {
247 matchPayload.addAll(cell.getPayload());
253 // TODO: Remove warning after API has been finalized
255 public boolean isPayloadAvailable() {
256 SpansCell pointer = min();
257 while (pointer != null) {
258 if (pointer.isPayloadAvailable()) {
261 pointer = pointer.next;
268 public String toString() {
269 return getClass().getName() + "("+query.toString()+")@"+
270 (firstTime?"START":(more?(doc()+":"+start()+"-"+end()):"END"));
273 private void initList(boolean next) throws IOException {
274 for (int i = 0; more && i < ordered.size(); i++) {
275 SpansCell cell = ordered.get(i);
277 more = cell.next(); // move to first entry
279 addToList(cell); // add to list
284 private void addToList(SpansCell cell) throws IOException {
285 if (last != null) { // add next to end of list
293 private void firstToLast() {
294 last.next = first; // move first to end of list
300 private void queueToList() throws IOException {
302 while (queue.top() != null) {
303 addToList(queue.pop());
307 private void listToQueue() {
308 queue.clear(); // rebuild queue
309 for (SpansCell cell = first; cell != null; cell = cell.next) {
310 queue.add(cell); // add to queue from list
314 private boolean atMatch() {
315 return (min().doc() == max.doc())
316 && ((max.end() - min().start() - totalLength) <= slop);