More bit shifting for FrameConstraints
diff --git a/src/main/java/de/ids_mannheim/korap/query/FrameConstraint.java b/src/main/java/de/ids_mannheim/korap/query/FrameConstraint.java
index 77edc69..c26aba6 100644
--- a/src/main/java/de/ids_mannheim/korap/query/FrameConstraint.java
+++ b/src/main/java/de/ids_mannheim/korap/query/FrameConstraint.java
@@ -1,5 +1,7 @@
package de.ids_mannheim.korap.query;
import de.ids_mannheim.korap.util.QueryException;
+import org.apache.lucene.search.spans.Spans;
+
import java.util.*;
/**
@@ -54,10 +56,29 @@
*/
public class FrameConstraint {
- public static final Integer FRAME_ALL = 1024 * 8 - 1;
+ public static final int
+ PRECEDES = 1,
+ PRECEDES_DIRECTLY = 1 << 1,
+ OVERLAPS_LEFT = 1 << 2,
+ ALIGNS_LEFT = 1 << 3,
+ STARTS_WITH = 1 << 4,
+ MATCHES = 1 << 5,
+ IS_WITHIN = 1 << 6,
+ IS_AROUND = 1 << 7,
+ ENDS_WITH = 1 << 8,
+ ALIGNS_RIGHT = 1 << 9,
+ OVERLAPS_RIGHT = 1 << 10,
+ SUCCEEDS_DIRECTLY = 1 << 11,
+ SUCCEEDS = 1 << 12,
+ ALL = 1024 * 8 - 1;
+
+
private static final Map<String,Integer> FRAME;
+ private static final List<Integer> NEXT_B;
+
static {
Map<String, Integer> FRAME_t = new HashMap<>();
+ List<Integer> NEXT_B_t = new ArrayList(16);
/*
* A precedes B
@@ -67,8 +88,8 @@
*
* A.end < B.start
*/
- FRAME_t.put("precedes", 1);
-
+ FRAME_t.put("precedes", PRECEDES);
+ NEXT_B_t.add(PRECEDES);
/*
* A precedes B directly
*
@@ -77,7 +98,8 @@
*
* A.end == b.start
*/
- FRAME_t.put("precedesDirectly", 1 << 1);
+ FRAME_t.put("precedesDirectly", PRECEDES_DIRECTLY);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY);
/*
* A overlaps B to the left
@@ -87,7 +109,8 @@
*
* a.end < b.end && a.end > b.start && a.start < b.start
*/
- FRAME_t.put("overlapsLeft", 1 << 2);
+ FRAME_t.put("overlapsLeft", OVERLAPS_LEFT);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT);
/*
* A aligns B to the left
@@ -97,7 +120,8 @@
*
* a.end < b.end && a.start == b.start
*/
- FRAME_t.put("alignsLeft", 1 << 3);
+ FRAME_t.put("alignsLeft", ALIGNS_LEFT);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT | ALIGNS_LEFT);
/*
* A starts with B
@@ -107,7 +131,10 @@
*
* a.end > b.end && a.start == b.start
*/
- FRAME_t.put("startsWith", 1 << 4);
+ FRAME_t.put("startsWith", STARTS_WITH);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT |
+ ALIGNS_LEFT | STARTS_WITH | MATCHES |
+ IS_AROUND | ENDS_WITH);
/*
* A matches B
@@ -117,7 +144,9 @@
*
* a.end = b.end && a.start = b.start
*/
- FRAME_t.put("matches", 1 << 5);
+ FRAME_t.put("matches", MATCHES);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT |
+ ALIGNS_LEFT | MATCHES | ENDS_WITH);
/*
* A is within B
@@ -127,7 +156,8 @@
*
* a.end < b.end && a.start > b.start
*/
- FRAME_t.put("isWithin", 1 << 6);
+ FRAME_t.put("isWithin", IS_WITHIN);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | ALIGNS_LEFT | IS_WITHIN);
/*
* A is around B
@@ -137,7 +167,9 @@
*
* a.start < b.start && a.end > b.end
*/
- FRAME_t.put("isAround", 1 << 7);
+ FRAME_t.put("isAround", IS_AROUND);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT |
+ IS_AROUND | ENDS_WITH);
/*
* A ends with B
@@ -147,7 +179,8 @@
*
* a.start < b.start && a.end == b.end
*/
- FRAME_t.put("endsWith", 1 << 8);
+ FRAME_t.put("endsWith", ENDS_WITH);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT | ENDS_WITH);
/*
* A aligns B to the right
@@ -157,7 +190,9 @@
*
* a.start > b.start && a.end == b.end
*/
- FRAME_t.put("alignsRight", 1 << 9);
+ FRAME_t.put("alignsRight", ALIGNS_RIGHT);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | ALIGNS_LEFT |
+ MATCHES | IS_WITHIN | ALIGNS_RIGHT);
/*
* A overlaps B to the right
@@ -165,9 +200,12 @@
* |-A-|
* |-B-|
*
- * a.start > b.start && a.start < b.end && && a.end > b.end
+ * a.start > b.start && a.start < b.end && a.end > b.end
*/
- FRAME_t.put("overlapsRight", 1 << 10);
+ FRAME_t.put("overlapsRight", OVERLAPS_RIGHT);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT |
+ ALIGNS_LEFT | STARTS_WITH | MATCHES | IS_WITHIN |
+ IS_AROUND | ENDS_WITH | ALIGNS_RIGHT | OVERLAPS_RIGHT);
/*
* A succeeds B directly
@@ -177,7 +215,11 @@
*
* a.start == b.end
*/
- FRAME_t.put("succeedsDirectly", 1 << 11);
+ FRAME_t.put("succeedsDirectly", SUCCEEDS_DIRECTLY);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | OVERLAPS_LEFT |
+ ALIGNS_LEFT | STARTS_WITH | MATCHES | IS_WITHIN |
+ IS_AROUND | ENDS_WITH | ALIGNS_RIGHT |
+ OVERLAPS_RIGHT | SUCCEEDS_DIRECTLY);
/*
* A succeeds B
@@ -187,8 +229,13 @@
*
* a.start > b.end
*/
- FRAME_t.put("succeeds", 1 << 12);
- FRAME = Collections.unmodifiableMap(FRAME_t);
+ FRAME_t.put("succeeds", SUCCEEDS);
+ NEXT_B_t.add(PRECEDES | PRECEDES_DIRECTLY | ALIGNS_LEFT |
+ STARTS_WITH | MATCHES | IS_WITHIN |
+ ALIGNS_RIGHT | SUCCEEDS_DIRECTLY | SUCCEEDS);
+
+ FRAME = Collections.unmodifiableMap(FRAME_t);
+ NEXT_B = Collections.unmodifiableList(NEXT_B_t);
};
// Bitvector representing the frame constraint
@@ -240,7 +287,7 @@
* @return The {@link FrameConstraint} for chaining.
*/
public FrameConstraint invert () {
- this.vector ^= FRAME_ALL;
+ this.vector ^= ALL;
return this;
};
@@ -283,4 +330,94 @@
public boolean check (FrameConstraint conditions) {
return (this.vector & conditions.vector) != 0;
};
+
+
+
+ // Todo: create nextB arraymatrix by adding all combinations of constellation precomputed
+ // NEXTB[SUCCEEDS_DIRECTLY | SUCCEEDS] = NEXTB[SUCEEDS_DIRECTLY] | NEXTB[SUCCEEDS];
+
+ // NextB
+ // Integer.numberOfTrailingZeros();
+ private static int _next_b (int constellation) {
+ return NEXT_B.get(Integer.numberOfTrailingZeros(constellation));
+ };
+
+
+ // Return a configuration, saying:
+ // 1. Binary: It matches - it doesn't match!
+ // 2. Binary: Go on by forwarding a
+ // 3. Binary: Go on by forwarding b
+ // 4. The constellation
+ public int _constellation (Spans a, Spans b) {
+
+ // Constellation checks are
+ // optimized for lazy loading,
+ // i.e. trying to minimize callings of end()
+
+ // A starts after B
+ if (a.start() > b.start()) {
+
+ // if (this.vector & next_b(SUCCEEDS_DIRECTLY) > 0)
+
+ // Don't call end() on A
+ if (a.start() == b.end())
+ return SUCCEEDS_DIRECTLY;
+
+ if (a.start() > b.end())
+ return SUCCEEDS;
+
+ // a) Check if match is possible
+ // b) Check if mext is possible on A
+
+ // Call end() on A
+ else if (a.end() == b.end()) {
+ return ALIGNS_RIGHT;
+ }
+
+ else if (a.end() < b.end()) {
+ return IS_WITHIN;
+ };
+
+ // a.end() > b.end() &&
+ // a.start() < b.end()
+ return OVERLAPS_RIGHT;
+ }
+
+ // A starts before B
+ else if (a.start() < b.start()) {
+
+ // Don't call end() on b
+ if (a.end() == b.start()) {
+ return PRECEDES_DIRECTLY;
+ }
+
+ else if (a.end() < b.start()) {
+ return PRECEDES;
+ }
+
+ // Call end() on B
+ else if (a.end() == b.end()) {
+ return ENDS_WITH;
+ }
+
+ else if (a.end() > b.end()) {
+ return IS_AROUND;
+ };
+
+ // a.end() > b.start()
+ return OVERLAPS_LEFT;
+ }
+
+ // A and B start at the same position
+ // a.start() == b.start()
+ else if (a.end() > b.end()) {
+ return STARTS_WITH;
+ }
+ else if (a.end() < b.end()) {
+ return ALIGNS_LEFT;
+ };
+
+ // a.end() == b.end()
+ return MATCHES;
+ };
};
diff --git a/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java b/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
index a6f9eb3..e0324d4 100644
--- a/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
+++ b/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
@@ -1120,7 +1120,7 @@
System.out.println(km.getStartPos() +","+km.getEndPos()+" "
+km.getSnippetBrackets());
};
-*/
+ */
};
diff --git a/src/test/java/de/ids_mannheim/korap/query/TestFrameConstraint.java b/src/test/java/de/ids_mannheim/korap/query/TestFrameConstraint.java
index 4600248..fd4285f 100644
--- a/src/test/java/de/ids_mannheim/korap/query/TestFrameConstraint.java
+++ b/src/test/java/de/ids_mannheim/korap/query/TestFrameConstraint.java
@@ -203,9 +203,99 @@
assertEquals(fc1.check("succeeds"), true);
};
+ @Test
+ public void testConstellation () throws QueryException {
+ FrameConstraint fc1 = new FrameConstraint();
+ fc1.invert();
+
+ // Precedes
+ assertEquals(
+ FrameConstraint.PRECEDES,
+ fc1._constellation(new TestSpans(2,3), new TestSpans(4,5))
+ );
+
+ // PrecedesDirectly
+ assertEquals(
+ FrameConstraint.PRECEDES_DIRECTLY,
+ fc1._constellation(new TestSpans(2,3), new TestSpans(3,5))
+ );
+
+ // OverlapsLeft
+ assertEquals(
+ FrameConstraint.OVERLAPS_LEFT,
+ fc1._constellation(new TestSpans(2,4), new TestSpans(3,5))
+ );
+
+ // AlignsLeft
+ assertEquals(
+ FrameConstraint.ALIGNS_LEFT,
+ fc1._constellation(new TestSpans(2,4), new TestSpans(2,5))
+ );
+
+ // StartsWith
+ assertEquals(
+ FrameConstraint.STARTS_WITH,
+ fc1._constellation(new TestSpans(2,5), new TestSpans(2,4))
+ );
+
+ // Matches
+ assertEquals(
+ FrameConstraint.MATCHES,
+ fc1._constellation(new TestSpans(2,5), new TestSpans(2,5))
+ );
+
+ // IsWithin
+ assertEquals(
+ FrameConstraint.IS_WITHIN,
+ fc1._constellation(new TestSpans(3,4), new TestSpans(2,5))
+ );
+
+ // IsAround
+ assertEquals(
+ FrameConstraint.IS_AROUND,
+ fc1._constellation(new TestSpans(2,5), new TestSpans(3,4))
+ );
+
+ // EndsWith
+ assertEquals(
+ FrameConstraint.ENDS_WITH,
+ fc1._constellation(new TestSpans(3,5), new TestSpans(4,5))
+ );
+
+ // AlignsRight
+ assertEquals(
+ FrameConstraint.ALIGNS_RIGHT,
+ fc1._constellation(new TestSpans(3,4), new TestSpans(2,4))
+ );
+
+ // OverlapsRight
+ assertEquals(
+ FrameConstraint.OVERLAPS_RIGHT,
+ fc1._constellation(new TestSpans(3,5), new TestSpans(2,4))
+ );
+
+ // SucceedsDirectly
+ assertEquals(
+ FrameConstraint.SUCCEEDS_DIRECTLY,
+ fc1._constellation(new TestSpans(4,6), new TestSpans(2,4))
+ );
+
+ // Succeeds
+ assertEquals(
+ FrameConstraint.SUCCEEDS,
+ fc1._constellation(new TestSpans(5,6), new TestSpans(2,4))
+ );
+ };
+
private class TestSpans extends Spans {
private int s, e;
+ // Constructor
+ public TestSpans (int start, int end) {
+ this.s = start;
+ this.e = end;
+ };
+
@Override
public int doc () {
return 0;