Update UnorderedDistanceSpans as an abstract class
Add UnorderedElementDistanceSpans and UnorderedTokenDistanceSpans
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/ElementDistanceSpan.java b/src/main/java/de/ids_mannheim/korap/query/spans/ElementDistanceSpan.java
index c097819..f79df35 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/ElementDistanceSpan.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/ElementDistanceSpan.java
@@ -23,10 +23,11 @@
* @author margaretha
* */
public class ElementDistanceSpan extends DistanceSpan {
-
- private boolean hasMoreElements;
+
private Spans elements;
- private int elementPosition, secondSpanPostion;
+ private boolean hasMoreElements;
+ private int elementPosition;
+ private int secondSpanPostion;
public ElementDistanceSpan(SpanDistanceQuery query,
AtomicReaderContext context, Bits acceptDocs,
@@ -70,7 +71,7 @@
}
else {
candidateList.clear();
- if (hasMoreFirstSpans && findSameDoc()){
+ if (hasMoreFirstSpans && findSameDoc(firstSpans, secondSpans, elements)){
candidateListDocNum = firstSpans.doc();
elementPosition=0;
candidateListIndex = -1;
@@ -95,18 +96,8 @@
}
}
- @Override
- protected boolean isSecondSpanValid() throws IOException{
- if (advanceElementTo(secondSpans)){
- secondSpanPostion = elementPosition;
- filterCandidateList(secondSpanPostion);
- return true;
- }
- // second span is not in an element
- return false;
- }
- /** Advance elements until encountering a span.
+ /** Advance elements until encountering a span within the given document.
* @return true iff an element containing the span, is found.
*/
private boolean advanceElementTo(Spans span) throws IOException{
@@ -125,10 +116,12 @@
return false;
}
+
/** Reduce the number of candidates by removing all candidates that are
- * not within a max distance from the given element position.
+ * not within the max distance from the given element position.
* */
private void filterCandidateList(int position){
+
Iterator<CandidateSpan> i = candidateList.iterator();
CandidateSpan cs;
while(i.hasNext()){
@@ -138,26 +131,19 @@
break;
}
i.remove();
- }
-
- //System.out.println("pos "+position+" " +candidateList.size());
- }
-
- /** Find the same doc shared by element, firstspan and secondspan.
- * @return true iff such a doc is found.
- * */
- private boolean findSameDoc() throws IOException{
-
- while (hasMoreSpans) {
- if (ensureSameDoc(firstSpans, secondSpans) &&
- elements.doc() == firstSpans.doc()){
- return true;
- }
- if (!ensureSameDoc(elements,secondSpans)){
- return false;
- };
}
- return false;
+ //System.out.println("pos "+position+" " +candidateList.size());
+ }
+
+ @Override
+ protected boolean isSecondSpanValid() throws IOException{
+ if (advanceElementTo(secondSpans)){
+ secondSpanPostion = elementPosition;
+ filterCandidateList(secondSpanPostion);
+ return true;
+ }
+ // second span is not in an element
+ return false;
}
@Override
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/NonPartialOverlappingSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/NonPartialOverlappingSpans.java
index e18c04c..50fd643 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/NonPartialOverlappingSpans.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/NonPartialOverlappingSpans.java
@@ -16,8 +16,7 @@
/** An abstract class for Span enumeration whose two child spans are matched by
* their positions and do not have a partial overlap.
*
- * @author margaretha
- *
+ * @author margaretha
* */
public abstract class NonPartialOverlappingSpans extends SimpleSpans{
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/SimpleSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/SimpleSpans.java
index 0b7b08c..a7483aa 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/SimpleSpans.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/SimpleSpans.java
@@ -2,6 +2,7 @@
import java.io.IOException;
import java.util.Collection;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -17,18 +18,18 @@
/** An abstract class for Span enumeration including span match properties
* and basic methods.
*
- * @author margaretha
- *
+ * @author margaretha
* */
public abstract class SimpleSpans extends Spans{
+ private SimpleSpanQuery query;
protected boolean isStartEnumeration;
+
protected boolean hasMoreSpans;
- protected int matchDocNumber, matchStartPosition, matchEndPosition;
- protected List<byte[]> matchPayload;
-
// Warning: enumeration of Spans
protected Spans firstSpans, secondSpans;
- private SimpleSpanQuery query;
+
+ protected int matchDocNumber, matchStartPosition, matchEndPosition;
+ protected List<byte[]> matchPayload;
public SimpleSpans (SimpleSpanQuery simpleSpanQuery,
AtomicReaderContext context,
@@ -74,7 +75,25 @@
}
return true;
}
-
+
+ /** Find the same doc shared by element, firstspan and secondspan.
+ * @return true iff such a doc is found.
+ * */
+ protected boolean findSameDoc(Spans x,
+ Spans y, Spans e) throws IOException{
+
+ while (hasMoreSpans) {
+ if (ensureSameDoc(x, y) &&
+ e.doc() == x.doc()){
+ return true;
+ }
+ if (!ensureSameDoc(e,y)){
+ return false;
+ };
+ }
+ return false;
+ }
+
@Override
public int doc() {
return matchDocNumber;
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/TokenDistanceSpan.java b/src/main/java/de/ids_mannheim/korap/query/spans/TokenDistanceSpan.java
index a4f26fc..ab9a69f 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/TokenDistanceSpan.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/TokenDistanceSpan.java
@@ -99,4 +99,8 @@
return candidateSpan.getCost() + secondSpans.cost();
}
+ @Override
+ protected boolean isSecondSpanValid() throws IOException {
+ return true;
+ }
}
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedDistanceSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedDistanceSpans.java
index 018ce1d..9b80f60 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedDistanceSpans.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedDistanceSpans.java
@@ -17,22 +17,23 @@
import de.ids_mannheim.korap.query.SpanDistanceQuery;
-/** Enumeration of span matches, whose two child spans have a specific
- * range of distance (within a min and a max distance) and can be in
- * any order.
- * @author margaretha
+/** Enumeration of span matches, whose two child spans have a specific range
+ * of distance (within a min and a max distance) and can be in any order.
+ *
+ * @author margaretha
* */
-public class UnorderedDistanceSpans extends SimpleSpans{
+public abstract class UnorderedDistanceSpans extends SimpleSpans{
- private int minDistance, maxDistance;
+ protected int minDistance, maxDistance;
private boolean collectPayloads;
- private boolean hasMoreFirstSpans, hasMoreSecondSpans;
- private List<CandidateSpan> firstSpanList, secondSpanList;
-
- private List<CandidateSpan> matchList;
+ protected boolean hasMoreFirstSpans, hasMoreSecondSpans;
+ protected List<CandidateSpan> firstSpanList, secondSpanList;
+ protected List<CandidateSpan> matchList;
private long matchCost;
+ protected int updatedListNum;
+
private Logger log = LoggerFactory.getLogger(UnorderedDistanceSpans.class);
public UnorderedDistanceSpans(SpanDistanceQuery query,
@@ -65,95 +66,85 @@
private boolean advance() throws IOException {
while (hasMoreSpans || !matchList.isEmpty()){
if (!matchList.isEmpty()){
- setMatch();
+ setMatchProperties();
return true;
}
if (firstSpanList.isEmpty() && secondSpanList.isEmpty()){
-
- if (hasMoreFirstSpans && hasMoreSecondSpans &&
- ensureSameDoc(firstSpans, secondSpans)){
-
- firstSpanList.add(new CandidateSpan(firstSpans));
- secondSpanList.add(new CandidateSpan(secondSpans));
- hasMoreFirstSpans = firstSpans.next();
- hasMoreSecondSpans = secondSpans.next();
-
+ if (fillEmptyCandidateLists()){
setMatchList();
}
else { hasMoreSpans = false; }
}
- else { setMatchList(); }
-
+ else { setMatchList(); }
}
return false;
}
+ /** Add the next possible first and second spans. Both the spans must be in the
+ * same document. In UnorderedElementDistanceSpans, a span that is not in
+ * an element, is not added to its candidate list. The element must also be in
+ * the same document.
+ *
+ * @return true iff at least one of the candidate lists can be filled.
+ * */
+ protected abstract boolean fillEmptyCandidateLists() throws IOException;
+
/** Set the list of matches between the span having the smallest position, and
* its candidates. Simply remove the span if it does not have any candidates.
* */
- private void setMatchList() throws IOException {
+ protected void setMatchList() throws IOException {
hasMoreFirstSpans = setCandidateList(firstSpanList,firstSpans,
hasMoreFirstSpans,secondSpanList);
hasMoreSecondSpans = setCandidateList(secondSpanList,secondSpans,
- hasMoreSecondSpans,firstSpanList);
-
+ hasMoreSecondSpans,firstSpanList);
+
CandidateSpan currentFirstSpan, currentSecondSpan;
if (!firstSpanList.isEmpty() && !secondSpanList.isEmpty()){
currentFirstSpan = firstSpanList.get(0) ;
currentSecondSpan = secondSpanList.get(0);
- if (currentFirstSpan.getEnd() < currentSecondSpan.getEnd()){
+ if (currentFirstSpan.getEnd() <= currentSecondSpan.getEnd()){
matchList = findMatches(currentFirstSpan, secondSpanList);
- firstSpanList.remove(0);
+ updateList(firstSpanList);
}
else {
matchList = findMatches(currentSecondSpan, firstSpanList);
- secondSpanList.remove(0);
+ updateList(secondSpanList);
}
}
- else if (firstSpanList.isEmpty())
- secondSpanList.remove(0);
- else firstSpanList.remove(0);
+ else if (firstSpanList.isEmpty()){
+ updateList(secondSpanList);
+ }
+ else{
+ updateList(firstSpanList);
+ }
}
+ protected abstract void updateList(List<CandidateSpan> candidateList);
+
+ /** Set the candidate list for the first element in the target list.
+ * @return true iff the spans enumeration still has a next element
+ * to be a candidate
+ */
+ protected abstract boolean setCandidateList(List<CandidateSpan>
+ candidateList, Spans candidate, boolean hasMoreCandidates,
+ List<CandidateSpan> targetList) throws IOException;
+
/** Search all matches between the target span and its candidates in the candidate
* list.
* @return the matches in a list
* */
- private List<CandidateSpan> findMatches(CandidateSpan target, List<CandidateSpan>
- candidateList) {
-
- List<CandidateSpan> matches = new ArrayList<>();
- int actualDistance;
- for (CandidateSpan cs : candidateList){
- if (minDistance == 0 &&
- //intersection
- target.getStart() < cs.getEnd() &&
- cs.getStart() < target.getEnd()){
- matches.add(createMatchCandidate(target,cs,true));
- continue;
- }
-
- // left candidate
- if (cs.getEnd() < target.getStart())
- actualDistance = target.getStart() - cs.getEnd() +1;
- else // right candidate
- actualDistance = cs.getStart() - target.getEnd() +1;
-
- if (minDistance <= actualDistance && actualDistance <= maxDistance)
- matches.add(createMatchCandidate(target, cs, false));
- }
- return matches;
- }
+ protected abstract List<CandidateSpan> findMatches(CandidateSpan target,
+ List<CandidateSpan> candidateList);
/** Compute match properties and create a candidate span match
* to be added to the match list.
* @return a candidate span match
* */
- private CandidateSpan createMatchCandidate(CandidateSpan target,
+ protected CandidateSpan createMatchCandidate(CandidateSpan target,
CandidateSpan cs, boolean isDistanceZero) {
int start = Math.min(target.getStart(), cs.getStart());
@@ -173,48 +164,10 @@
return new CandidateSpan(start,end,doc,cost,payloads);
}
- /** Set the candidate list for the first element in the target list.
- * @return true iff the spans enumeration still has a next element
- * to be a candidate
- */
- private boolean setCandidateList(List<CandidateSpan>
- candidateList, Spans candidate, boolean hasMoreCandidates,
- List<CandidateSpan> targetList) throws IOException {
-
- if (!targetList.isEmpty()){
- CandidateSpan target = targetList.get(0);
- while (hasMoreCandidates && candidate.doc() == target.getDoc()
- && isWithinMaxDistance(target,candidate)){
- candidateList.add(new CandidateSpan(candidate));
- hasMoreCandidates = candidate.next();
- }
- }
- return hasMoreCandidates;
- }
-
- /** Check if the target and candidate spans are not too far from each other.
- * @return true iff the target and candidate spans are within the maximum
- * distance
+ /** Assign the first candidate span in the match list as the current span match.
* */
- private boolean isWithinMaxDistance(CandidateSpan target, Spans candidate) {
- // left candidate
- if (candidate.end() < target.getStart() &&
- candidate.end() + maxDistance <= target.getStart()){
- return false;
- }
- // right candidate
- if (candidate.start() > target.getEnd() &&
- target.getEnd() + maxDistance <= candidate.start()){
- return false;
- }
- return true;
- }
-
- /** Assign the first candidate span in the match list as
- * the current span match.
- * */
- private void setMatch() {
+ private void setMatchProperties() {
CandidateSpan cs = matchList.get(0);
matchDocNumber = cs.getDoc();
matchStartPosition = cs.getStart();
@@ -222,7 +175,7 @@
matchCost = cs.getCost();
matchPayload.addAll(cs.getPayloads());
matchList.remove(0);
-
+
log.trace("Match doc#={} start={} end={}", matchDocNumber,
matchStartPosition,matchEndPosition);
}
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedElementDistanceSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedElementDistanceSpans.java
new file mode 100644
index 0000000..2483720
--- /dev/null
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedElementDistanceSpans.java
@@ -0,0 +1,209 @@
+package de.ids_mannheim.korap.query.spans;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.lucene.index.AtomicReaderContext;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermContext;
+import org.apache.lucene.search.spans.Spans;
+import org.apache.lucene.util.Bits;
+
+import de.ids_mannheim.korap.query.SpanDistanceQuery;
+
+/** Enumeration of span matches, whose two child spans have a specific range
+ * of distance (within a min and a max distance) and can be in any order.
+ * The unit distance is an element position, where element can be a sentence
+ * or a paragraph.
+ *
+ * @author margaretha
+ * */
+public class UnorderedElementDistanceSpans extends UnorderedDistanceSpans{
+
+ private Spans elements;
+ private boolean hasMoreElements;
+ private int elementPosition;
+
+ // contains all previous elements whose position is greater than the last
+ // target span
+ private List<CandidateSpan> elementList;
+ private int currentDoc;
+
+ public UnorderedElementDistanceSpans(SpanDistanceQuery query,
+ AtomicReaderContext context, Bits acceptDocs,
+ Map<Term, TermContext> termContexts) throws IOException {
+ super(query, context, acceptDocs, termContexts);
+ elements = query.getElementQuery().
+ getSpans(context, acceptDocs, termContexts);
+ hasMoreElements = elements.next();
+ elementPosition=0;
+ elementList = new ArrayList<CandidateSpan>();
+ }
+
+ @Override
+ protected boolean fillEmptyCandidateLists() throws IOException {
+ int position;
+ while (firstSpanList.isEmpty() && secondSpanList.isEmpty()){
+
+ if (hasMoreFirstSpans && hasMoreSecondSpans && hasMoreElements &&
+ findSameDoc(firstSpans, secondSpans, elements)){
+
+ if (currentDoc != firstSpans.doc()){
+ currentDoc = firstSpans.doc();
+ elementList.clear();
+ }
+
+ position = findElementPosition(firstSpans);
+ if (position != -1)
+ firstSpanList.add(new CandidateSpan(firstSpans,position));
+
+ position = findElementPosition(secondSpans);
+ if (position != -1)
+ secondSpanList.add(new CandidateSpan(secondSpans,position));
+
+ hasMoreFirstSpans = firstSpans.next();
+ hasMoreSecondSpans = secondSpans.next();
+ }
+ else { return false; }
+ }
+ return true;
+ }
+
+ /** Find the element position of the span in the element list or by advancing
+ * the element spans until encountering the span.
+ *
+ * @return the element position
+ * */
+ private int findElementPosition(Spans span) throws IOException {
+ // Check in the element list
+ if (!elementList.isEmpty() &&
+ span.end() <= elementList.get(elementList.size()-1).getEnd()){
+
+ for (CandidateSpan e : elementList)
+ if (e.getEnd() >= span.end() && e.getStart() <= span.start()){
+ return e.getPosition();
+ }
+ return -1; // The span is not in an element.
+ }
+
+ return ( advanceElementTo(span) ? elementPosition : -1 );
+ }
+
+ /** Advance the element spans until encountering the given span.
+ *
+ * @return true iff such an element is found, false if the span is not in
+ * an element.
+ * */
+ private boolean advanceElementTo(Spans span) throws IOException {
+ while (hasMoreElements &&
+ elements.doc() == currentDoc &&
+ elements.start() < span.end()){
+
+ if (span.start() >= elements.start() &&
+ span.end() <= elements.end()){
+ return true;
+ }
+ elementList.add(new CandidateSpan(elements,elementPosition));
+ hasMoreElements = elements.next();
+ elementPosition++;
+ }
+
+ return false; // invalid
+ }
+
+ @Override
+ protected boolean setCandidateList(List<CandidateSpan>
+ candidateList, Spans candidate, boolean hasMoreCandidates,
+ List<CandidateSpan> targetList) throws IOException {
+
+ if (!targetList.isEmpty()){
+ CandidateSpan cs;
+ CandidateSpan target = targetList.get(0);
+ int position;
+ while (hasMoreCandidates && candidate.doc() == target.getDoc()){
+ position = findElementPosition(candidate);
+ if (position != -1){
+ cs = new CandidateSpan(candidate,position);
+
+ if (isWithinMaxDistance(target, cs)){
+ candidateList.add(cs);
+ }
+ else break;
+ }
+ hasMoreCandidates = candidate.next();
+ }
+ }
+ return hasMoreCandidates;
+ }
+
+ /** Check if the target and candidate spans are not too far from each other.
+ *
+ * @return true iff the target and candidate spans are within the maximum
+ * distance
+ * */
+ protected boolean isWithinMaxDistance(CandidateSpan target, CandidateSpan candidate) {
+ int candidatePos = candidate.getPosition();
+ int targetPos = target.getPosition();
+
+ // left candidate
+ if (candidatePos < targetPos &&
+ candidatePos + maxDistance < targetPos){
+ return false;
+ }
+ // right candidate
+ if (candidatePos > targetPos &&
+ targetPos + maxDistance < candidatePos){
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ protected List<CandidateSpan> findMatches(CandidateSpan target, List<CandidateSpan>
+ candidateList) {
+
+ List<CandidateSpan> matches = new ArrayList<>();
+
+ int actualDistance;
+ int targetPos = target.getPosition();
+
+ for (CandidateSpan cs : candidateList){
+ actualDistance = Math.abs( targetPos - cs.getPosition() );
+
+ if (minDistance == 0 && actualDistance == 0){
+ matches.add(createMatchCandidate(target,cs,true));
+ continue;
+ }
+
+ if (minDistance <= actualDistance && actualDistance <= maxDistance)
+ matches.add(createMatchCandidate(target, cs, false));
+ }
+ return matches;
+ }
+
+ @Override
+ protected void updateList(List<CandidateSpan> candidateList) {
+ updateElementList(candidateList.get(0).getPosition());
+ candidateList.remove(0);
+ }
+
+ /** Reduce the number of elements kept in the element list by removing the element
+ * whose position is smaller than or identical to the position of the last target
+ * span.
+ * */
+ private void updateElementList(int position){
+ Iterator<CandidateSpan> i = elementList.iterator();
+ CandidateSpan e;
+ while(i.hasNext()){
+ e = i.next();
+ if (e.getPosition() < position) {
+ //System.out.println("pos "+position+" size "+ elementList.size());
+ i.remove();
+ }
+ break;
+ }
+ }
+}
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedTokenDistanceSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedTokenDistanceSpans.java
new file mode 100644
index 0000000..8d786d9
--- /dev/null
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/UnorderedTokenDistanceSpans.java
@@ -0,0 +1,110 @@
+package de.ids_mannheim.korap.query.spans;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.lucene.index.AtomicReaderContext;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermContext;
+import org.apache.lucene.search.spans.Spans;
+import org.apache.lucene.util.Bits;
+
+import de.ids_mannheim.korap.query.SpanDistanceQuery;
+
+/** Enumeration of span matches, whose two child spans have a specific range
+ * of distance (within a min and a max distance) and can be in any order.
+ * The unit distance is a token position.
+ *
+ * @author margaretha
+ * */
+public class UnorderedTokenDistanceSpans extends UnorderedDistanceSpans{
+
+ public UnorderedTokenDistanceSpans(SpanDistanceQuery query,
+ AtomicReaderContext context, Bits acceptDocs,
+ Map<Term, TermContext> termContexts) throws IOException {
+ super(query, context, acceptDocs, termContexts);
+ }
+
+ @Override
+ protected boolean fillEmptyCandidateLists() throws IOException {
+ if (hasMoreFirstSpans && hasMoreSecondSpans &&
+ ensureSameDoc(firstSpans, secondSpans)){
+ firstSpanList.add(new CandidateSpan(firstSpans));
+ secondSpanList.add(new CandidateSpan(secondSpans));
+ hasMoreFirstSpans = firstSpans.next();
+ hasMoreSecondSpans = secondSpans.next();
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ protected boolean setCandidateList(List<CandidateSpan>
+ candidateList, Spans candidate, boolean hasMoreCandidates,
+ List<CandidateSpan> targetList) throws IOException {
+
+ if (!targetList.isEmpty()){
+ CandidateSpan target = targetList.get(0);
+ while (hasMoreCandidates && candidate.doc() == target.getDoc()
+ && isWithinMaxDistance(target,candidate)){
+ candidateList.add(new CandidateSpan(candidate));
+ hasMoreCandidates = candidate.next();
+ }
+ }
+ return hasMoreCandidates;
+ }
+
+ /** Check if the target and candidate spans are not too far from each other.
+ * @return true iff the target and candidate spans are within the maximum
+ * distance
+ * */
+ protected boolean isWithinMaxDistance(CandidateSpan target, Spans candidate) {
+ // left candidate
+ if (candidate.end() < target.getStart() &&
+ candidate.end() + maxDistance <= target.getStart()){
+ return false;
+ }
+ // right candidate
+ if (candidate.start() > target.getEnd() &&
+ target.getEnd() + maxDistance <= candidate.start()){
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ protected List<CandidateSpan> findMatches(CandidateSpan target, List<CandidateSpan>
+ candidateList) {
+
+ List<CandidateSpan> matches = new ArrayList<>();
+ int actualDistance;
+ for (CandidateSpan cs : candidateList){
+ if (minDistance == 0 &&
+ //intersection
+ target.getStart() < cs.getEnd() &&
+ cs.getStart() < target.getEnd()){
+ matches.add(createMatchCandidate(target,cs,true));
+ continue;
+ }
+
+ // left candidate
+ if (cs.getEnd() < target.getStart())
+ actualDistance = target.getStart() - cs.getEnd() +1;
+ else // right candidate
+ actualDistance = cs.getStart() - target.getEnd() +1;
+
+ if (minDistance <= actualDistance && actualDistance <= maxDistance)
+ matches.add(createMatchCandidate(target, cs, false));
+ }
+ return matches;
+ }
+
+ @Override
+ protected void updateList(List<CandidateSpan> candidateList) {
+ candidateList.remove(0);
+ }
+
+}