You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@uima.apache.org by sc...@apache.org on 2015/05/05 05:31:59 UTC
svn commit: r1677731 [2/2] - in /uima/uimaj/trunk/uimaj-core/src:
main/java/org/apache/uima/cas/impl/ main/java/org/apache/uima/internal/util/
main/java/org/apache/uima/internal/util/rb_trees/
test/java/org/apache/uima/cas/impl/ test/java/org/apache/ui...
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java Tue May 5 03:31:59 2015
@@ -32,20 +32,6 @@ import org.apache.uima.internal.util.Str
public class IntArrayRBTcommon {
static final boolean debug = false;
- static final protected boolean useklrp = true;
- // Keys.
- protected int[] key;
-
- // Left daughters.
- protected int[] left;
-
- // Right daughters.
- protected int[] right;
-
- // Parents.
- protected int[] parent;
-
- // alternate layout
protected int[] klrp;
// the next 3 are for the rare cases where the number of entries
// in this instance exceeds 512 * 1024 * 1024 - 1
@@ -79,9 +65,6 @@ public class IntArrayRBTcommon {
protected int setXXX(int node, int offset, int value) {
if (node < MAXklrp0) {
-// if (((node << 2) + offset) >= klrp.length) {
-// System.out.println("caught");
-// }
return klrp[(node << 2) + offset] = value;
} else {
final int w = node >> 29;
@@ -99,60 +82,45 @@ public class IntArrayRBTcommon {
}
}
- protected int getKey(int node) {
- if (useklrp) {
- return getXXX(node, 0);
- }
- return key[node];
+ private int getKey(int node) {
+ return getXXX(node, 0);
}
- protected int setKey(int node, int value) {
- if (useklrp) {
- return setXXX(node, 0, value);
- }
- return key[node] = value;
+ private int setKey(int node, int value) {
+ return setXXX(node, 0, value);
}
protected int getLeft(int node) {
- if (useklrp) {
- return getXXX(node, 1);
- }
- return left[node];
+ return getXXX(node, 1);
}
protected int setLeft(int node, int value) {
- if (useklrp) {
- return setXXX(node, 1, value);
- }
- return left[node] = value;
+ return setXXX(node, 1, value);
}
protected int getRight(int node) {
- if (useklrp) {
- return getXXX(node, 2);
- }
- return right[node];
+ return getXXX(node, 2);
}
protected int setRight(int node, int value) {
- if (useklrp) {
- return setXXX(node, 2, value);
- }
- return right[node] = value;
+ return setXXX(node, 2, value);
}
protected int getParent(int node) {
- if (useklrp) {
- return getXXX(node, 3);
- }
- return parent[node];
+ return getXXX(node, 3);
}
+ /**
+ * @param node
+ * @param value
+ * @return the value
+ */
protected int setParent(int node, int value) {
- if (useklrp) {
- return setXXX(node, 3, value);
- }
- return parent[node] = value;
+ return setXXX(node, 3, value);
+ }
+
+ protected int getKeyForNode(int node) {
+ return getKey(node);
}
// Colors.
@@ -170,10 +138,11 @@ public class IntArrayRBTcommon {
// Keep a pointer to the largest node around so we can optimize for
// inserting
- // keys that are larger than all keys already in the tree.
- protected int greatestNode;
+ // keys that are larger than all keys already in the tree
+ // internal use, public because used by iterators in different package
+ public int greatestNode;
- protected static final int default_size = 1024; // must be pwr of 2 for useklrp true
+ protected static final int default_size = 8; // must be pwr of 2 for useklrp true
final protected int initialSize;
@@ -213,14 +182,7 @@ public class IntArrayRBTcommon {
protected void setupArrays() {
// Init the arrays.
- if (useklrp) {
- klrp = new int[initialSize << 2];
- } else {
- this.key = new int[initialSize];
- this.left = new int[initialSize];
- this.right = new int[initialSize];
- this.parent = new int[initialSize];
- }
+ klrp = new int[initialSize << 2];
this.color = new boolean[initialSize];
setLeft(NIL, NIL);
setRight(NIL, NIL);
@@ -239,14 +201,8 @@ public class IntArrayRBTcommon {
// All we do for flush is set the root to NIL and the size to 0.
initVars();
// and potentially release extra storage
- if (useklrp) {
- if (klrp.length > (initialSize << 2)) {
- setupArrays();
- }
- } else {
- if (key.length > initialSize) {
- setupArrays();
- }
+ if (klrp.length > (initialSize << 2)) {
+ setupArrays();
}
}
@@ -285,7 +241,7 @@ public class IntArrayRBTcommon {
// to be expanded.
final int w = requiredSize >> 29; // w is 0-3
- final int requiredCapacityForLastSegment = Math.max(1024, requiredSize - w * MAXklrp0);
+ final int requiredCapacityForLastSegment = nextPowerOf2(requiredSize - w * MAXklrp0);
switch (w) {
case 3: {
if (klrp3 == null) {
@@ -331,13 +287,6 @@ public class IntArrayRBTcommon {
throw new RuntimeException();
}
}
-
- private void ensureCapacityNotKrlp(int requiredSize) {
- this.key = ensureArrayCapacity(this.key, requiredSize);
- this.left = ensureArrayCapacity(this.left, requiredSize);
- this.right = ensureArrayCapacity(this.right, requiredSize);
- this.parent = ensureArrayCapacity(this.parent, requiredSize);
- }
// only called for krlp style
private int[] maximize(int[] array) {
@@ -352,23 +301,18 @@ public class IntArrayRBTcommon {
protected int newNode(final int k) {
// Make sure the tree is big enough to accommodate a new node.
- if (useklrp) {
- int lenKlrp = (klrp.length >> 2);
- if (klrp1 != null) {
- lenKlrp += (klrp1.length >> 2);
- if (klrp2 != null) {
- lenKlrp += (klrp2.length >> 2);
- if (klrp3 != null) {
- lenKlrp += (klrp3.length >> 2);
- }
+ int lenKlrp = (klrp.length >> 2);
+ if (klrp1 != null) {
+ lenKlrp += (klrp1.length >> 2);
+ if (klrp2 != null) {
+ lenKlrp += (klrp2.length >> 2);
+ if (klrp3 != null) {
+ lenKlrp += (klrp3.length >> 2);
}
}
- if (this.next >= lenKlrp) {
- ensureCapacityKlrp(this.next + 1);
- }
- } else {
- // not using klrp format
- ensureCapacityNotKrlp(this.next + 1);
+ }
+ if (this.next >= lenKlrp) {
+ ensureCapacityKlrp(this.next + 1);
}
if (this.next >= this.color.length){
@@ -455,48 +399,74 @@ public class IntArrayRBTcommon {
/**
* @param k -
- * @return the first node such that k <= key[node].
+ * @return the first node such that k = key[node].
*/
- protected int findKey(final int k) {
+ public int findKey(final int k) {
return findKeyDown(k, this.root);
}
protected int findKeyDown(final int k, int node) {
while (node != NIL) {
- final int keyNode = getKey(node);
- if (k < keyNode) {
- node = getLeft(node);
- } else if (k == keyNode) {
+ final int cr = compare(k, getKey(node));
+ if (0 == cr) {
return node;
- } else {
- node = getRight(node);
- }
+ }
+ node = (cr < 0) ? getLeft(node) : getRight(node);
}
- // node == NIL
return NIL;
}
/**
* Find the node such that key[node] ≥ k and key[previous(node)] < k.
- * @param k -
- * @return the node such that key[node] ≥ k and key[previous(node)] < k.
+ * If k is less than all the nodes, then the first node is returned
+ * If k is greater than all the nodes, then NIL is returned (invalid signal)
+ * @param k the key
+ * @return the index of the node, or NIL if k > all keys
*/
+ public int findInsertionPoint(final int k) {
+ return findInsertionPointCmn(k, true);
+ }
+
+ /**
+ * Find the node such that key[node] ≥ k and key[previous(node)] < k.
+ * @param k -
+ * @return the node such that key[node] ≥ k and key[previous(node)] < k.
+ */
public int findInsertionPointNoDups(final int k) {
+ return findInsertionPointCmn(k, false);
+ }
+
+ public int findInsertionPointCmn(final int k, boolean moveToLeftmost) {
int node = this.root;
int found = node;
+ int cr = 0;
+
while (node != NIL) {
found = node;
- final int keyNode = getKey(node);
- if (k < keyNode) {
- node = getLeft(node);
- } else if (k == keyNode) {
- return node;
- } else {
- node = getRight(node);
+ cr = compare(k, getKey(node));
+
+ if (0 == cr) {
+ // found a match, but in the presence of duplicates, need to
+ // move to the left most one
+ if (moveToLeftmost) {
+ while (true) {
+ int leftmost = previousNode(node);
+ if (NIL == leftmost || (0 != compare(k, getKey(leftmost)))) {
+ return node;
+ }
+ node = leftmost;
+ }
+ } else {
+ return found;
+ }
}
+
+ node = (cr < 0) ? getLeft(node) : getRight(node);
}
- // node == NIL
- return found;
+
+ // compare not equal, and ran out of elements (not found)
+ // if k > all nodes, return NIL
+ return (cr > 0) ? NIL : found;
}
public final boolean containsKey(int k) {
@@ -507,7 +477,8 @@ public class IntArrayRBTcommon {
return (findKey(k) != NIL);
}
- protected final int getFirstNode() {
+ // internal use, public to access by internal routine in another package
+ public final int getFirstNode() {
if (this.root == NIL) {
return NIL;
}
@@ -519,118 +490,138 @@ public class IntArrayRBTcommon {
}
node = left_node;
}
-// while (getLeft(node) != NIL) {
-// node = getLeft(node);
-// }
return node;
}
- // private final int nextNode(int node) {
- // if (right[node] != NIL) {
- // node = right[node];
- // while (left[node] != NIL) {
- // node = left[node];
- // }
- // } else {
- // while (isRightDtr(node)) {
- // node = parent[node];
- // }
- // if (node == root) {
- // return NIL;
- // }
- // // node is now a left dtr, so we can go one up.
- // node = parent[node];
- // }
- // return node;
- // }
-
- protected final int nextNode(int node) {
- int y;
+ // internal use, public only to get cross package internal reference
+ /**
+ * Method: if there's a right descendant, return the left-most chain down on that link
+ * Else, go up until parent has a right descendant not the previous, and return that.
+ *
+ * @param node starting point
+ * @return the node logically following this one.
+ */
+ public final int nextNode(int node) {
+ if (node == NIL) {
+ return NIL;
+ }
final int rightNode = getRight(node);
if (rightNode != NIL) {
node = rightNode;
while (true) {
final int leftNode = getLeft(node);
if (leftNode == NIL) {
- break;
+ return node;
}
node = leftNode;
}
-// while (getLeft(node) != NIL) {
-// node = getLeft(node);
-// }
- } else {
- y = getParent(node);
- while ((y != NIL) && (node == getRight(y))) {
- node = y;
- y = getParent(y);
+ }
+
+ while (true) {
+ if (node == this.root) { // if initial node is the root, can't go up.
+ return NIL;
+ }
+ final int parentNode = getParent(node); // guaranteed parentNode not NIL because it's tested above and below
+ final int nextNode = getRight(parentNode); // Can be NIL
+ if (node != nextNode) {
+ return parentNode;
+ }
+ if (parentNode == this.root) {
+ return NIL;
}
- node = y;
+ node = parentNode;
}
- return node;
}
- protected final int previousNode(int node) {
+ // internal use, public only to get cross package internal reference
+ /**
+ * Method: if there's a left descendant, go to the right-most bottom of that
+ * Otherwise, ascend up until the parent's left descendant isn't the previous link
+ * @param node the current node index
+ * @return the previous node index or NIL
+ */
+ public final int previousNode(int node) {
+ if (node == NIL) {
+ return NIL;
+ }
final int leftNode = getLeft(node);
if (leftNode != NIL) {
node = leftNode;
while (true) {
final int rightNode = getRight(node);
if (rightNode == NIL) {
- break;
+ return node;
}
node = rightNode;
}
-// while (getRight(node) != NIL) {
-// node = getRight(node);
-// }
- } else {
- while (true) {
- final int parentNode = getParent(node);
- if (node == this.root || (node != getLeft(parentNode))) {
- break;
- }
- node = parentNode;
- }
-
-// (node != this.root) && (node == getLeft(getParent(node))))
-// while (node != this.root && (node == getLeft(parentNode))) {
-// node = getParent(node);
-// }
- if (node == this.root) {
+ }
+
+ // ascend until a parent node has left non-nil child not equal to the previous node
+ // this means the parent node's right child is this previous node.
+
+ while (true) {
+ if (node == this.root) { // if initial node is the root, can't go up.
return NIL;
}
- // node is now a left dtr, so we can go one up.
- node = getParent(node);
+ final int parentNode = getParent(node); // guaranteed parentNode not NIL because it's tested above and below
+ final int nextNode = getLeft(parentNode); // can be NIL
+ if (node != nextNode) {
+ return parentNode;
+ }
+ node = parentNode;
}
- return node;
- }
+ }
+
+ /**
+ * delete node z
+ * Step 1: locate a node to delete at the bottom of the tree. Bottom means left or right (or both) descendant is NIL.
+ *
+ * There are 2 cases: either the node to delete is z, or the node is the nextNode.
+ * If z has one or both descendants NIL, then it's the one to delete.
+ * Otherwise, the next node which is found by descending right then left until reaching the bottom (left = 0) node.
+ *
+ * y is node to remove from the tree.
+ *
+ * x is the non-NIL descendant of y (if one exists). It will be reparented to y's parent, and y's parent's left or right
+ * will point to it, skipping over y.
+ *
+ * @param z node to be removed, logically
+ */
protected void deleteNode(final int z) {
+ // y is the node to remove from the tree; is the input node, or the next node.
+
final int y = ((getLeft(z) == NIL) || (getRight(z) == NIL)) ? z : nextNode(z);
-// if ((getLeft(z) == NIL) || (getRight(z) == NIL)) {
-// y = z;
-// } else {
-// y = nextNode(z);
-// }
- final int left_y = getLeft(y);
+
+ if (y == this.greatestNode) {
+ if (y == z) {
+ this.greatestNode = previousNode(z);
+ } else {
+ this.greatestNode = z;
+ }
+ }
+
+ final int left_y = getLeft(y); // will be NIL if y is nextNode(z)
+
+ // x is the descendant of y (or NIL) that needs reparenting to the parent of y
+ // and also serves as the initializing value for rebalancing
final int x = (left_y != NIL) ? left_y : getRight(y);
-// if (left_y != NIL) {
-// x = left_y;
-// } else {
-// x = getRight(y);
-// }
+
final int parent_y = getParent(y);
- setParent(x, parent_y);
+
+ // if x is NIL, we still may pass it to the red-black rebalancer; so set it's "parent" value in any case.
+ setParent(x, parent_y); // "splice out" y by pointing parent link of x to parent of y
+
if (parent_y == NIL) {
setAsRoot(x);
} else {
if (y == getLeft(parent_y)) {
- setLeft(parent_y, x);
+ setLeft(parent_y, x); // splice out y
} else {
- setRight(parent_y, x);
+ setRight(parent_y, x); // splice out y
}
}
+
if (y != z) {
setKey(z, getKey(y));
}
@@ -696,6 +687,9 @@ public class IntArrayRBTcommon {
this.color[x] = black;
}
+ protected int compare(int v1, int v2) {
+ return (v1 < v2) ? -1 : ((v1 > v2) ? 1 : 0);
+ }
// ///////////////////////////////////////////////////////////////////////////
// Debug utilities
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/UnambiguousIteratorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/UnambiguousIteratorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/UnambiguousIteratorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/UnambiguousIteratorTest.java Tue May 5 03:31:59 2015
@@ -109,6 +109,10 @@ public class UnambiguousIteratorTest ext
assertEquals(annotSizeU1, annotSizeU2);
assertTrue(annotSizeA2 > annotSizeU2);
assertEquals(annotSizeA2, annotSizeU2 * 2);
+
+ annotIdx = llc.ll_getIndexRepository().ll_getIndex(CAS.STD_ANNOTATION_INDEX, ((TypeImpl)(cas.getAnnotationType())).getCode());
+ iteratorSize(annotIdx.ll_iterator());
+ iteratorSize(annotIdx.ll_iterator(false));
} catch (Exception ex) {
JUnitExtension.handleException(ex);
}
@@ -120,6 +124,7 @@ public class UnambiguousIteratorTest ext
for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
++size;
}
+ assertEquals(size, it.ll_indexSize());
return size;
}
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/AnnotationIteratorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/AnnotationIteratorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/AnnotationIteratorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/AnnotationIteratorTest.java Tue May 5 03:31:59 2015
@@ -19,6 +19,9 @@
package org.apache.uima.cas.test;
+import java.util.ArrayList;
+import java.util.List;
+
import junit.framework.TestCase;
import org.apache.uima.cas.CAS;
@@ -27,6 +30,8 @@ import org.apache.uima.cas.FSIterator;
import org.apache.uima.cas.Feature;
import org.apache.uima.cas.Type;
import org.apache.uima.cas.TypeSystem;
+import org.apache.uima.cas.impl.FSIndexFlat;
+import org.apache.uima.cas.impl.FSIteratorWrapper;
import org.apache.uima.cas.text.AnnotationFS;
import org.apache.uima.cas.text.AnnotationIndex;
@@ -144,9 +149,12 @@ public class AnnotationIteratorTest exte
try {
this.cas.setDocumentText(text);
} catch (CASRuntimeException e) {
- assertTrue(false);
+ fail();
}
+ /***************************************************
+ * Create and index tokens an sentences
+ ***************************************************/
int annotCount = 1; // Init with document annotation.
// create token and sentence annotations
for (int i = 0; i < text.length() - 5; i++) {
@@ -161,23 +169,40 @@ public class AnnotationIteratorTest exte
this.cas.getIndexRepository().addFS(this.cas.createAnnotation(this.sentenceType, i, i + 10));
}
+ /***************************************************
+ * iterate over them
+ ***************************************************/
+ List fss = new ArrayList();
+ iterateOverAnnotations(annotCount, fss);
+
+ iterateOverAnnotations(annotCount, fss); // should be using flattened version
+ }
+
+ private void iterateOverAnnotations(int annotCount, List fss) {
+ boolean isSave = fss.size() == 0;
int count;
AnnotationIndex<AnnotationFS> annotIndex = this.cas.getAnnotationIndex();
FSIterator<AnnotationFS> it = annotIndex.iterator(true);
+ assertTrue((isSave) ? it instanceof FSIteratorWrapper : it instanceof FSIndexFlat.FSIteratorFlat);
count = 0;
while (it.isValid()) {
++count;
- it.moveToNext();
+ AnnotationFS fs = it.next();
+ if (isSave) {
+ fss.add(fs);
+ } else {
+ assertEquals(fss.get(count -1).hashCode(), fs.hashCode());
+ }
}
- assertTrue(annotCount == count);
+ assertEquals(annotCount, count);
// System.out.println("Size of ambiguous iterator: " + count);
- it = annotIndex.iterator(false);
+ it = annotIndex.iterator(false); // false means create an unambiguous iterator
count = 0;
while (it.isValid()) {
++count;
it.moveToNext();
}
- assertTrue(count == 1);
+ assertEquals(1, count); // because of document Annotation
// System.out.println("Size of unambiguous iterator: " + count);
AnnotationFS bigAnnot = this.cas.createAnnotation(this.sentenceType, 10, 41);
it = annotIndex.subiterator(bigAnnot, true, true);
@@ -188,12 +213,12 @@ public class AnnotationIteratorTest exte
// System.out.println("Annotation from " + a.getBegin() + " to " + a.getEnd());
it.moveToNext();
}
- assertTrue(count == 32);
+ assertEquals(32, count);
count = 0;
for (it.moveToLast(); it.isValid(); it.moveToPrevious()) {
++count;
}
- assertTrue(count == 32);
+ assertEquals(32, count);
// System.out.println("Size of subiterator(true, true): " + count);
it = annotIndex.subiterator(bigAnnot, false, true);
count = 0;
@@ -203,13 +228,13 @@ public class AnnotationIteratorTest exte
// System.out.println("Annotation from " + a.getBegin() + " to " + a.getEnd());
it.moveToNext();
}
- assertTrue(count == 3);
+ assertEquals(3, count);
// System.out.println("Size of subiterator(false, true): " + count);
count = 0;
for (it.moveToLast(); it.isValid(); it.moveToPrevious()) {
++count;
}
- assertTrue(count == 3);
+ assertEquals(3, count);
it = annotIndex.subiterator(bigAnnot, true, false);
count = 0;
while (it.isValid()) {
@@ -218,13 +243,13 @@ public class AnnotationIteratorTest exte
// System.out.println("Annotation from " + a.getBegin() + " to " + a.getEnd());
it.moveToNext();
}
- assertTrue(count == 39);
+ assertEquals(39, count);
// System.out.println("Size of subiterator(true, false): " + count);
count = 0;
for (it.moveToLast(); it.isValid(); it.moveToPrevious()) {
++count;
}
- assertTrue(count == 39);
+ assertEquals(39, count);
it = annotIndex.subiterator(bigAnnot, false, false);
count = 0;
while (it.isValid()) {
@@ -233,13 +258,13 @@ public class AnnotationIteratorTest exte
// System.out.println("Annotation from " + a.getBegin() + " to " + a.getEnd());
it.moveToNext();
}
- assertTrue(count == 4);
+ assertEquals(4, count);
// System.out.println("Size of subiterator(false, false): " + count);
count = 0;
for (it.moveToLast(); it.isValid(); it.moveToPrevious()) {
++count;
}
- assertTrue(count == 4);
+ assertEquals(4, count);
AnnotationFS sent = this.cas.getAnnotationIndex(this.sentenceType).iterator().get();
it = annotIndex.subiterator(sent, false, true);
count = 0;
@@ -249,13 +274,14 @@ public class AnnotationIteratorTest exte
// System.out.println("Annotation from " + a.getBegin() + " to " + a.getEnd());
it.moveToNext();
}
- assertTrue(count == 2);
+ assertEquals(2, count);
// System.out.println("Size of subiterator(false, false): " + count);
count = 0;
for (it.moveToLast(); it.isValid(); it.moveToPrevious()) {
++count;
}
- assertTrue(count == 2);
+ assertEquals(2, count);
+
}
public void testIncorrectIndexTypeException() {
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/FilteredIteratorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/FilteredIteratorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/FilteredIteratorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/FilteredIteratorTest.java Tue May 5 03:31:59 2015
@@ -36,6 +36,8 @@ import org.apache.uima.cas.FeaturePath;
import org.apache.uima.cas.FeatureStructure;
import org.apache.uima.cas.Type;
import org.apache.uima.cas.TypeSystem;
+import org.apache.uima.cas.impl.FSIndexFlat;
+import org.apache.uima.cas.impl.FSIteratorWrapper;
import org.apache.uima.cas.text.AnnotationFS;
/**
@@ -165,13 +167,22 @@ public class FilteredIteratorTest extend
cas.getIndexRepository().addFS(cas.createAnnotation(tokenType, 14, 15));
cas.getIndexRepository().addFS(cas.createAnnotation(sentenceType, 0, 15));
+ iterAndCount1(false);
+
+ expandBeyondFlatThreshold(6); // enables flat iterator
+ iterAndCount1(true);
+
+ }
+
+ private void iterAndCount1(boolean isFlat) {
// create filtered iterator over Tokens only
- FSIterator<AnnotationFS> it = cas.getAnnotationIndex().iterator();
+ FSIterator<AnnotationFS> it = cas.getAnnotationIndex().iterator(); // always non-flat because just did index update
+
FSTypeConstraint constraint = cas.getConstraintFactory().createTypeConstraint();
constraint.add(tokenType);
it = cas.createFilteredIterator(it, constraint);
-
+
// do iteration
while (it.isValid()) {
AnnotationFS a = it.get();
@@ -182,7 +193,8 @@ public class FilteredIteratorTest extend
}
// Count number of annotations.
- it = cas.getAnnotationIndex().iterator();
+ it = cas.getAnnotationIndex().iterator();
+ assertTrue( (isFlat) ? (it instanceof FSIndexFlat.FSIteratorFlat) : it instanceof FSIteratorWrapper);
int countAll = 0;
for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
++countAll;
@@ -228,6 +240,13 @@ public class FilteredIteratorTest extend
cas.getIndexRepository().addFS(cas.createAnnotation(tokenType, 14, 15));
cas.getIndexRepository().addFS(cas.createAnnotation(sentenceType, 0, 15));
+ iterAndCount1a();
+
+ expandBeyondFlatThreshold(6); // enables flat iterator
+ iterAndCount1a();
+ }
+
+ private void iterAndCount1a() {
// create filtered iterator over Tokens only
FSIterator<AnnotationFS> it = cas.getAnnotationIndex().iterator();
FSTypeConstraint constraint = cas.getConstraintFactory().createTypeConstraint();
@@ -242,6 +261,7 @@ public class FilteredIteratorTest extend
// System.out.println("Covered text: " + a.getCoveredText());
it.moveToNext();
}
+
}
// test uses constraint compiler
@@ -306,51 +326,58 @@ public class FilteredIteratorTest extend
token.setStringValue(lemmaFeat, type1);
cas.getIndexRepository().addFS(token);
- String lemma = "the";
- // create filtered iterator over Tokens of type 1
- FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
- FSStringConstraint type1Constraint = cas.getConstraintFactory().createStringConstraint();
- type1Constraint.equals(lemma);
- FeaturePath path = cas.createFeaturePath();
- path.addFeature(lemmaFeat);
- FSMatchConstraint cons = cas.getConstraintFactory().embedConstraint(path, type1Constraint);
- it = cas.createFilteredIterator(it, cons);
-
- int count = 0;
- for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
- ++count;
- }
+ iterAndCount2();
+
+ expandBeyondFlatThreshold(6); // enables flat iterator
+ iterAndCount2();
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ fail();
+ }
+ }
- // /////////////////////////////////////////////////////////////
- // Count instances of tokens with lemma "the".
+ private void iterAndCount2() {
+ String lemma = "the";
+ // create filtered iterator over Tokens of type 1
+ FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
+ FSStringConstraint type1Constraint = cas.getConstraintFactory().createStringConstraint();
+ type1Constraint.equals(lemma);
+ FeaturePath path = cas.createFeaturePath();
+ path.addFeature(lemmaFeat);
+ FSMatchConstraint cons = cas.getConstraintFactory().embedConstraint(path, type1Constraint);
+ it = cas.createFilteredIterator(it, cons);
- // Create an iterator over Token annotations.
- FSIndex<AnnotationFS> tokenIndex = cas.getAnnotationIndex(tokenType);
- FSIterator<AnnotationFS> tokenIt = tokenIndex.iterator();
- // Create a counter.
- int theCount = 0;
- // Iterate over the tokens.
- for (tokenIt.moveToFirst(); tokenIt.isValid(); tokenIt.moveToNext()) {
- AnnotationFS tok = tokenIt.get();
- if (tok.getStringValue(lemmaFeat).equals(lemma)) {
- ++theCount;
- // System.out.println("Found token: " + tok.getCoveredText());
- }
- }
- assertTrue(count == theCount);
- // System.out.println(
- // "Number of tokens with \"" + lemma + "\": " + theCount);
- // System.out.println("Number of tokens overall: " + tokenIndex.size());
+ int count = 0;
+ for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
+ ++count;
+ }
- // System.out.println("Count: " + count);
- // assertTrue(count == 4);
+ // /////////////////////////////////////////////////////////////
+ // Count instances of tokens with lemma "the".
- } catch (Exception e) {
- e.printStackTrace();
- assertTrue(false);
+ // Create an iterator over Token annotations.
+ FSIndex<AnnotationFS> tokenIndex = cas.getAnnotationIndex(tokenType);
+ FSIterator<AnnotationFS> tokenIt = tokenIndex.iterator();
+ // Create a counter.
+ int theCount = 0;
+ // Iterate over the tokens.
+ for (tokenIt.moveToFirst(); tokenIt.isValid(); tokenIt.moveToNext()) {
+ AnnotationFS tok = tokenIt.get();
+ if (tok.getStringValue(lemmaFeat).equals(lemma)) {
+ ++theCount;
+ // System.out.println("Found token: " + tok.getCoveredText());
+ }
}
- }
+ assertTrue(count == theCount);
+ // System.out.println(
+ // "Number of tokens with \"" + lemma + "\": " + theCount);
+ // System.out.println("Number of tokens overall: " + tokenIndex.size());
+ // System.out.println("Count: " + count);
+ // assertTrue(count == 4);
+ }
+
public void testIterator2a() {
try {
cas.setDocumentText("This is a test with the word \"the\" in it.");
@@ -378,48 +405,56 @@ public class FilteredIteratorTest extend
token.setStringValue(lemmaFeat, type1);
cas.getIndexRepository().addFS(token);
- String lemma = "the";
- FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
- FSStringConstraint type1Constraint = cas.getConstraintFactory().createStringConstraint();
- type1Constraint.equals(lemma);
- ArrayList<String> path = new ArrayList<String>();
- path.add(lemmaFeat.getShortName());
- FSMatchConstraint cons = cas.getConstraintFactory().embedConstraint(path, type1Constraint);
- it = cas.createFilteredIterator(it, cons);
-
- int count = 0;
- for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
- ++count;
- }
+ iterAndCount2a();
+
+ expandBeyondFlatThreshold(6); // enables flat iterator
+ iterAndCount2a();
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ assertTrue(false);
+ }
+ }
+
+ private void iterAndCount2a() {
+ String lemma = "the";
+ FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
+ FSStringConstraint type1Constraint = cas.getConstraintFactory().createStringConstraint();
+ type1Constraint.equals(lemma);
+ ArrayList<String> path = new ArrayList<String>();
+ path.add(lemmaFeat.getShortName());
+ FSMatchConstraint cons = cas.getConstraintFactory().embedConstraint(path, type1Constraint);
+ it = cas.createFilteredIterator(it, cons);
- // /////////////////////////////////////////////////////////////
- // Count instances of tokens with lemma "the".
+ int count = 0;
+ for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
+ ++count;
+ }
- // Create an iterator over Token annotations.
- FSIndex<AnnotationFS> tokenIndex = cas.getAnnotationIndex(tokenType);
- FSIterator<AnnotationFS> tokenIt = tokenIndex.iterator();
- // Create a counter.
- int theCount = 0;
- // Iterate over the tokens.
- for (tokenIt.moveToFirst(); tokenIt.isValid(); tokenIt.moveToNext()) {
- AnnotationFS tok = tokenIt.get();
- if (tok.getStringValue(lemmaFeat).equals(lemma)) {
- ++theCount;
- // System.out.println("Found token: " + tok.getCoveredText());
- }
+ // /////////////////////////////////////////////////////////////
+ // Count instances of tokens with lemma "the".
+
+ // Create an iterator over Token annotations.
+ FSIndex<AnnotationFS> tokenIndex = cas.getAnnotationIndex(tokenType);
+ FSIterator<AnnotationFS> tokenIt = tokenIndex.iterator();
+ // Create a counter.
+ int theCount = 0;
+ // Iterate over the tokens.
+ for (tokenIt.moveToFirst(); tokenIt.isValid(); tokenIt.moveToNext()) {
+ AnnotationFS tok = tokenIt.get();
+ if (tok.getStringValue(lemmaFeat).equals(lemma)) {
+ ++theCount;
+ // System.out.println("Found token: " + tok.getCoveredText());
}
- assertTrue(count == theCount);
- // System.out.println(
- // "Number of tokens with \"" + lemma + "\": " + theCount);
- // System.out.println("Number of tokens overall: " + tokenIndex.size());
+ }
+ assertTrue(count == theCount);
+ // System.out.println(
+ // "Number of tokens with \"" + lemma + "\": " + theCount);
+ // System.out.println("Number of tokens overall: " + tokenIndex.size());
- // System.out.println("Count: " + count);
- // assertTrue(count == 4);
+ // System.out.println("Count: " + count);
+ // assertTrue(count == 4);
- } catch (Exception e) {
- e.printStackTrace();
- assertTrue(false);
- }
}
public void testIterator2b() {
@@ -459,27 +494,35 @@ public class FilteredIteratorTest extend
token.setFeatureValue(tokenTypeFeat, eosFS);
cas.getIndexRepository().addFS(token);
- FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
-
- ConstraintFactory cf = this.cas.getConstraintFactory();
- FSTypeConstraint tc = cf.createTypeConstraint();
- tc.add(sepType);
- tc.add(eosType.getName());
- ArrayList<String> path = new ArrayList<String>();
- path.add(tokenTypeFeat.getShortName());
- FSMatchConstraint cons = cf.embedConstraint(path, tc);
- it = this.cas.createFilteredIterator(it, cons);
- int count = 0;
- for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
- ++count;
- }
- assertTrue(count == 4);
-
+ iterAndCount2b();
+
+ expandBeyondFlatThreshold(6); // enables flat iterator
+ iterAndCount2b();
+
} catch (Exception e) {
e.printStackTrace();
assertTrue(false);
}
}
+
+ private void iterAndCount2b() {
+ FSIterator<AnnotationFS> it = cas.getAnnotationIndex(tokenType).iterator();
+
+ ConstraintFactory cf = this.cas.getConstraintFactory();
+ FSTypeConstraint tc = cf.createTypeConstraint();
+ tc.add(sepType);
+ tc.add(eosType.getName());
+ ArrayList<String> path = new ArrayList<String>();
+ path.add(tokenTypeFeat.getShortName());
+ FSMatchConstraint cons = cf.embedConstraint(path, tc);
+ it = this.cas.createFilteredIterator(it, cons);
+ int count = 0;
+ for (it.moveToFirst(); it.isValid(); it.moveToNext()) {
+ ++count;
+ }
+ assertTrue(count == 4);
+
+ }
// test uses constraint compiler
/*
@@ -516,5 +559,17 @@ public class FilteredIteratorTest extend
* public static void main(String[] args) { FilteredIteratorTest test = new
* FilteredIteratorTest(null); test.run(); }
*/
-
+
+ // add enough tokens to make the total be > THRESHOLD_FOR_FLATTENING, ii is the current number...
+ // this is so that the flattening can happen
+ private void expandBeyondFlatThreshold(int ii) {
+ int t = FSIndexFlat.THRESHOLD_FOR_FLATTENING;
+ FeatureStructure wordFS = this.cas.createFS(wordType);
+ for (int i = 0; i < t - ii; i++) {
+ AnnotationFS token = cas.createAnnotation(tokenType, 99, 99);
+ token.setStringValue(lemmaFeat, "dummytype"); // stuff to make the filter not throw null pointer exceptions
+ token.setFeatureValue(tokenTypeFeat, wordFS);
+ cas.getIndexRepository().addFS(token);
+ }
+ }
}
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IndexComparitorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IndexComparitorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IndexComparitorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IndexComparitorTest.java Tue May 5 03:31:59 2015
@@ -19,8 +19,6 @@
package org.apache.uima.cas.test;
-import java.util.Iterator;
-
import junit.framework.TestCase;
import org.apache.uima.cas.CAS;
@@ -332,10 +330,12 @@ public class IndexComparitorTest extends
ir.addFS(createFs(type1Sub1, 1, 1));
FeatureStructure testprobe = createFs(type1Sub1, 1, 1); // not in index, used only for key values
- assertFalse(sortedType1.contains(testprobe));
+ https://issues.apache.org/jira/browse/UIMA-4352
+ assertTrue(sortedType1.contains(testprobe));
assertTrue(sortedType1Sub1.contains(testprobe));
+
FeatureStructure testProbeSuper = createFs(type1, 1, 1);
assertTrue(sortedType1Sub1.contains(testProbeSuper));
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IteratorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IteratorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IteratorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/IteratorTest.java Tue May 5 03:31:59 2015
@@ -22,6 +22,7 @@ package org.apache.uima.cas.test;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
@@ -42,6 +43,11 @@ import org.apache.uima.cas.FeatureStruct
import org.apache.uima.cas.Type;
import org.apache.uima.cas.TypeSystem;
import org.apache.uima.cas.impl.CASImpl;
+import org.apache.uima.cas.impl.FeatureStructureImpl;
+import org.apache.uima.cas.impl.LowLevelIndex;
+import org.apache.uima.cas.impl.LowLevelIndexRepository;
+import org.apache.uima.cas.impl.LowLevelIterator;
+import org.apache.uima.cas.impl.TypeImpl;
import org.apache.uima.cas.text.AnnotationFS;
import org.apache.uima.internal.util.IntVector;
import org.apache.uima.jcas.JCas;
@@ -350,16 +356,27 @@ public class IteratorTest extends TestCa
private void createFSs(int i) {
+ FeatureStructureImpl fsi;
this.cas.getIndexRepository().addFS(
this.cas.createAnnotation(this.annotationType, i * 2, (i * 2) + 1));
this.cas.getIndexRepository().addFS(
this.cas.createAnnotation(this.sentenceType, i * 2, (i * 2) + 1));
this.cas.getIndexRepository().addFS(
- this.cas.createAnnotation(this.tokenType, i * 2, (i * 2) + 1));
+ fsi = (FeatureStructureImpl) this.cas.createAnnotation(this.tokenType, i * 2, (i * 2) + 1));
this.cas.getIndexRepository().addFS(
this.cas.createAnnotation(this.tokenType, i * 2, (i * 2) + 1));
this.cas.getIndexRepository().addFS(
this.cas.createAnnotation(this.tokenType, i * 2, (i * 2) + 1));
+ //debug
+ System.out.format("Token at %,d %n", fsi.getAddress());
+ }
+
+ private void debugls() {
+ LowLevelIndexRepository llir = this.cas.ll_getIndexRepository();
+ LowLevelIndex setIndexForType = llir.ll_getIndex(CASTestSetup.ANNOT_SET_INDEX, ((TypeImpl)tokenType).getCode());
+ LowLevelIterator it = setIndexForType.ll_iterator();
+ it.moveToLast();
+ System.out.format("Last token in set index is %,d%n", it.ll_get());
}
private void setupFSs() {
@@ -445,13 +462,18 @@ public class IteratorTest extends TestCa
findTst(bagIndex, jcasBagIndex);
findTst(ssBagIndex, jcasSsBagIndex);
+ debugls(); //debug
+
basicRemoveAdd(bagIndex, 20, 21);
basicRemoveAdd(ssBagIndex, 20, 21);
basicRemoveAdd(sortedIndex, 38, 39);
+ debugls(); //debug
basicRemoveAdd(ssSortedIndex, 38, 39);
basicRemoveAdd(setIndex, 38, 39);
basicRemoveAdd(ssSetIndex, 38, 39);
+
+
// /////////////////////////////////////////////////////////////////////////
// Test fast fail.
@@ -464,6 +486,8 @@ public class IteratorTest extends TestCa
fastFailTst(sortedIndex, true);
fastFailTst(ssSortedIndex, false);
+ debugls(); //debug
+
// Test find()
@@ -471,7 +495,52 @@ public class IteratorTest extends TestCa
tstWord(wordSetIndex);
tstWord(ssWordSetIndex);
+
+ debugls(); //debug
+
+ // moved IntArrayRBTtest for pointer iterators here
+ LowLevelIndexRepository llir = this.cas.ll_getIndexRepository();
+ LowLevelIndex setIndexForType = llir.ll_getIndex(CASTestSetup.ANNOT_SET_INDEX, ((TypeImpl)tokenType).getCode());
+ int[] expected = {17, 53, 89, 125, 161, 197, 233, 269, 305, 341, 701, 665, 629, 593, 557, 521, 485, 449, 413, 377};
+ setIndexIterchk(setIndexForType, expected);
+
+ setIndexForType = llir.ll_getIndex(CASTestSetup.ANNOT_SET_INDEX, ((TypeImpl)sentenceType).getCode());
+ expected = new int[] {12, 48, 84, 120, 156, 192, 228, 264, 300, 336, 696, 660, 624, 588, 552, 516, 480, 444, 408, 372};
+ setIndexIterchk(setIndexForType, expected);
+
+ setIndexForType = llir.ll_getIndex(CASTestSetup.ANNOT_SET_INDEX);
+ expected = new int[] {
+ 1, 44, 80, 116, 152, 188, 224, 260, 296, 332, 692, 656, 620, 584, 548, 512, 476, 440, 404, 368,
+ 12, 48, 84, 120, 156, 192, 228, 264, 300, 336, 696, 660, 624, 588, 552, 516, 480, 444, 408, 372,
+ 17, 53, 89, 125, 161, 197, 233, 269, 305, 341, 701, 665, 629, 593, 557, 521, 485, 449, 413, 377};
+ setIndexIterchk(setIndexForType, expected);
+
+ setIndexForType = llir.ll_getIndex(CASTestSetup.ANNOT_SET_INDEX, ((TypeImpl)tokenType).getCode());
+ LowLevelIterator it = setIndexForType.ll_iterator();
+ assertTrue(it.isValid());
+ it.moveToPrevious();
+ assertFalse(it.isValid());
+ it.moveToNext();
+ assertFalse(it.isValid());
+ it.moveToLast();
+ assertTrue(it.isValid());
+ it.moveToNext();
+ assertFalse(it.isValid());
+ it.moveToPrevious();
+ assertFalse(it.isValid());
+ }
+
+ private void setIndexIterchk(LowLevelIndex idx, int[] expected) {
+ LowLevelIterator it = idx.ll_iterator();
+ int[] r = new int[70];
+ int i = 0;
+ while (it.isValid()) {
+ r[i++] = it.ll_get();
+ it.moveToNext();
+ }
+ // r 17, 53, 89, 125, 161, 197, 233, 269, 305, 341, 719, 665, 629, 593, 557, 521, 485, 449, 413, 395
+ assertTrue(Arrays.equals(Arrays.copyOfRange(r, 0, expected.length), expected));
}
private void setIteratorWithoutMods(FSIndex<FeatureStructure> setIndex, int threadNumber) {
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/SubiteratorTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/SubiteratorTest.java?rev=1677731&r1=1677730&r2=1677731&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/SubiteratorTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/test/SubiteratorTest.java Tue May 5 03:31:59 2015
@@ -100,13 +100,10 @@ public class SubiteratorTest extends Tes
jcas.setDocumentText(text);
try {
this.ae.process(jcas);
- AnnotationIndex<Annotation> tokenIndex = jcas.getAnnotationIndex(jcas.getCasType(Token.type));
- Annotation sentence = jcas.getAnnotationIndex(jcas.getCasType(Sentence.type)).iterator().next();
- FSIterator<Annotation> tokenIterator = tokenIndex.subiterator(sentence);
- Annotation token = tokenIndex.iterator().next();
- tokenIterator.moveTo(token); //throws ClassCastException
- UnambiguousIteratorImpl<Annotation> it = new UnambiguousIteratorImpl<Annotation>(tokenIndex.iterator());
- it.moveTo(token);
+
+ iterateAndcheck(jcas);
+
+ iterateAndcheck(jcas);
} catch (AnalysisEngineProcessException e) {
e.printStackTrace();
assertTrue(false);
@@ -115,6 +112,16 @@ public class SubiteratorTest extends Tes
assertTrue(false);
}
}
+
+ private void iterateAndcheck(JCas jcas) {
+ AnnotationIndex<Token> tokenIndex = jcas.getAnnotationIndex(Token.class);
+ Annotation sentence = jcas.getAnnotationIndex(Sentence.class).iterator().next();
+ FSIterator<Token> tokenIterator = tokenIndex.subiterator(sentence);
+ Annotation token = tokenIndex.iterator().next();
+ tokenIterator.moveTo(token); //throws ClassCastException
+ UnambiguousIteratorImpl<Token> it = new UnambiguousIteratorImpl<Token>(tokenIndex.iterator());
+ it.moveTo(token);
+ }
public static void main(String[] args) {
junit.textui.TestRunner.run(SubiteratorTest.class);