You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/03/31 10:27:46 UTC
svn commit: r1670272 [1/3] - in /lucene/dev/trunk/lucene: ./
core/src/java/org/apache/lucene/search/
core/src/java/org/apache/lucene/search/payloads/
core/src/java/org/apache/lucene/search/spans/
core/src/test/org/apache/lucene/search/ core/src/test/or...
Author: mikemccand
Date: Tue Mar 31 08:27:45 2015
New Revision: 1670272
URL: http://svn.apache.org/r1670272
Log:
LUCENE-6308: cutover Spans to DISI, reuse ConjunctionDISI, use two-phased iteration
Added:
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpans.java (with props)
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java (with props)
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestSpansEnum.java (with props)
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadNearQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadSpanUtil.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadTermQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FieldMaskingSpanQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FilterSpans.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanFirstQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearPayloadCheckQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNotQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanOrQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanPayloadCheckQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionCheckQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionRangeQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanScorer.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanTermQuery.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanWeight.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/Spans.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/TermSpans.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/package-info.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/TestPositionIncrement.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/payloads/TestPayloadTermQuery.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/JustCompileSearchSpans.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/MultiSpansWrapper.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestBasics.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestFieldMaskingSpanQuery.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestPayloadSpans.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/search/spans/TestSpans.java
lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/WeightedSpanTermExtractor.java
lucene/dev/trunk/lucene/highlighter/src/test/org/apache/lucene/search/postingshighlight/TestMultiTermHighlighting.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Tue Mar 31 08:27:45 2015
@@ -32,6 +32,15 @@ API Changes
* LUCENE-6067: Accountable.getChildResources has a default
implementation returning the empty list. (Robert Muir)
+======================= Lucene 5.2.0 =======================
+
+New Features
+
+* LUCENE-6308: Span queries now share document conjunction/intersection
+ code with boolean queries, and use two-phased iterators for
+ faster intersection by avoiding loading positions in certain cases.
+ (Paul Elschot, Robert Muir via Mike McCandless)
+
======================= Lucene 5.1.0 =======================
New Features
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java Tue Mar 31 08:27:45 2015
@@ -23,8 +23,14 @@ import java.util.Comparator;
import java.util.List;
import org.apache.lucene.util.CollectionUtil;
+import org.apache.lucene.search.spans.Spans;
-class ConjunctionDISI extends DocIdSetIterator {
+/** A conjunction of DocIdSetIterators.
+ * This iterates over the doc ids that are present in each given DocIdSetIterator.
+ * <br>Public only for use in {@link org.apache.lucene.search.spans}.
+ * @lucene.internal
+ */
+public class ConjunctionDISI extends DocIdSetIterator {
/** Create a conjunction over the provided iterators, taking advantage of
* {@link TwoPhaseIterator}. */
@@ -32,18 +38,16 @@ class ConjunctionDISI extends DocIdSetIt
final List<DocIdSetIterator> allIterators = new ArrayList<>();
final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
for (DocIdSetIterator iterator : iterators) {
- if (iterator instanceof Scorer) {
- // if we have a scorer, check if it supports two-phase iteration
- TwoPhaseIterator twoPhaseIterator = ((Scorer) iterator).asTwoPhaseIterator();
- if (twoPhaseIterator != null) {
- // Note:
- allIterators.add(twoPhaseIterator.approximation());
- twoPhaseIterators.add(twoPhaseIterator);
- } else {
- allIterators.add(iterator);
- }
- } else {
- // no approximation support, use the iterator as-is
+ TwoPhaseIterator twoPhaseIterator = null;
+ if (iterator instanceof Scorer) {
+ twoPhaseIterator = ((Scorer) iterator).asTwoPhaseIterator();
+ } else if (iterator instanceof Spans) {
+ twoPhaseIterator = ((Spans) iterator).asTwoPhaseIterator();
+ }
+ if (twoPhaseIterator != null) {
+ allIterators.add(twoPhaseIterator.approximation());
+ twoPhaseIterators.add(twoPhaseIterator);
+ } else { // no approximation support, use the iterator as-is
allIterators.add(iterator);
}
}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadNearQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadNearQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadNearQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadNearQuery.java Tue Mar 31 08:27:45 2015
@@ -26,7 +26,6 @@ import org.apache.lucene.search.ComplexE
import org.apache.lucene.search.Explanation;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Scorer;
-import org.apache.lucene.search.Weight;
import org.apache.lucene.search.similarities.DefaultSimilarity;
import org.apache.lucene.search.similarities.Similarity;
import org.apache.lucene.search.similarities.Similarity.SimScorer;
@@ -71,7 +70,7 @@ public class PayloadNearQuery extends Sp
}
@Override
- public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+ public SpanWeight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
return new PayloadNearSpanWeight(this, searcher);
}
@@ -113,7 +112,7 @@ public class PayloadNearQuery extends Sp
@Override
public int hashCode() {
final int prime = 31;
- int result = super.hashCode();
+ int result = super.hashCode() ^ getClass().hashCode();
result = prime * result + ((fieldName == null) ? 0 : fieldName.hashCode());
result = prime * result + ((function == null) ? 0 : function.hashCode());
return result;
@@ -149,8 +148,10 @@ public class PayloadNearQuery extends Sp
@Override
public Scorer scorer(LeafReaderContext context, Bits acceptDocs) throws IOException {
- return new PayloadNearSpanScorer(query.getSpans(context, acceptDocs, termContexts), this,
- similarity, similarity.simScorer(stats, context));
+ Spans spans = query.getSpans(context, acceptDocs, termContexts);
+ return (spans == null)
+ ? null
+ : new PayloadNearSpanScorer(spans, this, similarity, similarity.simScorer(stats, context));
}
@Override
@@ -188,7 +189,7 @@ public class PayloadNearQuery extends Sp
protected float payloadScore;
private int payloadsSeen;
- protected PayloadNearSpanScorer(Spans spans, Weight weight,
+ protected PayloadNearSpanScorer(Spans spans, SpanWeight weight,
Similarity similarity, Similarity.SimScorer docScorer) throws IOException {
super(spans, weight, docScorer);
this.spans = spans;
@@ -200,13 +201,13 @@ public class PayloadNearQuery extends Sp
if (subSpans[i] instanceof NearSpansOrdered) {
if (((NearSpansOrdered) subSpans[i]).isPayloadAvailable()) {
processPayloads(((NearSpansOrdered) subSpans[i]).getPayload(),
- subSpans[i].start(), subSpans[i].end());
+ subSpans[i].startPosition(), subSpans[i].endPosition());
}
getPayloads(((NearSpansOrdered) subSpans[i]).getSubSpans());
} else if (subSpans[i] instanceof NearSpansUnordered) {
if (((NearSpansUnordered) subSpans[i]).isPayloadAvailable()) {
processPayloads(((NearSpansUnordered) subSpans[i]).getPayload(),
- subSpans[i].start(), subSpans[i].end());
+ subSpans[i].startPosition(), subSpans[i].endPosition());
}
getPayloads(((NearSpansUnordered) subSpans[i]).getSubSpans());
}
@@ -233,7 +234,7 @@ public class PayloadNearQuery extends Sp
scratch.length = thePayload.length;
payloadScore = function.currentScore(doc, fieldName, start, end,
payloadsSeen, payloadScore, docScorer.computePayloadFactor(doc,
- spans.start(), spans.end(), scratch));
+ spans.startPosition(), spans.endPosition(), scratch));
++payloadsSeen;
}
}
@@ -241,22 +242,20 @@ public class PayloadNearQuery extends Sp
//
@Override
protected boolean setFreqCurrentDoc() throws IOException {
- if (!more) {
- return false;
- }
- doc = spans.doc();
- freq = 0.0f;
- payloadScore = 0;
- payloadsSeen = 0;
- do {
- int matchLength = spans.end() - spans.start();
- freq += docScorer.computeSlopFactor(matchLength);
- Spans[] spansArr = new Spans[1];
- spansArr[0] = spans;
- getPayloads(spansArr);
- more = spans.next();
- } while (more && (doc == spans.doc()));
- return true;
+ freq = 0.0f;
+ payloadScore = 0;
+ payloadsSeen = 0;
+ int startPos = spans.nextStartPosition();
+ assert startPos != Spans.NO_MORE_POSITIONS : "initial startPos NO_MORE_POSITIONS, spans="+spans;
+ do {
+ int matchLength = spans.endPosition() - startPos;
+ freq += docScorer.computeSlopFactor(matchLength);
+ Spans[] spansArr = new Spans[1];
+ spansArr[0] = spans;
+ getPayloads(spansArr);
+ startPos = spans.nextStartPosition();
+ } while (startPos != Spans.NO_MORE_POSITIONS);
+ return true;
}
@Override
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadSpanUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadSpanUtil.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadSpanUtil.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadSpanUtil.java Tue Mar 31 08:27:45 2015
@@ -169,7 +169,7 @@ public class PayloadSpanUtil {
final boolean inorder = (slop == 0);
SpanNearQuery sp = new SpanNearQuery(clauses, slop + positionGaps,
- inorder);
+ inorder);
sp.setBoost(query.getBoost());
getPayloads(payloads, sp);
}
@@ -186,11 +186,15 @@ public class PayloadSpanUtil {
}
for (LeafReaderContext leafReaderContext : context.leaves()) {
final Spans spans = query.getSpans(leafReaderContext, leafReaderContext.reader().getLiveDocs(), termContexts);
- while (spans.next() == true) {
- if (spans.isPayloadAvailable()) {
- Collection<byte[]> payload = spans.getPayload();
- for (byte [] bytes : payload) {
- payloads.add(bytes);
+ if (spans != null) {
+ while (spans.nextDoc() != Spans.NO_MORE_DOCS) {
+ while (spans.nextStartPosition() != Spans.NO_MORE_POSITIONS) {
+ if (spans.isPayloadAvailable()) {
+ Collection<byte[]> payload = spans.getPayload();
+ for (byte [] bytes : payload) {
+ payloads.add(bytes);
+ }
+ }
}
}
}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadTermQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadTermQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadTermQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/payloads/PayloadTermQuery.java Tue Mar 31 08:27:45 2015
@@ -18,6 +18,7 @@ package org.apache.lucene.search.payload
*/
import java.io.IOException;
+import java.util.Objects;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.PostingsEnum;
@@ -26,10 +27,10 @@ import org.apache.lucene.search.ComplexE
import org.apache.lucene.search.Explanation;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Scorer;
-import org.apache.lucene.search.Weight;
import org.apache.lucene.search.similarities.DefaultSimilarity;
import org.apache.lucene.search.similarities.Similarity;
import org.apache.lucene.search.similarities.Similarity.SimScorer;
+import org.apache.lucene.search.spans.Spans;
import org.apache.lucene.search.spans.SpanQuery;
import org.apache.lucene.search.spans.SpanScorer;
import org.apache.lucene.search.spans.SpanTermQuery;
@@ -60,14 +61,14 @@ public class PayloadTermQuery extends Sp
}
public PayloadTermQuery(Term term, PayloadFunction function,
- boolean includeSpanScore) {
+ boolean includeSpanScore) {
super(term);
- this.function = function;
+ this.function = Objects.requireNonNull(function);
this.includeSpanScore = includeSpanScore;
}
@Override
- public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+ public SpanWeight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
return new PayloadTermWeight(this, searcher);
}
@@ -79,9 +80,11 @@ public class PayloadTermQuery extends Sp
}
@Override
- public Scorer scorer(LeafReaderContext context, Bits acceptDocs) throws IOException {
- return new PayloadTermSpanScorer((TermSpans) query.getSpans(context, acceptDocs, termContexts),
- this, similarity.simScorer(stats, context));
+ public PayloadTermSpanScorer scorer(LeafReaderContext context, Bits acceptDocs) throws IOException {
+ TermSpans spans = (TermSpans) query.getSpans(context, acceptDocs, termContexts);
+ return (spans == null)
+ ? null
+ : new PayloadTermSpanScorer(spans, this, similarity.simScorer(stats, context));
}
protected class PayloadTermSpanScorer extends SpanScorer {
@@ -90,45 +93,42 @@ public class PayloadTermQuery extends Sp
protected int payloadsSeen;
private final TermSpans termSpans;
- public PayloadTermSpanScorer(TermSpans spans, Weight weight, Similarity.SimScorer docScorer) throws IOException {
+ public PayloadTermSpanScorer(TermSpans spans, SpanWeight weight, Similarity.SimScorer docScorer) throws IOException {
super(spans, weight, docScorer);
- termSpans = spans;
+ termSpans = spans; // CHECKME: generics to use SpansScorer.spans as TermSpans.
}
@Override
protected boolean setFreqCurrentDoc() throws IOException {
- if (!more) {
- return false;
- }
- doc = spans.doc();
freq = 0.0f;
numMatches = 0;
payloadScore = 0;
payloadsSeen = 0;
- while (more && doc == spans.doc()) {
- int matchLength = spans.end() - spans.start();
+ int startPos = spans.nextStartPosition();
+ assert startPos != Spans.NO_MORE_POSITIONS : "initial startPos NO_MORE_POSITIONS, spans="+spans;
+ do {
+ int matchLength = spans.endPosition() - startPos;
freq += docScorer.computeSlopFactor(matchLength);
numMatches++;
processPayload(similarity);
- more = spans.next();// this moves positions to the next match in this
- // document
- }
- return more || (freq != 0);
+ startPos = spans.nextStartPosition();
+ } while (startPos != Spans.NO_MORE_POSITIONS);
+ return freq != 0;
}
protected void processPayload(Similarity similarity) throws IOException {
- if (termSpans.isPayloadAvailable()) {
+ if (spans.isPayloadAvailable()) {
final PostingsEnum postings = termSpans.getPostings();
payload = postings.getPayload();
if (payload != null) {
payloadScore = function.currentScore(doc, term.field(),
- spans.start(), spans.end(), payloadsSeen, payloadScore,
- docScorer.computePayloadFactor(doc, spans.start(), spans.end(), payload));
+ spans.startPosition(), spans.endPosition(), payloadsSeen, payloadScore,
+ docScorer.computePayloadFactor(doc, spans.startPosition(), spans.endPosition(), payload));
} else {
payloadScore = function.currentScore(doc, term.field(),
- spans.start(), spans.end(), payloadsSeen, payloadScore, 1F);
+ spans.startPosition(), spans.endPosition(), payloadsSeen, payloadScore, 1F);
}
payloadsSeen++;
@@ -176,7 +176,7 @@ public class PayloadTermQuery extends Sp
@Override
public Explanation explain(LeafReaderContext context, int doc) throws IOException {
- PayloadTermSpanScorer scorer = (PayloadTermSpanScorer) scorer(context, context.reader().getLiveDocs());
+ PayloadTermSpanScorer scorer = scorer(context, context.reader().getLiveDocs());
if (scorer != null) {
int newDoc = scorer.advance(doc);
if (newDoc == doc) {
@@ -220,7 +220,7 @@ public class PayloadTermQuery extends Sp
public int hashCode() {
final int prime = 31;
int result = super.hashCode();
- result = prime * result + ((function == null) ? 0 : function.hashCode());
+ result = prime * result + function.hashCode();
result = prime * result + (includeSpanScore ? 1231 : 1237);
return result;
}
@@ -234,14 +234,9 @@ public class PayloadTermQuery extends Sp
if (getClass() != obj.getClass())
return false;
PayloadTermQuery other = (PayloadTermQuery) obj;
- if (function == null) {
- if (other.function != null)
- return false;
- } else if (!function.equals(other.function))
- return false;
if (includeSpanScore != other.includeSpanScore)
return false;
- return true;
+ return function.equals(other.function);
}
}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FieldMaskingSpanQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FieldMaskingSpanQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FieldMaskingSpanQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FieldMaskingSpanQuery.java Tue Mar 31 08:27:45 2015
@@ -106,7 +106,7 @@ public class FieldMaskingSpanQuery exten
}
@Override
- public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+ public SpanWeight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
return maskedQuery.createWeight(searcher, needsScores);
}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FilterSpans.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FilterSpans.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FilterSpans.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/FilterSpans.java Tue Mar 31 08:27:45 2015
@@ -19,10 +19,13 @@ package org.apache.lucene.search.spans;
import java.io.IOException;
import java.util.Collection;
+import java.util.Objects;
+
+import org.apache.lucene.search.TwoPhaseIterator;
/**
- * A {@link Spans} implementation which allows wrapping another spans instance
- * and override some selected methods.
+ * A {@link Spans} implementation wrapping another spans instance,
+ * allowing to override selected methods in a subclass.
*/
public class FilterSpans extends Spans {
@@ -31,32 +34,37 @@ public class FilterSpans extends Spans {
/** Wrap the given {@link Spans}. */
public FilterSpans(Spans in) {
- this.in = in;
+ this.in = Objects.requireNonNull(in);
}
@Override
- public boolean next() throws IOException {
- return in.next();
+ public int nextDoc() throws IOException {
+ return in.nextDoc();
}
@Override
- public boolean skipTo(int target) throws IOException {
- return in.skipTo(target);
+ public int advance(int target) throws IOException {
+ return in.advance(target);
}
@Override
- public int doc() {
- return in.doc();
+ public int docID() {
+ return in.docID();
}
@Override
- public int start() {
- return in.start();
+ public int nextStartPosition() throws IOException {
+ return in.nextStartPosition();
}
@Override
- public int end() {
- return in.end();
+ public int startPosition() {
+ return in.startPosition();
+ }
+
+ @Override
+ public int endPosition() {
+ return in.endPosition();
}
@Override
@@ -79,4 +87,8 @@ public class FilterSpans extends Spans {
return "Filter(" + in.toString() + ")";
}
+ @Override
+ public TwoPhaseIterator asTwoPhaseIterator() {
+ return in.asTwoPhaseIterator();
+ }
}
Added: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpans.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpans.java?rev=1670272&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpans.java (added)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpans.java Tue Mar 31 08:27:45 2015
@@ -0,0 +1,103 @@
+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.search.DocIdSetIterator;
+import org.apache.lucene.search.ConjunctionDISI;
+import org.apache.lucene.search.TwoPhaseIterator;
+
+import java.io.IOException;
+import java.util.List;
+import java.util.Objects;
+
+/**
+ * Common super class for un/ordered Spans
+ */
+abstract class NearSpans extends Spans {
+ SpanNearQuery query;
+ int allowedSlop;
+
+ List<Spans> subSpans; // in query order
+ DocIdSetIterator conjunction; // use to move to next doc with all clauses
+ boolean atFirstInCurrentDoc;
+ boolean oneExhaustedInCurrentDoc; // no more results possbile in current doc
+
+ NearSpans(SpanNearQuery query, List<Spans> subSpans)
+ throws IOException {
+ this.query = Objects.requireNonNull(query);
+ this.allowedSlop = query.getSlop();
+ if (subSpans.size() < 2) {
+ throw new IllegalArgumentException("Less than 2 subSpans: " + query);
+ }
+ this.subSpans = Objects.requireNonNull(subSpans); // in query order
+ this.conjunction = ConjunctionDISI.intersect(subSpans);
+ }
+
+ @Override
+ public int docID() {
+ return conjunction.docID();
+ }
+
+ @Override
+ public long cost() {
+ return conjunction.cost();
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return (conjunction.nextDoc() == NO_MORE_DOCS)
+ ? NO_MORE_DOCS
+ : toMatchDoc();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ return (conjunction.advance(target) == NO_MORE_DOCS)
+ ? NO_MORE_DOCS
+ : toMatchDoc();
+ }
+
+ abstract int toMatchDoc() throws IOException;
+
+ abstract boolean twoPhaseCurrentDocMatches() throws IOException;
+
+ /**
+ * Return a {@link TwoPhaseIterator} view of this {@link NearSpans}.
+ */
+ @Override
+ public TwoPhaseIterator asTwoPhaseIterator() {
+ TwoPhaseIterator res = new TwoPhaseIterator(conjunction) {
+
+ @Override
+ public boolean matches() throws IOException {
+ return twoPhaseCurrentDocMatches();
+ }
+ };
+ return res;
+ }
+
+ private Spans[] subSpansArray = null; // init only when needed.
+
+ public Spans[] getSubSpans() {
+ if (subSpansArray == null) {
+ subSpansArray = subSpans.toArray(new Spans[subSpans.size()]);
+ }
+ return subSpansArray;
+ }
+
+}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java Tue Mar 31 08:27:45 2015
@@ -17,24 +17,18 @@ package org.apache.lucene.search.spans;
* limitations under the License.
*/
-import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.Term;
-import org.apache.lucene.index.TermContext;
-import org.apache.lucene.util.ArrayUtil;
-import org.apache.lucene.util.Bits;
-import org.apache.lucene.util.InPlaceMergeSorter;
-
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Collection;
-import java.util.Map;
import java.util.Set;
/** A Spans that is formed from the ordered subspans of a SpanNearQuery
- * where the subspans do not overlap and have a maximum slop between them.
+ * where the subspans do not overlap and have a maximum slop between them,
+ * and that does not need to collect payloads.
+ * To also collect payloads, see {@link NearSpansPayloadOrdered}.
* <p>
* The formed spans only contains minimum slop matches.<br>
* The matching slop is computed from the distance(s) between
@@ -55,306 +49,196 @@ import java.util.Set;
* Expert:
* Only public for subclassing. Most implementations should not need this class
*/
-public class NearSpansOrdered extends Spans {
- private final int allowedSlop;
- private boolean firstTime = true;
- private boolean more = false;
-
- /** The spans in the same order as the SpanNearQuery */
- private final Spans[] subSpans;
-
- /** Indicates that all subSpans have same doc() */
- private boolean inSameDoc = false;
-
- private int matchDoc = -1;
- private int matchStart = -1;
- private int matchEnd = -1;
- private List<byte[]> matchPayload;
-
- private final Spans[] subSpansByDoc;
- // Even though the array is probably almost sorted, InPlaceMergeSorter will likely
- // perform better since it has a lower overhead than TimSorter for small arrays
- private final InPlaceMergeSorter sorter = new InPlaceMergeSorter() {
- @Override
- protected void swap(int i, int j) {
- ArrayUtil.swap(subSpansByDoc, i, j);
- }
- @Override
- protected int compare(int i, int j) {
- return subSpansByDoc[i].doc() - subSpansByDoc[j].doc();
- }
- };
-
- private SpanNearQuery query;
- private boolean collectPayloads = true;
-
- public NearSpansOrdered(SpanNearQuery spanNearQuery, LeafReaderContext context, Bits acceptDocs, Map<Term,TermContext> termContexts) throws IOException {
- this(spanNearQuery, context, acceptDocs, termContexts, true);
- }
-
- public NearSpansOrdered(SpanNearQuery spanNearQuery, LeafReaderContext context, Bits acceptDocs, Map<Term,TermContext> termContexts, boolean collectPayloads)
- throws IOException {
- if (spanNearQuery.getClauses().length < 2) {
- throw new IllegalArgumentException("Less than 2 clauses: "
- + spanNearQuery);
- }
- this.collectPayloads = collectPayloads;
- allowedSlop = spanNearQuery.getSlop();
- SpanQuery[] clauses = spanNearQuery.getClauses();
- subSpans = new Spans[clauses.length];
- matchPayload = new LinkedList<>();
- subSpansByDoc = new Spans[clauses.length];
- for (int i = 0; i < clauses.length; i++) {
- subSpans[i] = clauses[i].getSpans(context, acceptDocs, termContexts);
- subSpansByDoc[i] = subSpans[i]; // used in toSameDoc()
- }
- query = spanNearQuery; // kept for toString() only.
- }
-
- // inherit javadocs
- @Override
- public int doc() { return matchDoc; }
+public class NearSpansOrdered extends NearSpans {
- // inherit javadocs
- @Override
- public int start() { return matchStart; }
-
- // inherit javadocs
- @Override
- public int end() { return matchEnd; }
-
- public Spans[] getSubSpans() {
- return subSpans;
- }
-
- // TODO: Remove warning after API has been finalized
- // TODO: Would be nice to be able to lazy load payloads
- @Override
- public Collection<byte[]> getPayload() throws IOException {
- return matchPayload;
- }
-
- // TODO: Remove warning after API has been finalized
- @Override
- public boolean isPayloadAvailable() {
- return matchPayload.isEmpty() == false;
+ protected int matchDoc = -1;
+ protected int matchStart = -1;
+ protected int matchEnd = -1;
+
+ public NearSpansOrdered(SpanNearQuery query, List<Spans> subSpans) throws IOException {
+ super(query, subSpans);
+ this.atFirstInCurrentDoc = true; // -1 startPosition/endPosition also at doc -1
}
+ /** Advances the subSpans to just after an ordered match with a minimum slop
+ * that is smaller than the slop allowed by the SpanNearQuery.
+ * @return true iff there is such a match.
+ */
@Override
- public long cost() {
- long minCost = Long.MAX_VALUE;
- for (int i = 0; i < subSpans.length; i++) {
- minCost = Math.min(minCost, subSpans[i].cost());
- }
- return minCost;
- }
-
- // inherit javadocs
- @Override
- public boolean next() throws IOException {
- if (firstTime) {
- firstTime = false;
- for (int i = 0; i < subSpans.length; i++) {
- if (! subSpans[i].next()) {
- more = false;
- return false;
+ int toMatchDoc() throws IOException {
+ subSpansToFirstStartPosition();
+ while (true) {
+ if (! stretchToOrder()) {
+ if (conjunction.nextDoc() == NO_MORE_DOCS) {
+ return NO_MORE_DOCS;
+ }
+ subSpansToFirstStartPosition();
+ } else {
+ if (shrinkToAfterShortestMatch()) {
+ atFirstInCurrentDoc = true;
+ return conjunction.docID();
+ }
+ // not a match, after shortest ordered spans, not at beginning of doc.
+ if (oneExhaustedInCurrentDoc) {
+ if (conjunction.nextDoc() == NO_MORE_DOCS) {
+ return NO_MORE_DOCS;
+ }
+ subSpansToFirstStartPosition();
}
}
- more = true;
}
- if(collectPayloads) {
- matchPayload.clear();
- }
- return advanceAfterOrdered();
}
- // inherit javadocs
@Override
- public boolean skipTo(int target) throws IOException {
- if (firstTime) {
- firstTime = false;
- for (int i = 0; i < subSpans.length; i++) {
- if (! subSpans[i].skipTo(target)) {
- more = false;
- return false;
- }
- }
- more = true;
- } else if (more && (subSpans[0].doc() < target)) {
- if (subSpans[0].skipTo(target)) {
- inSameDoc = false;
- } else {
- more = false;
+ boolean twoPhaseCurrentDocMatches() throws IOException {
+ subSpansToFirstStartPosition();
+ while (true) {
+ if (! stretchToOrder()) {
return false;
}
- }
- if(collectPayloads) {
- matchPayload.clear();
- }
- return advanceAfterOrdered();
- }
-
- /** Advances the subSpans to just after an ordered match with a minimum slop
- * that is smaller than the slop allowed by the SpanNearQuery.
- * @return true iff there is such a match.
- */
- private boolean advanceAfterOrdered() throws IOException {
- while (more && (inSameDoc || toSameDoc())) {
- if (stretchToOrder() && shrinkToAfterShortestMatch()) {
+ if (shrinkToAfterShortestMatch()) {
+ atFirstInCurrentDoc = true;
return true;
}
+ // not a match, after shortest ordered spans
+ if (oneExhaustedInCurrentDoc) {
+ return false;
+ }
}
- return false; // no more matches
}
-
- /** Advance the subSpans to the same document */
- private boolean toSameDoc() throws IOException {
- sorter.sort(0, subSpansByDoc.length);
- int firstIndex = 0;
- int maxDoc = subSpansByDoc[subSpansByDoc.length - 1].doc();
- while (subSpansByDoc[firstIndex].doc() != maxDoc) {
- if (! subSpansByDoc[firstIndex].skipTo(maxDoc)) {
- more = false;
- inSameDoc = false;
- return false;
+ @Override
+ public int nextStartPosition() throws IOException {
+ if (atFirstInCurrentDoc) {
+ atFirstInCurrentDoc = false;
+ return matchStart;
+ }
+ while (true) {
+ if (oneExhaustedInCurrentDoc) {
+ matchStart = NO_MORE_POSITIONS;
+ matchEnd = NO_MORE_POSITIONS;
+ return NO_MORE_POSITIONS;
}
- maxDoc = subSpansByDoc[firstIndex].doc();
- if (++firstIndex == subSpansByDoc.length) {
- firstIndex = 0;
+ if (! stretchToOrder()) {
+ matchStart = NO_MORE_POSITIONS;
+ matchEnd = NO_MORE_POSITIONS;
+ return NO_MORE_POSITIONS;
}
+ if (shrinkToAfterShortestMatch()) { // may also leave oneExhaustedInCurrentDoc
+ return matchStart;
+ }
+ // after shortest ordered spans, or oneExhaustedInCurrentDoc
}
- for (int i = 0; i < subSpansByDoc.length; i++) {
- assert (subSpansByDoc[i].doc() == maxDoc)
- : " NearSpansOrdered.toSameDoc() spans " + subSpansByDoc[0]
- + "\n at doc " + subSpansByDoc[i].doc()
- + ", but should be at " + maxDoc;
- }
- inSameDoc = true;
- return true;
- }
-
- /** Check whether two Spans in the same document are ordered and not overlapping.
- * @return false iff spans2's start position is smaller than spans1's end position
- */
- static final boolean docSpansOrderedNonOverlap(Spans spans1, Spans spans2) {
- assert spans1.doc() == spans2.doc() : "doc1 " + spans1.doc() + " != doc2 " + spans2.doc();
- assert spans1.start() < spans1.end();
- assert spans2.start() < spans2.end();
- return spans1.end() <= spans2.start();
}
- /** Like {@link #docSpansOrderedNonOverlap(Spans,Spans)}, but use the spans
- * starts and ends as parameters.
- */
- private static final boolean docSpansOrderedNonOverlap(int start1, int end1, int start2, int end2) {
- assert start1 < end1;
- assert start2 < end2;
- return end1 <= start2;
+ private void subSpansToFirstStartPosition() throws IOException {
+ for (Spans spans : subSpans) {
+ assert spans.startPosition() == -1 : "spans="+spans;
+ spans.nextStartPosition();
+ assert spans.startPosition() != NO_MORE_POSITIONS;
+ }
+ oneExhaustedInCurrentDoc = false;
}
- /** Order the subSpans within the same document by advancing all later spans
- * after the previous one.
+ /** Order the subSpans within the same document by using nextStartPosition on all subSpans
+ * after the first as little as necessary.
+ * Return true when the subSpans could be ordered in this way,
+ * otherwise at least one is exhausted in the current doc.
*/
private boolean stretchToOrder() throws IOException {
- matchDoc = subSpans[0].doc();
- for (int i = 1; inSameDoc && (i < subSpans.length); i++) {
- while (! docSpansOrderedNonOverlap(subSpans[i-1], subSpans[i])) {
- if (! subSpans[i].next()) {
- inSameDoc = false;
- more = false;
- break;
- } else if (matchDoc != subSpans[i].doc()) {
- inSameDoc = false;
- break;
+ Spans prevSpans = subSpans.get(0);
+ assert prevSpans.startPosition() != NO_MORE_POSITIONS : "prevSpans no start position "+prevSpans;
+ assert prevSpans.endPosition() != NO_MORE_POSITIONS;
+ for (int i = 1; i < subSpans.size(); i++) {
+ Spans spans = subSpans.get(i);
+ assert spans.startPosition() != NO_MORE_POSITIONS;
+ assert spans.endPosition() != NO_MORE_POSITIONS;
+
+ while (prevSpans.endPosition() > spans.startPosition()) { // while overlapping spans
+ if (spans.nextStartPosition() == NO_MORE_POSITIONS) {
+ return false;
}
}
+ prevSpans = spans;
}
- return inSameDoc;
+ return true; // all subSpans ordered and non overlapping
}
/** The subSpans are ordered in the same doc, so there is a possible match.
- * Compute the slop while making the match as short as possible by advancing
- * all subSpans except the last one in reverse order.
+ * Compute the slop while making the match as short as possible by using nextStartPosition
+ * on all subSpans, except the last one, in reverse order.
*/
- private boolean shrinkToAfterShortestMatch() throws IOException {
- matchStart = subSpans[subSpans.length - 1].start();
- matchEnd = subSpans[subSpans.length - 1].end();
- Set<byte[]> possibleMatchPayloads = new HashSet<>();
- if (subSpans[subSpans.length - 1].isPayloadAvailable()) {
- possibleMatchPayloads.addAll(subSpans[subSpans.length - 1].getPayload());
- }
+ protected boolean shrinkToAfterShortestMatch() throws IOException {
+ Spans lastSubSpans = subSpans.get(subSpans.size() - 1);
+ matchStart = lastSubSpans.startPosition();
+ matchEnd = lastSubSpans.endPosition();
- Collection<byte[]> possiblePayload = null;
-
int matchSlop = 0;
int lastStart = matchStart;
int lastEnd = matchEnd;
- for (int i = subSpans.length - 2; i >= 0; i--) {
- Spans prevSpans = subSpans[i];
- if (collectPayloads && prevSpans.isPayloadAvailable()) {
- Collection<byte[]> payload = prevSpans.getPayload();
- possiblePayload = new ArrayList<>(payload.size());
- possiblePayload.addAll(payload);
- }
-
- int prevStart = prevSpans.start();
- int prevEnd = prevSpans.end();
- while (true) { // Advance prevSpans until after (lastStart, lastEnd)
- if (! prevSpans.next()) {
- inSameDoc = false;
- more = false;
- break; // Check remaining subSpans for final match.
- } else if (matchDoc != prevSpans.doc()) {
- inSameDoc = false; // The last subSpans is not advanced here.
- break; // Check remaining subSpans for last match in this document.
- } else {
- int ppStart = prevSpans.start();
- int ppEnd = prevSpans.end(); // Cannot avoid invoking .end()
- if (! docSpansOrderedNonOverlap(ppStart, ppEnd, lastStart, lastEnd)) {
- break; // Check remaining subSpans.
- } else { // prevSpans still before (lastStart, lastEnd)
- prevStart = ppStart;
- prevEnd = ppEnd;
- if (collectPayloads && prevSpans.isPayloadAvailable()) {
- Collection<byte[]> payload = prevSpans.getPayload();
- possiblePayload = new ArrayList<>(payload.size());
- possiblePayload.addAll(payload);
- }
- }
+ for (int i = subSpans.size() - 2; i >= 0; i--) {
+ Spans prevSpans = subSpans.get(i);
+
+ int prevStart = prevSpans.startPosition();
+ int prevEnd = prevSpans.endPosition();
+ while (true) { // prevSpans nextStartPosition until after (lastStart, lastEnd)
+ if (prevSpans.nextStartPosition() == NO_MORE_POSITIONS) {
+ oneExhaustedInCurrentDoc = true;
+ break; // Check remaining subSpans for match.
+ }
+ int ppStart = prevSpans.startPosition();
+ int ppEnd = prevSpans.endPosition();
+ if (ppEnd > lastStart) { // if overlapping spans
+ break; // Check remaining subSpans.
}
+ // prevSpans still before (lastStart, lastEnd)
+ prevStart = ppStart;
+ prevEnd = ppEnd;
}
- if (collectPayloads && possiblePayload != null) {
- possibleMatchPayloads.addAll(possiblePayload);
- }
-
assert prevStart <= matchStart;
if (matchStart > prevEnd) { // Only non overlapping spans add to slop.
matchSlop += (matchStart - prevEnd);
}
/* Do not break on (matchSlop > allowedSlop) here to make sure
- * that subSpans[0] is advanced after the match, if any.
+ * that on return the first subSpans has nextStartPosition called.
*/
matchStart = prevStart;
lastStart = prevStart;
lastEnd = prevEnd;
}
-
+
boolean match = matchSlop <= allowedSlop;
-
- if(collectPayloads && match && possibleMatchPayloads.size() > 0) {
- matchPayload.addAll(possibleMatchPayloads);
- }
return match; // ordered and allowed slop
}
@Override
+ public int startPosition() {
+ return atFirstInCurrentDoc ? -1 : matchStart;
+ }
+
+ @Override
+ public int endPosition() {
+ return atFirstInCurrentDoc ? -1 : matchEnd;
+ }
+
+ /** Throws an UnsupportedOperationException */
+ @Override
+ public Collection<byte[]> getPayload() throws IOException {
+ throw new UnsupportedOperationException("Use NearSpansPayloadOrdered instead");
+ }
+
+ /** Throws an UnsupportedOperationException */
+ @Override
+ public boolean isPayloadAvailable() {
+ throw new UnsupportedOperationException("Use NearSpansPayloadOrdered instead");
+ }
+
+ @Override
public String toString() {
- return getClass().getName() + "("+query.toString()+")@"+
- (firstTime?"START":(more?(doc()+":"+start()+"-"+end()):"END"));
+ return "NearSpansOrdered("+query.toString()+")@"+docID()+": "+startPosition()+" - "+endPosition();
}
}
Added: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java?rev=1670272&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java (added)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java Tue Mar 31 08:27:45 2015
@@ -0,0 +1,146 @@
+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 java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Collection;
+import java.util.Set;
+
+/** A {@link NearSpansOrdered} that allows collecting payloads.
+ * Expert:
+ * Only public for subclassing. Most implementations should not need this class
+ */
+public class NearSpansPayloadOrdered extends NearSpansOrdered {
+
+ private List<byte[]> matchPayload;
+ private Set<byte[]> possibleMatchPayloads;
+
+ public NearSpansPayloadOrdered(SpanNearQuery query, List<Spans> subSpans)
+ throws IOException {
+ super(query, subSpans);
+ this.matchPayload = new LinkedList<>();
+ this.possibleMatchPayloads = new HashSet<>();
+ }
+
+ /** The subSpans are ordered in the same doc, so there is a possible match.
+ * Compute the slop while making the match as short as possible by using nextStartPosition
+ * on all subSpans, except the last one, in reverse order.
+ * Also collect the payloads.
+ */
+ protected boolean shrinkToAfterShortestMatch() throws IOException {
+ Spans lastSubSpans = subSpans.get(subSpans.size() - 1);
+ matchStart = lastSubSpans.startPosition();
+ matchEnd = lastSubSpans.endPosition();
+
+ matchPayload.clear();
+ possibleMatchPayloads.clear();
+
+ if (lastSubSpans.isPayloadAvailable()) {
+ possibleMatchPayloads.addAll(lastSubSpans.getPayload());
+ }
+
+ Collection<byte[]> possiblePayload = null;
+
+ int matchSlop = 0;
+ int lastStart = matchStart;
+ int lastEnd = matchEnd;
+ for (int i = subSpans.size() - 2; i >= 0; i--) {
+ Spans prevSpans = subSpans.get(i);
+
+ if (prevSpans.isPayloadAvailable()) {
+ Collection<byte[]> payload = prevSpans.getPayload();
+ possiblePayload = new ArrayList<>(payload.size());
+ possiblePayload.addAll(payload);
+ }
+
+ int prevStart = prevSpans.startPosition();
+ int prevEnd = prevSpans.endPosition();
+ while (true) { // prevSpans nextStartPosition until after (lastStart, lastEnd)
+ if (prevSpans.nextStartPosition() == NO_MORE_POSITIONS) {
+ oneExhaustedInCurrentDoc = true;
+ break; // Check remaining subSpans for match.
+ }
+ int ppStart = prevSpans.startPosition();
+ int ppEnd = prevSpans.endPosition();
+ if (ppEnd > lastStart) { // if overlapping spans
+ break; // Check remaining subSpans.
+ }
+ // prevSpans still before (lastStart, lastEnd)
+ prevStart = ppStart;
+ prevEnd = ppEnd;
+ if (prevSpans.isPayloadAvailable()) {
+ Collection<byte[]> payload = prevSpans.getPayload();
+ if (possiblePayload == null) {
+ possiblePayload = new ArrayList<>(payload.size());
+ } else {
+ possiblePayload.clear();
+ }
+ possiblePayload.addAll(payload);
+ }
+ }
+
+ if (possiblePayload != null) {
+ possibleMatchPayloads.addAll(possiblePayload);
+ }
+
+ assert prevStart <= matchStart;
+ if (matchStart > prevEnd) { // Only non overlapping spans add to slop.
+ matchSlop += (matchStart - prevEnd);
+ }
+
+ /* Do not break on (matchSlop > allowedSlop) here to make sure
+ * that on return the first subSpans has nextStartPosition called.
+ */
+ matchStart = prevStart;
+ lastStart = prevStart;
+ lastEnd = prevEnd;
+ }
+
+ boolean match = matchSlop <= allowedSlop;
+
+ if (match && possibleMatchPayloads.size() > 0) {
+ matchPayload.addAll(possibleMatchPayloads);
+ }
+
+ return match; // ordered and allowed slop
+ }
+
+ // TODO: Remove warning after API has been finalized
+ // TODO: Would be nice to be able to lazy load payloads
+ /** Return payloads when available. */
+ @Override
+ public Collection<byte[]> getPayload() throws IOException {
+ return matchPayload;
+ }
+
+ /** Indicates whether payloads are available */
+ @Override
+ public boolean isPayloadAvailable() {
+ return ! matchPayload.isEmpty();
+ }
+
+ @Override
+ public String toString() {
+ return "NearSpansPayloadOrdered("+query.toString()+")@"+docID()+": "+startPosition()+" - "+endPosition();
+ }
+}
+
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java Tue Mar 31 08:27:45 2015
@@ -17,253 +17,225 @@ package org.apache.lucene.search.spans;
* limitations under the License.
*/
-import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.Term;
-import org.apache.lucene.index.TermContext;
-import org.apache.lucene.util.Bits;
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.Map;
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;
+public class NearSpansUnordered extends NearSpans {
- private List<SpansCell> ordered = new ArrayList<>(); // spans in query order
- private Spans[] subSpans;
- private int slop; // from query
+ private List<SpansCell> subSpanCells; // in query order
- private SpansCell first; // linked list of spans
- private SpansCell last; // sorted by doc only
+ private SpanPositionQueue spanPositionQueue;
- private int totalLength; // sum of current lengths
+ public NearSpansUnordered(SpanNearQuery query, List<Spans> subSpans)
+ throws IOException {
+ super(query, subSpans);
- private CellQueue queue; // sorted queue of spans
- private SpansCell max; // max element in queue
+ this.subSpanCells = new ArrayList<>(subSpans.size());
+ for (Spans subSpan : subSpans) { // sub spans in query order
+ this.subSpanCells.add(new SpansCell(subSpan));
+ }
+ spanPositionQueue = new SpanPositionQueue(subSpans.size());
+ singleCellToPositionQueue(); // -1 startPosition/endPosition also at doc -1
+ }
- private boolean more = true; // true iff not done
- private boolean firstTime = true; // true before first next()
+ private void singleCellToPositionQueue() {
+ maxEndPositionCell = subSpanCells.get(0);
+ assert maxEndPositionCell.docID() == -1;
+ assert maxEndPositionCell.startPosition() == -1;
+ spanPositionQueue.add(maxEndPositionCell);
+ }
- private class CellQueue extends PriorityQueue<SpansCell> {
- public CellQueue(int size) {
- super(size);
- }
-
- @Override
- protected final boolean lessThan(SpansCell spans1, SpansCell spans2) {
- if (spans1.doc() == spans2.doc()) {
- return docSpansOrdered(spans1, spans2);
- } else {
- return spans1.doc() < spans2.doc();
- }
+ private void subSpanCellsToPositionQueue() throws IOException { // used when all subSpanCells arrived at the same doc.
+ spanPositionQueue.clear();
+ for (SpansCell cell : subSpanCells) {
+ assert cell.startPosition() == -1;
+ cell.nextStartPosition();
+ assert cell.startPosition() != NO_MORE_POSITIONS;
+ spanPositionQueue.add(cell);
}
}
+ /** SpansCell wraps a sub Spans to maintain totalSpanLength and maxEndPositionCell */
+ private int totalSpanLength;
+ private SpansCell maxEndPositionCell;
- /** 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;
+ private class SpansCell extends FilterSpans {
+ private int spanLength = -1;
- public SpansCell(Spans spans, int index) {
- this.spans = spans;
- this.index = index;
+ public SpansCell(Spans spans) {
+ super(spans);
}
@Override
- public boolean next() throws IOException {
- return adjust(spans.next());
+ public int nextStartPosition() throws IOException {
+ int res = in.nextStartPosition();
+ if (res != NO_MORE_POSITIONS) {
+ adjustLength();
+ }
+ adjustMax(); // also after last end position in current doc.
+ return res;
}
- @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;
- }
+ private void adjustLength() {
+ if (spanLength != -1) {
+ totalSpanLength -= spanLength; // subtract old, possibly from a previous doc
}
- more = condition;
- return condition;
+ assert in.startPosition() != NO_MORE_POSITIONS;
+ spanLength = endPosition() - startPosition();
+ assert spanLength >= 0;
+ totalSpanLength += spanLength; // add new
}
- @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<>(spans.getPayload());
+ private void adjustMax() {
+ assert docID() == maxEndPositionCell.docID();
+ if (endPosition() > maxEndPositionCell.endPosition()) {
+ maxEndPositionCell = this;
+ }
}
- // TODO: Remove warning after API has been finalized
@Override
- public boolean isPayloadAvailable() throws IOException {
- return spans.isPayloadAvailable();
+ public String toString() {
+ return "NearSpansUnordered.SpansCell(" + in.toString() + ")";
}
+ }
- @Override
- public long cost() {
- return spans.cost();
+
+ private static class SpanPositionQueue extends PriorityQueue<SpansCell> {
+ public SpanPositionQueue(int size) {
+ super(size);
}
@Override
- public String toString() { return spans.toString() + "#" + index; }
+ protected final boolean lessThan(SpansCell spans1, SpansCell spans2) {
+ return positionsOrdered(spans1, spans2);
+ }
}
+ /** Check whether two Spans in the same document are ordered with possible overlap.
+ * @return true iff spans1 starts before spans2
+ * or the spans start at the same position,
+ * and spans1 ends before spans2.
+ */
+ static final boolean positionsOrdered(Spans spans1, Spans spans2) {
+ assert spans1.docID() == spans2.docID() : "doc1 " + spans1.docID() + " != doc2 " + spans2.docID();
+ int start1 = spans1.startPosition();
+ int start2 = spans2.startPosition();
+ return (start1 == start2) ? (spans1.endPosition() < spans2.endPosition()) : (start1 < start2);
+ }
- public NearSpansUnordered(SpanNearQuery query, LeafReaderContext context, Bits acceptDocs, Map<Term,TermContext> termContexts)
- 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(context, acceptDocs, termContexts), i);
- ordered.add(cell);
- subSpans[i] = cell.spans;
- }
+ private SpansCell minPositionCell() {
+ return spanPositionQueue.top();
}
- public Spans[] getSubSpans() {
- return subSpans;
+
+ private boolean atMatch() {
+ assert minPositionCell().docID() == maxEndPositionCell.docID();
+ return (maxEndPositionCell.endPosition() - minPositionCell().startPosition() - totalSpanLength) <= allowedSlop;
}
+
@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;
+ int toMatchDoc() throws IOException {
+ // at doc with all subSpans
+ subSpanCellsToPositionQueue();
+ while (true) {
+ if (atMatch()) {
+ atFirstInCurrentDoc = true;
+ oneExhaustedInCurrentDoc = false;
+ return conjunction.docID();
+ }
+ assert minPositionCell().startPosition() != NO_MORE_POSITIONS;
+ if (minPositionCell().nextStartPosition() != NO_MORE_POSITIONS) {
+ spanPositionQueue.updateTop();
+ }
+ else { // exhausted a subSpan in current doc
+ if (conjunction.nextDoc() == NO_MORE_DOCS) {
+ return NO_MORE_DOCS;
+ }
+ // at doc with all subSpans
+ subSpanCellsToPositionQueue();
}
}
+ }
- 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;
- }
-
+ @Override
+ boolean twoPhaseCurrentDocMatches() throws IOException {
+ // at doc with all subSpans
+ subSpanCellsToPositionQueue();
+ while (true) {
if (atMatch()) {
+ atFirstInCurrentDoc = true;
+ oneExhaustedInCurrentDoc = false;
return true;
}
-
- more = min().next();
- if (more) {
- queue.updateTop(); // maintain queue
+ assert minPositionCell().startPosition() != NO_MORE_POSITIONS;
+ if (minPositionCell().nextStartPosition() != NO_MORE_POSITIONS) {
+ spanPositionQueue.updateTop();
+ }
+ else { // exhausted a subSpan in current doc
+ return false;
}
}
- 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;
- }
+ public int nextStartPosition() throws IOException {
+ if (atFirstInCurrentDoc) {
+ atFirstInCurrentDoc = false;
+ return minPositionCell().startPosition();
+ }
+ while (minPositionCell().startPosition() == -1) { // initially at current doc
+ minPositionCell().nextStartPosition();
+ spanPositionQueue.updateTop();
+ }
+ assert minPositionCell().startPosition() != NO_MORE_POSITIONS;
+ while (true) {
+ if (minPositionCell().nextStartPosition() == NO_MORE_POSITIONS) {
+ oneExhaustedInCurrentDoc = true;
+ return NO_MORE_POSITIONS;
+ }
+ spanPositionQueue.updateTop();
+ if (atMatch()) {
+ return minPositionCell().startPosition();
}
}
- return more && (atMatch() || next());
}
- /** Check whether two Spans in the same document are ordered with possible overlap.
- * @return true iff spans1 starts before spans2
- * or the spans start at the same position,
- * and spans1 ends before spans2.
- */
- static final boolean docSpansOrdered(Spans spans1, Spans spans2) {
- assert spans1.doc() == spans2.doc() : "doc1 " + spans1.doc() + " != doc2 " + spans2.doc();
- int start1 = spans1.start();
- int start2 = spans2.start();
- return (start1 == start2) ? (spans1.end() < spans2.end()) : (start1 < start2);
+ @Override
+ public int startPosition() {
+ assert minPositionCell() != null;
+ return atFirstInCurrentDoc ? -1
+ : oneExhaustedInCurrentDoc ? NO_MORE_POSITIONS
+ : minPositionCell().startPosition();
}
- 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(); }
+ public int endPosition() {
+ return atFirstInCurrentDoc ? -1
+ : oneExhaustedInCurrentDoc ? NO_MORE_POSITIONS
+ : maxEndPositionCell.endPosition();
+ }
+
- // TODO: Remove warning after API has been finalized
/**
- * WARNING: The List is not necessarily in order of the the positions
+ * WARNING: The List is not necessarily in order of the positions.
* @return Collection of <code>byte[]</code> payloads
* @throws IOException if there is a low-level I/O error
*/
@Override
public Collection<byte[]> getPayload() throws IOException {
Set<byte[]> matchPayload = new HashSet<>();
- for (SpansCell cell = first; cell != null; cell = cell.next) {
+ for (SpansCell cell : subSpanCells) {
if (cell.isPayloadAvailable()) {
matchPayload.addAll(cell.getPayload());
}
@@ -271,78 +243,23 @@ public class NearSpansUnordered extends
return matchPayload;
}
- // TODO: Remove warning after API has been finalized
@Override
public boolean isPayloadAvailable() throws IOException {
- SpansCell pointer = min();
- while (pointer != null) {
- if (pointer.isPayloadAvailable()) {
+ for (SpansCell cell : subSpanCells) {
+ if (cell.isPayloadAvailable()) {
return true;
}
- pointer = pointer.next;
}
-
return false;
}
-
- @Override
- public long cost() {
- long minCost = Long.MAX_VALUE;
- for (int i = 0; i < subSpans.length; i++) {
- minCost = Math.min(minCost, subSpans[i].cost());
- }
- return minCost;
- }
@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
- }
+ if (minPositionCell() != null) {
+ return getClass().getName() + "("+query.toString()+")@"+
+ (docID()+":"+startPosition()+"-"+endPosition());
+ } else {
+ return getClass().getName() + "("+query.toString()+")@ ?START?";
}
}
-
- private void addToList(SpansCell cell) {
- 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() {
- 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);
- }
}
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanFirstQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanFirstQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanFirstQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanFirstQuery.java Tue Mar 31 08:27:45 2015
@@ -21,9 +21,9 @@ import org.apache.lucene.util.ToStringUt
import java.io.IOException;
-/**
+/**
* Matches spans near the beginning of a field.
- * <p>
+ * <p>
* This class is a simple extension of {@link SpanPositionRangeQuery} in that it assumes the
* start to be zero and only checks the end boundary.
*/
@@ -37,10 +37,10 @@ public class SpanFirstQuery extends Span
@Override
protected AcceptStatus acceptPosition(Spans spans) throws IOException {
- assert spans.start() != spans.end() : "start equals end: " + spans.start();
- if (spans.start() >= end)
- return AcceptStatus.NO_AND_ADVANCE;
- else if (spans.end() <= end)
+ assert spans.startPosition() != spans.endPosition() : "start equals end: " + spans.startPosition();
+ if (spans.startPosition() >= end)
+ return AcceptStatus.NO_MORE_IN_CURRENT_DOC;
+ else if (spans.endPosition() <= end)
return AcceptStatus.YES;
else
return AcceptStatus.NO;
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearPayloadCheckQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearPayloadCheckQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearPayloadCheckQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearPayloadCheckQuery.java Tue Mar 31 08:27:45 2015
@@ -105,7 +105,7 @@ public class SpanNearPayloadCheckQuery e
@Override
public int hashCode() {
- int h = match.hashCode();
+ int h = match.hashCode() ^ getClass().hashCode();
h ^= (h << 8) | (h >>> 25); // reversible
//TODO: is this right?
h ^= payloadToMatch.hashCode();
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java Tue Mar 31 08:27:45 2015
@@ -37,7 +37,8 @@ import org.apache.lucene.util.ToStringUt
/** Matches spans which are near one another. One can specify <i>slop</i>, the
* maximum number of intervening unmatched positions, as well as whether
- * matches are required to be in-order. */
+ * matches are required to be in-order.
+ */
public class SpanNearQuery extends SpanQuery implements Cloneable {
protected List<SpanQuery> clauses;
protected int slop;
@@ -53,22 +54,19 @@ public class SpanNearQuery extends SpanQ
* must be in the same order as in <code>clauses</code> and must be non-overlapping.
* <br>When <code>inOrder</code> is false, the spans from each clause
* need not be ordered and may overlap.
- * @param clauses the clauses to find near each other
+ * @param clauses the clauses to find near each other, in the same field, at least 2.
* @param slop The slop value
* @param inOrder true if order is important
*/
public SpanNearQuery(SpanQuery[] clauses, int slop, boolean inOrder) {
- this(clauses, slop, inOrder, true);
+ this(clauses, slop, inOrder, true);
}
-
- public SpanNearQuery(SpanQuery[] clauses, int slop, boolean inOrder, boolean collectPayloads) {
- // copy clauses array into an ArrayList
- this.clauses = new ArrayList<>(clauses.length);
- for (int i = 0; i < clauses.length; i++) {
- SpanQuery clause = clauses[i];
- if (field == null) { // check field
- field = clause.getField();
+ public SpanNearQuery(SpanQuery[] clausesIn, int slop, boolean inOrder, boolean collectPayloads) {
+ this.clauses = new ArrayList<>(clausesIn.length);
+ for (SpanQuery clause : clausesIn) {
+ if (this.field == null) { // check field
+ this.field = clause.getField();
} else if (clause.getField() != null && !clause.getField().equals(field)) {
throw new IllegalArgumentException("Clauses must have same field.");
}
@@ -92,14 +90,13 @@ public class SpanNearQuery extends SpanQ
@Override
public String getField() { return field; }
-
+
@Override
public void extractTerms(Set<Term> terms) {
for (final SpanQuery clause : clauses) {
clause.extractTerms(terms);
}
- }
-
+ }
@Override
public String toString(String field) {
@@ -124,15 +121,21 @@ public class SpanNearQuery extends SpanQ
@Override
public Spans getSpans(final LeafReaderContext context, Bits acceptDocs, Map<Term,TermContext> termContexts) throws IOException {
- if (clauses.size() == 0) // optimize 0-clause case
- return new SpanOrQuery(getClauses()).getSpans(context, acceptDocs, termContexts);
-
- if (clauses.size() == 1) // optimize 1-clause case
- return clauses.get(0).getSpans(context, acceptDocs, termContexts);
+ ArrayList<Spans> subSpans = new ArrayList<>(clauses.size());
- return inOrder
- ? (Spans) new NearSpansOrdered(this, context, acceptDocs, termContexts, collectPayloads)
- : (Spans) new NearSpansUnordered(this, context, acceptDocs, termContexts);
+ for (SpanQuery seq : clauses) {
+ Spans subSpan = seq.getSpans(context, acceptDocs, termContexts);
+ if (subSpan != null) {
+ subSpans.add(subSpan);
+ } else {
+ return null; // all required
+ }
+ }
+
+ // all NearSpans require at least two subSpans
+ return (! inOrder) ? new NearSpansUnordered(this, subSpans)
+ : collectPayloads ? new NearSpansPayloadOrdered(this, subSpans)
+ : new NearSpansOrdered(this, subSpans);
}
@Override
@@ -148,12 +151,12 @@ public class SpanNearQuery extends SpanQ
}
}
if (clone != null) {
- return clone; // some clauses rewrote
+ return clone; // some clauses rewrote
} else {
- return this; // no clauses rewrote
+ return this; // no clauses rewrote
}
}
-
+
@Override
public SpanNearQuery clone() {
int sz = clauses.size();
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNotQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNotQuery.java?rev=1670272&r1=1670271&r2=1670272&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNotQuery.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/search/spans/SpanNotQuery.java Tue Mar 31 08:27:45 2015
@@ -30,9 +30,11 @@ import java.util.ArrayList;
import java.util.Collection;
import java.util.Map;
import java.util.Set;
+import java.util.Objects;
-/** Removes matches which overlap with another SpanQuery or
- * within a x tokens before or y tokens after another SpanQuery. */
+/** Removes matches which overlap with another SpanQuery or which are
+ * within x tokens before or y tokens after another SpanQuery.
+ */
public class SpanNotQuery extends SpanQuery implements Cloneable {
private SpanQuery include;
private SpanQuery exclude;
@@ -45,20 +47,20 @@ public class SpanNotQuery extends SpanQu
this(include, exclude, 0, 0);
}
-
+
/** Construct a SpanNotQuery matching spans from <code>include</code> which
- * have no overlap with spans from <code>exclude</code> within
+ * have no overlap with spans from <code>exclude</code> within
* <code>dist</code> tokens of <code>include</code>. */
public SpanNotQuery(SpanQuery include, SpanQuery exclude, int dist) {
this(include, exclude, dist, dist);
}
-
+
/** Construct a SpanNotQuery matching spans from <code>include</code> which
- * have no overlap with spans from <code>exclude</code> within
+ * have no overlap with spans from <code>exclude</code> within
* <code>pre</code> tokens before or <code>post</code> tokens of <code>include</code>. */
public SpanNotQuery(SpanQuery include, SpanQuery exclude, int pre, int post) {
- this.include = include;
- this.exclude = exclude;
+ this.include = Objects.requireNonNull(include);
+ this.exclude = Objects.requireNonNull(exclude);
this.pre = (pre >=0) ? pre : 0;
this.post = (post >= 0) ? post : 0;
@@ -96,81 +98,153 @@ public class SpanNotQuery extends SpanQu
@Override
public SpanNotQuery clone() {
- SpanNotQuery spanNotQuery = new SpanNotQuery((SpanQuery)include.clone(),
- (SpanQuery) exclude.clone(), pre, post);
+ SpanNotQuery spanNotQuery = new SpanNotQuery((SpanQuery) include.clone(),
+ (SpanQuery) exclude.clone(), pre, post);
spanNotQuery.setBoost(getBoost());
- return spanNotQuery;
+ return spanNotQuery;
}
@Override
public Spans getSpans(final LeafReaderContext context, final Bits acceptDocs, final Map<Term,TermContext> termContexts) throws IOException {
- return new Spans() {
- private Spans includeSpans = include.getSpans(context, acceptDocs, termContexts);
- private boolean moreInclude = true;
+ Spans includeSpans = include.getSpans(context, acceptDocs, termContexts);
+ if (includeSpans == null) {
+ return null;
+ }
- private Spans excludeSpans = exclude.getSpans(context, acceptDocs, termContexts);
- private boolean moreExclude = excludeSpans.next();
+ Spans excludeSpans = exclude.getSpans(context, acceptDocs, termContexts);
+ if (excludeSpans == null) {
+ return includeSpans;
+ }
- @Override
- public boolean next() throws IOException {
- if (moreInclude) // move to next include
- moreInclude = includeSpans.next();
-
- while (moreInclude && moreExclude) {
-
- if (includeSpans.doc() > excludeSpans.doc()) // skip exclude
- moreExclude = excludeSpans.skipTo(includeSpans.doc());
-
- while (moreExclude // while exclude is before
- && includeSpans.doc() == excludeSpans.doc()
- && excludeSpans.end() <= includeSpans.start() - pre) {
- moreExclude = excludeSpans.next(); // increment exclude
- }
+ return new Spans() {
+ private boolean moreInclude = true;
+ private int includeStart = -1;
+ private int includeEnd = -1;
+ private boolean atFirstInCurrentDoc = false;
+
+ private boolean moreExclude = excludeSpans.nextDoc() != NO_MORE_DOCS;
+ private int excludeStart = moreExclude ? excludeSpans.nextStartPosition() : NO_MORE_POSITIONS;
- if (!moreExclude // if no intersection
- || includeSpans.doc() != excludeSpans.doc()
- || includeSpans.end()+post <= excludeSpans.start())
- break; // we found a match
- moreInclude = includeSpans.next(); // intersected: keep scanning
+ @Override
+ public int nextDoc() throws IOException {
+ if (moreInclude) {
+ moreInclude = includeSpans.nextDoc() != NO_MORE_DOCS;
+ if (moreInclude) {
+ atFirstInCurrentDoc = true;
+ includeStart = includeSpans.nextStartPosition();
+ assert includeStart != NO_MORE_POSITIONS;
}
- return moreInclude;
}
+ toNextIncluded();
+ int res = moreInclude ? includeSpans.docID() : NO_MORE_DOCS;
+ return res;
+ }
- @Override
- public boolean skipTo(int target) throws IOException {
- if (moreInclude) // skip include
- moreInclude = includeSpans.skipTo(target);
+ private void toNextIncluded() throws IOException {
+ while (moreInclude && moreExclude) {
+ if (includeSpans.docID() > excludeSpans.docID()) {
+ moreExclude = excludeSpans.advance(includeSpans.docID()) != NO_MORE_DOCS;
+ if (moreExclude) {
+ excludeStart = -1; // only use exclude positions at same doc
+ }
+ }
+ if (excludeForwardInCurrentDocAndAtMatch()) {
+ break; // at match.
+ }
- if (!moreInclude)
- return false;
+ // else intersected: keep scanning, to next doc if needed
+ includeStart = includeSpans.nextStartPosition();
+ if (includeStart == NO_MORE_POSITIONS) {
+ moreInclude = includeSpans.nextDoc() != NO_MORE_DOCS;
+ if (moreInclude) {
+ atFirstInCurrentDoc = true;
+ includeStart = includeSpans.nextStartPosition();
+ assert includeStart != NO_MORE_POSITIONS;
+ }
+ }
+ }
+ }
- if (moreExclude // skip exclude
- && includeSpans.doc() > excludeSpans.doc())
- moreExclude = excludeSpans.skipTo(includeSpans.doc());
+ private boolean excludeForwardInCurrentDocAndAtMatch() throws IOException {
+ assert moreInclude;
+ assert includeStart != NO_MORE_POSITIONS;
+ if (! moreExclude) {
+ return true;
+ }
+ if (includeSpans.docID() != excludeSpans.docID()) {
+ return true;
+ }
+ // at same doc
+ if (excludeStart == -1) { // init exclude start position if needed
+ excludeStart = excludeSpans.nextStartPosition();
+ assert excludeStart != NO_MORE_POSITIONS;
+ }
+ while (excludeSpans.endPosition() <= includeStart - pre) {
+ // exclude end position is before a possible exclusion
+ excludeStart = excludeSpans.nextStartPosition();
+ if (excludeStart == NO_MORE_POSITIONS) {
+ return true; // no more exclude at current doc.
+ }
+ }
+ // exclude end position far enough in current doc, check start position:
+ boolean res = includeSpans.endPosition() + post <= excludeStart;
+ return res;
+ }
- while (moreExclude // while exclude is before
- && includeSpans.doc() == excludeSpans.doc()
- && excludeSpans.end() <= includeSpans.start()-pre) {
- moreExclude = excludeSpans.next(); // increment exclude
+ @Override
+ public int advance(int target) throws IOException {
+ if (moreInclude) {
+ assert target > includeSpans.docID() : "target="+target+", includeSpans.docID()="+includeSpans.docID();
+ moreInclude = includeSpans.advance(target) != NO_MORE_DOCS;
+ if (moreInclude) {
+ atFirstInCurrentDoc = true;
+ includeStart = includeSpans.nextStartPosition();
+ assert includeStart != NO_MORE_POSITIONS;
}
+ }
+ toNextIncluded();
+ int res = moreInclude ? includeSpans.docID() : NO_MORE_DOCS;
+ return res;
+ }
- if (!moreExclude // if no intersection
- || includeSpans.doc() != excludeSpans.doc()
- || includeSpans.end()+post <= excludeSpans.start())
- return true; // we found a match
+ @Override
+ public int docID() {
+ int res = includeSpans.docID();
+ return res;
+ }
+
+ @Override
+ public int nextStartPosition() throws IOException {
+ assert moreInclude;
- return next(); // scan to next match
+ if (atFirstInCurrentDoc) {
+ atFirstInCurrentDoc = false;
+ assert includeStart != NO_MORE_POSITIONS;
+ return includeStart;
}
- @Override
- public int doc() { return includeSpans.doc(); }
- @Override
- public int start() { return includeSpans.start(); }
- @Override
- public int end() { return includeSpans.end(); }
+ includeStart = includeSpans.nextStartPosition();
+ while ((includeStart != NO_MORE_POSITIONS)
+ && (! excludeForwardInCurrentDocAndAtMatch()))
+ {
+ includeStart = includeSpans.nextStartPosition();
+ }
+
+ return includeStart;
+ }
+
+ @Override
+ public int startPosition() {
+ assert includeStart == includeSpans.startPosition();
+ return atFirstInCurrentDoc ? -1 : includeStart;
+ }
+
+ @Override
+ public int endPosition() {
+ return atFirstInCurrentDoc ? -1 : includeSpans.endPosition();
+ }
- // TODO: Remove warning after API has been finalized
@Override
public Collection<byte[]> getPayload() throws IOException {
ArrayList<byte[]> result = null;
@@ -180,7 +254,6 @@ public class SpanNotQuery extends SpanQu
return result;
}
- // TODO: Remove warning after API has been finalized
@Override
public boolean isPayloadAvailable() throws IOException {
return includeSpans.isPayloadAvailable();
@@ -193,10 +266,9 @@ public class SpanNotQuery extends SpanQu
@Override
public String toString() {
- return "spans(" + SpanNotQuery.this.toString() + ")";
- }
-
- };
+ return "spans(" + SpanNotQuery.this.toString() + ")";
+ }
+ };
}
@Override
@@ -230,7 +302,7 @@ public class SpanNotQuery extends SpanQu
SpanNotQuery other = (SpanNotQuery)o;
return this.include.equals(other.include)
&& this.exclude.equals(other.exclude)
- && this.pre == other.pre
+ && this.pre == other.pre
&& this.post == other.post;
}