+++ /dev/null
-package org.apache.lucene.search.spans;
-
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.util.PriorityQueue;
-
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-import java.util.Set;
-import java.util.HashSet;
-
-/**
- * Similar to {@link NearSpansOrdered}, but for the unordered case.
- *
- * Expert:
- * Only public for subclassing. Most implementations should not need this class
- */
-public class NearSpansUnordered extends Spans {
- private SpanNearQuery query;
-
- private List<SpansCell> ordered = new ArrayList<SpansCell>(); // spans in query order
- private Spans[] subSpans;
- private int slop; // from query
-
- private SpansCell first; // linked list of spans
- private SpansCell last; // sorted by doc only
-
- private int totalLength; // sum of current lengths
-
- private CellQueue queue; // sorted queue of spans
- private SpansCell max; // max element in queue
-
- private boolean more = true; // true iff not done
- private boolean firstTime = true; // true before first next()
-
- private class CellQueue extends PriorityQueue<SpansCell> {
- public CellQueue(int size) {
- initialize(size);
- }
-
- @Override
- protected final boolean lessThan(SpansCell spans1, SpansCell spans2) {
- if (spans1.doc() == spans2.doc()) {
- return NearSpansOrdered.docSpansOrdered(spans1, spans2);
- } else {
- return spans1.doc() < spans2.doc();
- }
- }
- }
-
-
- /** Wraps a Spans, and can be used to form a linked list. */
- private class SpansCell extends Spans {
- private Spans spans;
- private SpansCell next;
- private int length = -1;
- private int index;
-
- public SpansCell(Spans spans, int index) {
- this.spans = spans;
- this.index = index;
- }
-
- @Override
- public boolean next() throws IOException {
- return adjust(spans.next());
- }
-
- @Override
- public boolean skipTo(int target) throws IOException {
- return adjust(spans.skipTo(target));
- }
-
- private boolean adjust(boolean condition) {
- if (length != -1) {
- totalLength -= length; // subtract old length
- }
- if (condition) {
- length = end() - start();
- totalLength += length; // add new length
-
- if (max == null || doc() > max.doc()
- || (doc() == max.doc()) && (end() > max.end())) {
- max = this;
- }
- }
- more = condition;
- return condition;
- }
-
- @Override
- public int doc() { return spans.doc(); }
-
- @Override
- public int start() { return spans.start(); }
-
- @Override
- public int end() { return spans.end(); }
- // TODO: Remove warning after API has been finalized
- @Override
- public Collection<byte[]> getPayload() throws IOException {
- return new ArrayList<byte[]>(spans.getPayload());
- }
-
- // TODO: Remove warning after API has been finalized
- @Override
- public boolean isPayloadAvailable() {
- return spans.isPayloadAvailable();
- }
-
- @Override
- public String toString() { return spans.toString() + "#" + index; }
- }
-
-
- public NearSpansUnordered(SpanNearQuery query, IndexReader reader)
- throws IOException {
- this.query = query;
- this.slop = query.getSlop();
-
- SpanQuery[] clauses = query.getClauses();
- queue = new CellQueue(clauses.length);
- subSpans = new Spans[clauses.length];
- for (int i = 0; i < clauses.length; i++) {
- SpansCell cell =
- new SpansCell(clauses[i].getSpans(reader), i);
- ordered.add(cell);
- subSpans[i] = cell.spans;
- }
- }
- public Spans[] getSubSpans() {
- return subSpans;
- }
- @Override
- public boolean next() throws IOException {
- if (firstTime) {
- initList(true);
- listToQueue(); // initialize queue
- firstTime = false;
- } else if (more) {
- if (min().next()) { // trigger further scanning
- queue.updateTop(); // maintain queue
- } else {
- more = false;
- }
- }
-
- while (more) {
-
- boolean queueStale = false;
-
- if (min().doc() != max.doc()) { // maintain list
- queueToList();
- queueStale = true;
- }
-
- // skip to doc w/ all clauses
-
- while (more && first.doc() < last.doc()) {
- more = first.skipTo(last.doc()); // skip first upto last
- firstToLast(); // and move it to the end
- queueStale = true;
- }
-
- if (!more) return false;
-
- // found doc w/ all clauses
-
- if (queueStale) { // maintain the queue
- listToQueue();
- queueStale = false;
- }
-
- if (atMatch()) {
- return true;
- }
-
- more = min().next();
- if (more) {
- queue.updateTop(); // maintain queue
- }
- }
- return false; // no more matches
- }
-
- @Override
- public boolean skipTo(int target) throws IOException {
- if (firstTime) { // initialize
- initList(false);
- for (SpansCell cell = first; more && cell!=null; cell=cell.next) {
- more = cell.skipTo(target); // skip all
- }
- if (more) {
- listToQueue();
- }
- firstTime = false;
- } else { // normal case
- while (more && min().doc() < target) { // skip as needed
- if (min().skipTo(target)) {
- queue.updateTop();
- } else {
- more = false;
- }
- }
- }
- return more && (atMatch() || next());
- }
-
- private SpansCell min() { return queue.top(); }
-
- @Override
- public int doc() { return min().doc(); }
- @Override
- public int start() { return min().start(); }
- @Override
- public int end() { return max.end(); }
-
- // TODO: Remove warning after API has been finalized
- /**
- * WARNING: The List is not necessarily in order of the the positions
- * @return Collection of <code>byte[]</code> payloads
- * @throws IOException
- */
- @Override
- public Collection<byte[]> getPayload() throws IOException {
- Set<byte[]> matchPayload = new HashSet<byte[]>();
- for (SpansCell cell = first; cell != null; cell = cell.next) {
- if (cell.isPayloadAvailable()) {
- matchPayload.addAll(cell.getPayload());
- }
- }
- return matchPayload;
- }
-
- // TODO: Remove warning after API has been finalized
- @Override
- public boolean isPayloadAvailable() {
- SpansCell pointer = min();
- while (pointer != null) {
- if (pointer.isPayloadAvailable()) {
- return true;
- }
- pointer = pointer.next;
- }
-
- return false;
- }
-
- @Override
- public String toString() {
- return getClass().getName() + "("+query.toString()+")@"+
- (firstTime?"START":(more?(doc()+":"+start()+"-"+end()):"END"));
- }
-
- private void initList(boolean next) throws IOException {
- for (int i = 0; more && i < ordered.size(); i++) {
- SpansCell cell = ordered.get(i);
- if (next)
- more = cell.next(); // move to first entry
- if (more) {
- addToList(cell); // add to list
- }
- }
- }
-
- private void addToList(SpansCell cell) throws IOException {
- if (last != null) { // add next to end of list
- last.next = cell;
- } else
- first = cell;
- last = cell;
- cell.next = null;
- }
-
- private void firstToLast() {
- last.next = first; // move first to end of list
- last = first;
- first = first.next;
- last.next = null;
- }
-
- private void queueToList() throws IOException {
- last = first = null;
- while (queue.top() != null) {
- addToList(queue.pop());
- }
- }
-
- private void listToQueue() {
- queue.clear(); // rebuild queue
- for (SpansCell cell = first; cell != null; cell = cell.next) {
- queue.add(cell); // add to queue from list
- }
- }
-
- private boolean atMatch() {
- return (min().doc() == max.doc())
- && ((max.end() - min().start() - totalLength) <= slop);
- }
-}
fnp / pylucene.git / blobdiff