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/01/07 21:32:27 UTC
svn commit: r1650148 - in /uima/uimaj/trunk/uimaj-core/src:
main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java
Author: schor
Date: Wed Jan 7 20:32:26 2015
New Revision: 1650148
URL: http://svn.apache.org/r1650148
Log:
[UIMA-4171] fix edge case for findInsertionPoint, add test case
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java?rev=1650148&r1=1650147&r2=1650148&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java Wed Jan 7 20:32:26 2015
@@ -486,12 +486,14 @@ public class IntArrayRBT extends IntArra
* @return the index of the node
*/
public int findInsertionPoint(final int k) {
+ boolean onlyWentRight = true;
int node = this.root;
int found = node;
while (node != NIL) {
found = node;
final int keyNode = getKey(node);
if (k < keyNode) {
+ onlyWentRight = false;
node = getLeft(node);
} else if (k == keyNode) {
// In the presence of duplicates, we have to check if there are
@@ -514,7 +516,7 @@ public class IntArrayRBT extends IntArra
}
}
// node == NIL
- return found;
+ return onlyWentRight ? NIL : found;
}
// private final boolean isLeftDtr(int node) {
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java?rev=1650148&r1=1650147&r2=1650148&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTtest.java Wed Jan 7 20:32:26 2015
@@ -28,6 +28,19 @@ import org.apache.uima.internal.util.Int
import org.apache.uima.internal.util.IntPointerIterator;
public class IntArrayRBTtest extends TestCase {
+
+ public void testFindInsertionPoint() {
+ IntArrayRBT ia = new IntArrayRBT();
+ Integer[] vs = new Integer[] {2, 2, 5, 1, 6, 7, 3, 4};
+ for (Integer i : vs) {
+ ia.insertKey(i);
+ }
+
+ assertTrue(ia.findInsertionPoint(7) != 0);
+ assertEquals(0, ia.findInsertionPoint(8));
+
+ }
+
public void testIterator() {
IntArrayRBT ia = new IntArrayRBT();
Integer[] vs = new Integer[] {2, 2, 5, 1, 6, 7, 3, 4};