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 2013/11/09 20:28:38 UTC
svn commit: r1540372 - in
/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees:
Int2IntRBT.java IntArrayRBT.java IntArrayRBTcommon.java
Author: schor
Date: Sat Nov 9 19:28:37 2013
New Revision: 1540372
URL: http://svn.apache.org/r1540372
Log:
[UIMA-3415] refactor out common parts into new superclass. Fix loic for growing to grow key/left/right/parent and other things independently. Still needs test case for very large sets/maps.
Added:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java?rev=1540372&r1=1540371&r2=1540372&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java Sat Nov 9 19:28:37 2013
@@ -21,10 +21,8 @@ package org.apache.uima.internal.util.rb
import java.util.NoSuchElementException;
-import org.apache.uima.internal.util.IntArrayUtils;
import org.apache.uima.internal.util.IntKeyValueIterator;
import org.apache.uima.internal.util.IntListIterator;
-import org.apache.uima.internal.util.StringUtils;
/**
* Int to Int Map, based on IntArrayRBT, used in no-duplicates mode
@@ -37,7 +35,7 @@ import org.apache.uima.internal.util.Str
* no values()
*
*/
-public class Int2IntRBT {
+public class Int2IntRBT extends IntArrayRBTcommon {
private class KeyValueIterator implements IntKeyValueIterator {
@@ -175,235 +173,32 @@ public class Int2IntRBT {
this.currentNode = NIL;
}
- private final int getKey(int node) {
- return Int2IntRBT.this.getKey(node);
- }
-
}
-
- static final private boolean useklrp = true;
- // Keys.
- private int[] key;
- // Left daughters.
- private int[] left;
-
- // Right daughters.
- private int[] right;
-
- // Parents.
- private int[] parent;
-
- // alternate layout
- private int[] klrp;
- // the next 3 are for the rare cases where the number of entries
- // in this instance exceeds 512 * 1024 * 1024 - 1
- // which is the largest index that can be stored in klrp
- // because it is shifted left by 2
- private int[] klrp1;
- private int[] klrp2;
- private int[] klrp3;
- private static final int MAXklrp0 = 512 * 1024 * 1024;
- private static final int MAXklrpMask = MAXklrp0 - 1;
-
-
- private int getXXX(int node, int offset) {
- if (node < MAXklrp0) {
- return klrp[(node << 2) + offset];
- } else {
- final int w = node >> 29;
- final int i = ((node & MAXklrpMask) << 2) + offset;
- switch (w) {
- case 1:
- return klrp1[i];
- case 2:
- return klrp2[i];
- case 3:
- return klrp3[i];
- default:
- throw new RuntimeException();
- }
- }
- }
-
- private 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;
- final int i = ((node & MAXklrpMask) << 2) + offset;
- switch (w) {
- case 1:
- return klrp1[i] = value;
- case 2:
- return klrp2[i] = value;
- case 3:
- return klrp3[i] = value;
- default:
- throw new RuntimeException();
- }
- }
- }
-
- /**
- * Given a node, get the key
- * @param node
- * @return the key
- */
- private int getKey(int node) {
- if (useklrp) {
- return getXXX(node, 0);
- }
- return key[node];
- }
+ private int[] values;
private int getValue(int node) {
return values[node];
}
- private int setKey(int node, int value) {
- if (useklrp) {
- return setXXX(node, 0, value);
- }
- return key[node] = value;
- }
-
- private void setValue(int node, int v) {
- values[node] = v;
- }
-
- private int getLeft(int node) {
- if (useklrp) {
- return getXXX(node, 1);
- }
- return left[node];
- }
-
- private int setLeft(int node, int value) {
- if (useklrp) {
- return setXXX(node, 1, value);
- }
- return left[node] = value;
- }
-
- private int getRight(int node) {
- if (useklrp) {
- return getXXX(node, 2);
- }
- return right[node];
- }
-
- private int setRight(int node, int value) {
- if (useklrp) {
- return setXXX(node, 2, value);
- }
- return right[node] = value;
- }
-
- private int getParent(int node) {
- if (useklrp) {
- return getXXX(node, 3);
- }
- return parent[node];
- }
-
- private int setParent(int node, int value) {
- if (useklrp) {
- return setXXX(node, 3, value);
- }
- return parent[node] = value;
- }
-
- private int[] values;
-
private int prevValue;
-
- // Colors.
- private boolean[] color;
-
- // The index of the next node.
- private int next;
-
- // The current size of the tree. Since we can remove nodes, since needs to
- // be kept separate from the next free cell.
- private int size;
-
- // The root of the tree.
- private int root;
-
+
private int lastNodeGotten; // a speed up, maybe
- // 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.
- private int greatestNode;
-
- private static final int default_size = 1024; // must be pwr of 2 for useklrp true
-
- private static final int default_growth_factor = 2; // must be pwr of 2 for useklrp true
-
- private static final int default_multiplication_limit = 1024 * 1024 * 2; // must be pwr of 2 for useklrp true
-
- final private int initialSize;
-
- final private int growth_factor; // must be pwr of 2 for useklrp true
-
- final private int multiplication_limit; // must be pwr of 2 for useklrp true
-
- // The NIL sentinel
- public static final int NIL = 0;
-
- // The colors.
- private static final boolean red = true;
-
- private static final boolean black = false;
-
/**
* Constructor for IntArrayRBT.
*/
public Int2IntRBT() {
- this(default_size);
+ super(default_size);
}
public Int2IntRBT(int initialSize) {
- super();
- if (initialSize < 1) {
- initialSize = 1;
- }
- initVars();
- // Increase initialSize by one since we use one slot for sentinel.
- ++initialSize;
- this.initialSize = nextPowerOf2(initialSize);
- this.growth_factor = default_growth_factor;
- this.multiplication_limit = default_multiplication_limit;
- setupArrays();
+ super(initialSize);
}
-
- private int nextPowerOf2(int v) {
- // v is >= 0
- int v2 = Integer.highestOneBit(v);
- return (v2 < v) ? (v2 << 1) : v2;
- }
-
- private 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];
- }
- this.color = new boolean[initialSize];
+
+ protected void setupArrays() {
+ super.setupArrays();
this.values = new int[initialSize];
- setLeft(NIL, NIL);
- setRight(NIL, NIL);
- setParent(NIL, NIL);
- this.color[NIL] = black;
}
public Int2IntRBT copy() {
@@ -428,106 +223,15 @@ public class Int2IntRBT {
return c;
}
- private void initVars() {
- this.root = NIL;
- this.greatestNode = NIL;
- this.next = 1;
- this.size = 0;
- }
-
public void clear() {
- // 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();
- }
- }
+ flush();
}
- public final int size() {
- return this.size;
- }
-
- private void grow(int requiredSize) {
- if (useklrp) {
-
- // the klrp design stacks 4 pointers together into the int array
- // When growing, the last array is grown by the needed amount.
- // Edge case: if the new required size jumps up by more than
- // about 2 million, the previous array might need to be
- // expanded too.
- // This could in a real edge case require all previous arrays
- // to be expanded.
-
- final int w = requiredSize >> 29; // w is 0-3
- final int requiredSizeForLastSegment = requiredSize - w * MAXklrp0;
- switch (w) {
- case 3: {
- if (klrp3 == null) {
- klrp3 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp3 = grow(klrp3, requiredSizeForLastSegment << 2);
- }
- maximize(klrp2);
- maximize(klrp1);
- maximize(klrp);
- }
- break;
- case 2: {
- if (klrp2 == null) {
- klrp2 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp2 = grow(klrp2, requiredSizeForLastSegment << 2);
- }
- maximize(klrp1);
- maximize(klrp);
- }
- break;
- case 1: {
- if (klrp1 == null) {
- klrp1 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp1 = grow(klrp1, requiredSizeForLastSegment << 2);
- }
- maximize(klrp);
- }
- break;
- case 0:
- if (klrp == null) {
- klrp = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp = grow(klrp, requiredSizeForLastSegment << 2);
- }
- break;
- default:
- throw new RuntimeException();
- }
- } else {
- this.key = grow(this.key, requiredSize);
- this.left = grow(this.left, requiredSize);
- this.right = grow(this.right, requiredSize);
- this.parent = grow(this.parent, requiredSize);
- }
- this.color = grow(this.color, requiredSize);
- this.values = grow(this.values, requiredSize);
+ protected void ensureCapacity(int requiredSize) {
+ super.ensureCapacity(requiredSize);
+ this.values = ensureArrayCapacity(this.values, requiredSize);
}
- // only called for krlp style
- private int[] maximize(int[] array) {
- if (array.length < MAXklrp0) {
- int[] a = new int[MAXklrp0];
- System.arraycopy(array, 0, a, 0, array.length);
- return a;
- }
- return array;
- }
-
/**
*
* @param k
@@ -537,7 +241,7 @@ public class Int2IntRBT {
if ((this.greatestNode != NIL) && (getKey(this.greatestNode) < k)) {
final int y = this.greatestNode;
final int z = newNode(k);
- values[z] = v;
+ values[z] = v; // addition
this.greatestNode = z;
setRight(y, z);
setParent(z, y);
@@ -550,8 +254,8 @@ public class Int2IntRBT {
final int xKey = getKey(x);
if (k == xKey) {
// key found
- prevValue = values[x];
- values[x] = v;
+ prevValue = values[x]; // addition
+ values[x] = v; // addition
return -x;
}
x = (k < xKey) ? getLeft(x) : getRight(x);
@@ -576,96 +280,6 @@ public class Int2IntRBT {
}
- private int newNode(final int k) {
- // Make sure the tree is big enough to accomodate a new node.
-
- if (useklrp) {
- final int lenKlrp = (klrp.length >> 2) +
- ((klrp1 != null) ? (klrp1.length >> 2) : 0) +
- ((klrp2 != null) ? (klrp2.length >> 2) : 0) +
- ((klrp3 != null) ? (klrp3.length >> 2) : 0);
- if (this.next >= lenKlrp) {
- grow(this.next + 1);
- }
- } else {
- if (this.next >= this.key.length) {
- grow(this.next + 1);
- }
- }
- // assert(key.length > next);
- final int z = this.next;
- ++this.next;
- ++this.size;
- setKey(z, k);
- setLeft(z, NIL);
- setRight(z, NIL);
- this.color[z] = red;
- return z;
- }
-
- private final void setAsRoot(int x) {
- this.root = x;
- setParent(this.root, NIL);
- }
-
- /**
- *
- * @param array - the array to expand - may be klrp0, 1, 2, 3, etc.
- * @param newSize = the total size - if in parts, the size of the part
- * @return expanded array
- */
- private final int[] grow(final int[] array, final int newSize) {
- return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
- }
-
- private final boolean[] grow(boolean[] array, int newSize) {
- return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
- }
-
- private final void leftRotate(final int x) {
- final int y = getRight(x);
- final int left_of_y = getLeft(y);
- setRight(x, left_of_y );
- if (left_of_y != NIL) {
- setParent(left_of_y , x);
- }
- setParent(y, getParent(x));
- if (this.root == x) {
- setAsRoot(y);
- } else {
- final int parent_x = getParent(x);
- if (x == getLeft(parent_x)) {
- setLeft(parent_x, y);
- } else {
- setRight(parent_x, y);
- }
- }
- setLeft(y, x);
- setParent(x, y);
- }
-
- private final void rightRotate(final int x) {
- final int y = getLeft(x);
- final int right_y = getRight(y);
- setLeft(x, right_y);
- if (right_y != NIL) {
- setParent(right_y, x);
- }
- final int parent_x = getParent(x);
- setParent(y, parent_x);
- if (this.root == x) {
- setAsRoot(y);
- } else {
- if (x == getRight(parent_x)) {
- setRight(parent_x, y);
- } else {
- setLeft(parent_x, y);
- }
- }
- setRight(y, x);
- setParent(x, y);
- }
-
/**
* Get the value for a given key
* @param k
@@ -821,29 +435,7 @@ public class Int2IntRBT {
}
return node;
}
-
- /**
- * Find the first node such that k <= key[node].
- */
- private int findKey(final int k) {
- return findKeyDown(k, this.root);
- }
-
- private 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) {
- return node;
- } else {
- node = getRight(node);
- }
- }
- // node == NIL
- return NIL;
- }
-
+
// /**
// * Find the node such that key[node] >= k and key[previous(node)] < k.
// */
@@ -878,31 +470,6 @@ public class Int2IntRBT {
// // node == NIL
// return found;
// }
-
- /**
- * Find the node such that key[node] >= k and key[previous(node)] < k.
- */
- private int findInsertionPointNoDups(final int k) {
- int node = this.root;
- int found = node;
- 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);
- }
- }
- // node == NIL
- return found;
- }
-
- public final boolean containsKey(int k) {
- return (findKey(k) != NIL);
- }
// private final boolean isLeftDtr(int node) {
// return ((node != this.root) && (node == getLeft(getParent(node))));
@@ -912,205 +479,6 @@ public class Int2IntRBT {
// return ((node != root) && (node == right[parent[node]]));
// }
- private final int getFirstNode() {
- if (this.root == NIL) {
- return NIL;
- }
- int node = this.root;
- while (true) {
- final int left_node = getLeft(node);
- if (left_node == NIL) {
- break;
- }
- 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;
- // }
-
- private final int nextNode(int node) {
- int y;
- final int rightNode = getRight(node);
- if (rightNode != NIL) {
- node = rightNode;
- while (true) {
- final int leftNode = getLeft(node);
- if (leftNode == NIL) {
- break;
- }
- node = leftNode;
- }
-// while (getLeft(node) != NIL) {
-// node = getLeft(node);
-// }
- } else {
- y = getParent(node);
- while ((y != NIL) && (node == getRight(y))) {
- node = y;
- y = getParent(y);
- }
- node = y;
- }
- return node;
- }
-
- private final int previousNode(int node) {
- final int leftNode = getLeft(node);
- if (leftNode != NIL) {
- node = leftNode;
- while (true) {
- final int rightNode = getRight(node);
- if (rightNode == NIL) {
- break;
- }
- 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) {
- return NIL;
- }
- // node is now a left dtr, so we can go one up.
- node = getParent(node);
- }
- return node;
- }
-
-// public boolean deleteKey(int aKey) {
-// final int node = findKey(aKey);
-// if (node == NIL) {
-// return false;
-// }
-// deleteNode(node);
-// --this.size;
-// return true;
-// }
-
- private void deleteNode(final int z) {
- 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);
- 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 (parent_y == NIL) {
- setAsRoot(x);
- } else {
- if (y == getLeft(parent_y)) {
- setLeft(parent_y, x);
- } else {
- setRight(parent_y, x);
- }
- }
- if (y != z) {
- setKey(z, y);
- }
- if (this.color[y] == black) {
- deleteFixup(x);
- }
- }
-
- private void deleteFixup(int x) {
- int w;
- while ((x != this.root) && (this.color[x] == black)) {
- final int parent_x = getParent(x);
- if (x == getLeft(parent_x)) {
- w = getRight(parent_x);
- if (this.color[w] == red) {
- this.color[w] = black;
- this.color[parent_x] = red;
- leftRotate(parent_x);
- w = getRight(parent_x);
- }
- if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
- this.color[w] = red;
- x = parent_x;
- } else {
- if (this.color[getRight(w)] == black) {
- this.color[getLeft(w)] = black;
- this.color[w] = red;
- rightRotate(w);
- w = getRight(parent_x);
- }
- this.color[w] = this.color[parent_x];
- this.color[parent_x] = black;
- this.color[getRight(w)] = black;
- leftRotate(parent_x);
- x = this.root;
- }
- } else {
- w = getLeft(parent_x);
- if (this.color[w] == red) {
- this.color[w] = black;
- this.color[parent_x] = red;
- rightRotate(parent_x);
- w = getLeft(parent_x);
- }
- if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
- this.color[w] = red;
- x = getParent(x);
- } else {
- if (this.color[getLeft(w)] == black) {
- this.color[getRight(w)] = black;
- this.color[w] = red;
- leftRotate(w);
- w = getLeft(getParent(x));
- }
- this.color[w] = this.color[parent_x];
- this.color[parent_x] = black;
- this.color[getLeft(w)] = black;
- rightRotate(parent_x);
- x = this.root;
- }
- }
- }
- this.color[x] = black;
- }
-
public IntListIterator keyIterator() {
return new KeyIterator();
}
@@ -1131,145 +499,4 @@ public class Int2IntRBT {
return it;
}
- // ///////////////////////////////////////////////////////////////////////////
- // Debug utilities
-
- private boolean satisfiesRedBlackProperties() {
- // Compute depth of black nodes.
- int node = this.root;
- int blackDepth = 0;
- while (node != NIL) {
- if (this.color[node] == black) {
- ++blackDepth;
- }
- node = getLeft(node);
- }
- return satisfiesRBProps(this.root, blackDepth, 0);
- }
-
- private boolean satisfiesRBProps(int node, final int blackDepth, int currentBlack) {
- if (node == NIL) {
- return (currentBlack == blackDepth);
- }
- if (this.color[node] == red) {
- if (this.color[getLeft(node)] == red || this.color[getRight(node)] == red) {
- return false;
- }
- } else {
- ++currentBlack;
- }
- return (satisfiesRBProps(getLeft(node), blackDepth, currentBlack) && satisfiesRBProps(
- getRight(node), blackDepth, currentBlack));
- }
-
- public int maxDepth() {
- return maxDepth(this.root, 0);
- }
-
- public int minDepth() {
- return minDepth(this.root, 0);
- }
-
- public int nodeDepth(int k) {
- return nodeDepth(this.root, 1, k);
- }
-
- private int nodeDepth(int node, int depth, int k) {
- if (node == NIL) {
- return -1;
- }
- if (k == getKey(node)) {
- return depth;
- } else if (k < getKey(node)) {
- return nodeDepth(getLeft(node), depth + 1, k);
- } else {
- return nodeDepth(getRight(node), depth + 1, k);
- }
- }
-
- private int maxDepth(int node, int depth) {
- if (node == NIL) {
- return depth;
- }
- int depth1 = maxDepth(getLeft(node), depth + 1);
- int depth2 = maxDepth(getRight(node), depth + 1);
- return (depth1 > depth2) ? depth1 : depth2;
- }
-
- private int minDepth(int node, int depth) {
- if (node == NIL) {
- return depth;
- }
- int depth1 = maxDepth(getLeft(node), depth + 1);
- int depth2 = maxDepth(getRight(node), depth + 1);
- return (depth1 > depth2) ? depth2 : depth1;
- }
-
- public final void printKeys() {
- if (this.size() == 0) {
- System.out.println("Tree is empty.");
- return;
- }
- StringBuffer buf = new StringBuffer();
- printKeys(this.root, 0, buf);
- System.out.println(buf);
- }
-
- private final void printKeys(int node, int offset, StringBuffer buf) {
- if (node == NIL) {
- // StringUtils.printSpaces(offset, buf);
- // buf.append("NIL\n");
- return;
- }
- StringUtils.printSpaces(offset, buf);
- buf.append(Integer.toString(getKey(node)));
- if (this.color[node] == black) {
- buf.append(" BLACK");
- }
- buf.append("\n");
- printKeys(getLeft(node), offset + 2, buf);
- printKeys(getRight(node), offset + 2, buf);
- }
-
- public static void main(String[] args) {
- System.out.println("Constructing tree.");
- Int2IntRBT tree = new Int2IntRBT();
- // assert(tree.color[0] == black);
- // assert(tree.size() == 0);
- // assert(tree.insertKey(5) == 1);
- // assert(tree.size() == 1);
- // assert(tree.insertKeyWithDups(5) == 2);
- // assert(tree.insertKey(3) == 3);
- // assert(tree.size() == 3);
- // assert(tree.insertKey(4) == 4);
- // assert(tree.size() == 4);
- // assert(tree.insertKey(2) == 5);
- // assert(tree.size() == 5);
- // tree.printKeys();
- // System.out.println("Constructing tree.");
- // tree = new IntArrayRBT();
- // int max = 10;
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(i);
- // }
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(i);
- // }
- // tree.printKeys();
- // tree = new IntArrayRBT();
- // max = 100;
- // // System.out.println("Creating tree.");
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(1);
- // }
- // // System.out.println("Printing tree.");
- // tree.printKeys();
- // // IntIterator it = tree.iterator();
- // // int numElements = 0;
- // // while (it.hasNext()) {
- // // it.next();
- // // ++numElements;
- // // }
- }
-
}
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=1540372&r1=1540371&r2=1540372&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 Sat Nov 9 19:28:37 2013
@@ -24,11 +24,9 @@ import java.util.Random;
import org.apache.uima.internal.util.ComparableIntIterator;
import org.apache.uima.internal.util.ComparableIntPointerIterator;
-import org.apache.uima.internal.util.IntArrayUtils;
import org.apache.uima.internal.util.IntComparator;
import org.apache.uima.internal.util.IntListIterator;
import org.apache.uima.internal.util.IntPointerIterator;
-import org.apache.uima.internal.util.StringUtils;
/**
* Red-black tree implementation based on integer arrays. Preliminary performance measurements on
@@ -42,7 +40,7 @@ import org.apache.uima.internal.util.Str
*
*
*/
-public class IntArrayRBT {
+public class IntArrayRBT extends IntArrayRBTcommon {
/**
* Implement a comparable iterator over the keys.
@@ -251,166 +249,8 @@ public class IntArrayRBT {
}
- static final private boolean useklrp = true;
- // Keys.
- private int[] key;
- // Left daughters.
- private int[] left;
-
- // Right daughters.
- private int[] right;
-
- // Parents.
- private int[] parent;
-
- // alternate layout
- private int[] klrp;
- // the next 3 are for the rare cases where the number of entries
- // in this instance exceeds 512 * 1024 * 1024 - 1
- // which is the largest index that can be stored in klrp
- // because it is shifted left by 2
- private int[] klrp1;
- private int[] klrp2;
- private int[] klrp3;
- private static final int MAXklrp0 = 512 * 1024 * 1024;
- private static final int MAXklrpMask = MAXklrp0 - 1;
-
-
- private int getXXX(int node, int offset) {
- if (node < MAXklrp0) {
- return klrp[(node << 2) + offset];
- } else {
- final int w = node >> 29;
- final int i = ((node & MAXklrpMask) << 2) + offset;
- switch (w) {
- case 1:
- return klrp1[i];
- case 2:
- return klrp2[i];
- case 3:
- return klrp3[i];
- default:
- throw new RuntimeException();
- }
- }
- }
-
- private 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;
- final int i = ((node & MAXklrpMask) << 2) + offset;
- switch (w) {
- case 1:
- return klrp1[i] = value;
- case 2:
- return klrp2[i] = value;
- case 3:
- return klrp3[i] = value;
- default:
- throw new RuntimeException();
- }
- }
- }
-
- protected int getKey(int node) {
- if (useklrp) {
- return getXXX(node, 0);
- }
- return key[node];
- }
-
- protected int setKey(int node, int value) {
- if (useklrp) {
- return setXXX(node, 0, value);
- }
- return key[node] = value;
- }
-
- protected int getLeft(int node) {
- if (useklrp) {
- return getXXX(node, 1);
- }
- return left[node];
- }
-
- protected int setLeft(int node, int value) {
- if (useklrp) {
- return setXXX(node, 1, value);
- }
- return left[node] = value;
- }
-
- protected int getRight(int node) {
- if (useklrp) {
- return getXXX(node, 2);
- }
- return right[node];
- }
-
- protected int setRight(int node, int value) {
- if (useklrp) {
- return setXXX(node, 2, value);
- }
- return right[node] = value;
- }
-
- protected int getParent(int node) {
- if (useklrp) {
- return getXXX(node, 3);
- }
- return parent[node];
- }
-
- protected int setParent(int node, int value) {
- if (useklrp) {
- return setXXX(node, 3, value);
- }
- return parent[node] = value;
- }
-
- // Colors.
- protected boolean[] color;
-
- // The index of the next node.
- private int next;
-
- // The current size of the tree. Since we can remove nodes, since needs to
- // be kept separate from the next free cell.
- private int size;
-
- // The root of the tree.
- protected int root;
-
- // 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;
-
- protected static final int default_size = 1024; // must be pwr of 2 for useklrp true
-
- private static final int default_growth_factor = 2; // must be pwr of 2 for useklrp true
-
- private static final int default_multiplication_limit = 1024 * 1024 * 2; // must be pwr of 2 for useklrp true
-
- final private int initialSize;
-
- final private int growth_factor; // must be pwr of 2 for useklrp true
-
- final private int multiplication_limit; // must be pwr of 2 for useklrp true
-
- // The NIL sentinel
- public static final int NIL = 0;
-
- // The colors.
- protected static final boolean red = true;
-
- protected static final boolean black = false;
+
// Random number generator to randomize inserts of identical keys.
protected final Random rand;
@@ -425,140 +265,8 @@ public class IntArrayRBT {
public IntArrayRBT(int initialSize) {
super();
this.rand = new Random();
- if (initialSize < 1) {
- initialSize = 1;
- }
- initVars();
- // Increase initialSize by one since we use one slot for sentinel.
- ++initialSize;
- this.initialSize = nextPowerOf2(initialSize);
- this.growth_factor = default_growth_factor;
- this.multiplication_limit = default_multiplication_limit;
- setupArrays();
- }
-
- private int nextPowerOf2(int v) {
- // v is >= 0
- int v2 = Integer.highestOneBit(v);
- return (v2 < v) ? (v2 << 1) : v2;
- }
-
- private 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];
- }
- this.color = new boolean[initialSize];
- setLeft(NIL, NIL);
- setRight(NIL, NIL);
- setParent(NIL, NIL);
- this.color[NIL] = black;
- }
-
- private void initVars() {
- this.root = NIL;
- this.greatestNode = NIL;
- this.next = 1;
- this.size = 0;
- }
-
- public void flush() {
- // 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();
- }
- }
}
-
- public final int size() {
- return this.size;
- }
-
- private void grow(int requiredSize) {
- if (useklrp) {
-
- // the klrp design stacks 4 pointers together into the int array
- // When growing, the last array is grown by the needed amount.
- // Edge case: if the new required size jumps up by more than
- // about 2 million, the previous array might need to be
- // expanded too.
- // This could in a real edge case require all previous arrays
- // to be expanded.
-
- final int w = requiredSize >> 29; // w is 0-3
- final int requiredSizeForLastSegment = requiredSize - w * MAXklrp0;
- switch (w) {
- case 3: {
- if (klrp3 == null) {
- klrp3 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp3 = grow(klrp3, requiredSizeForLastSegment << 2);
- }
- maximize(klrp2);
- maximize(klrp1);
- maximize(klrp);
- }
- break;
- case 2: {
- if (klrp2 == null) {
- klrp2 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp2 = grow(klrp2, requiredSizeForLastSegment << 2);
- }
- maximize(klrp1);
- maximize(klrp);
- }
- break;
- case 1: {
- if (klrp1 == null) {
- klrp1 = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp1 = grow(klrp1, requiredSizeForLastSegment << 2);
- }
- maximize(klrp);
- }
- break;
- case 0:
- if (klrp == null) {
- klrp = new int[requiredSizeForLastSegment << 2];
- } else {
- klrp = grow(klrp, requiredSizeForLastSegment << 2);
- }
- break;
- default:
- throw new RuntimeException();
- }
- } else {
- this.key = grow(this.key, requiredSize);
- this.left = grow(this.left, requiredSize);
- this.right = grow(this.right, requiredSize);
- this.parent = grow(this.parent, requiredSize);
- }
- this.color = grow(this.color, requiredSize);
- }
-
- // only called for krlp style
- private int[] maximize(int[] array) {
- if (array.length < MAXklrp0) {
- int[] a = new int[MAXklrp0];
- System.arraycopy(array, 0, a, 0, array.length);
- return a;
- }
- return array;
- }
-
+
public int getKeyForNode(final int node) {
return getKey(node);
}
@@ -642,91 +350,6 @@ public class IntArrayRBT {
return z;
}
- protected int newNode(final int k) {
- // Make sure the tree is big enough to accomodate a new node.
-
- if (useklrp) {
- final int lenKlrp = (klrp.length >> 2) +
- ((klrp1 != null) ? (klrp1.length >> 2) : 0) +
- ((klrp2 != null) ? (klrp2.length >> 2) : 0) +
- ((klrp3 != null) ? (klrp3.length >> 2) : 0);
- if (this.next >= lenKlrp) {
- grow(this.next + 1);
- }
- } else {
- if (this.next >= this.key.length) {
- grow(this.next + 1);
- }
- }
- // assert(key.length > next);
- final int z = this.next;
- ++this.next;
- ++this.size;
- setKey(z, k);
- setLeft(z, NIL);
- setRight(z, NIL);
- this.color[z] = red;
- return z;
- }
-
- private final void setAsRoot(int x) {
- this.root = x;
- setParent(this.root, NIL);
- }
-
- // grow an array to the new size
- private final int[] grow(int[] array, int newSize) {
- return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit * (useklrp ? 4 : 1));
- }
-
- private final boolean[] grow(boolean[] array, int newSize) {
- return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
- }
-
- private final void leftRotate(final int x) {
- final int y = getRight(x);
- final int left_of_y = getLeft(y);
- setRight(x, left_of_y );
- if (left_of_y != NIL) {
- setParent(left_of_y , x);
- }
- setParent(y, getParent(x));
- if (this.root == x) {
- setAsRoot(y);
- } else {
- final int parent_x = getParent(x);
- if (x == getLeft(parent_x)) {
- setLeft(parent_x, y);
- } else {
- setRight(parent_x, y);
- }
- }
- setLeft(y, x);
- setParent(x, y);
- }
-
- private final void rightRotate(final int x) {
- final int y = getLeft(x);
- final int right_y = getRight(y);
- setLeft(x, right_y);
- if (right_y != NIL) {
- setParent(right_y, x);
- }
- final int parent_x = getParent(x);
- setParent(y, parent_x);
- if (this.root == x) {
- setAsRoot(y);
- } else {
- if (x == getRight(parent_x)) {
- setRight(parent_x, y);
- } else {
- setLeft(parent_x, y);
- }
- }
- setRight(y, x);
- setParent(x, y);
- }
-
public int insertKey(int k) {
return insertKey(k, false);
}
@@ -881,35 +504,6 @@ public class IntArrayRBT {
return found;
}
- /**
- * Find the node such that key[node] >= k and key[previous(node)] < k.
- */
- public int findInsertionPointNoDups(final int k) {
- int node = this.root;
- int found = node;
- 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);
- }
- }
- // node == NIL
- return found;
- }
-
- public final boolean containsKey(int k) {
- return (findKey(k) != NIL);
- }
-
- public final boolean contains(int k) {
- return (findKey(k) != NIL);
- }
-
// private final boolean isLeftDtr(int node) {
// return ((node != this.root) && (node == getLeft(getParent(node))));
// }
@@ -918,105 +512,6 @@ public class IntArrayRBT {
// return ((node != root) && (node == right[parent[node]]));
// }
- private final int getFirstNode() {
- if (this.root == NIL) {
- return NIL;
- }
- int node = this.root;
- while (true) {
- final int left_node = getLeft(node);
- if (left_node == NIL) {
- break;
- }
- 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;
- final int rightNode = getRight(node);
- if (rightNode != NIL) {
- node = rightNode;
- while (true) {
- final int leftNode = getLeft(node);
- if (leftNode == NIL) {
- break;
- }
- node = leftNode;
- }
-// while (getLeft(node) != NIL) {
-// node = getLeft(node);
-// }
- } else {
- y = getParent(node);
- while ((y != NIL) && (node == getRight(y))) {
- node = y;
- y = getParent(y);
- }
- node = y;
- }
- return node;
- }
-
- private final int previousNode(int node) {
- final int leftNode = getLeft(node);
- if (leftNode != NIL) {
- node = leftNode;
- while (true) {
- final int rightNode = getRight(node);
- if (rightNode == NIL) {
- break;
- }
- 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) {
- return NIL;
- }
- // node is now a left dtr, so we can go one up.
- node = getParent(node);
- }
- return node;
- }
-
public boolean deleteKey(int aKey) {
final int node = findKey(aKey);
if (node == NIL) {
@@ -1030,95 +525,6 @@ public class IntArrayRBT {
return true;
}
- private void deleteNode(final int z) {
- 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);
- 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 (parent_y == NIL) {
- setAsRoot(x);
- } else {
- if (y == getLeft(parent_y)) {
- setLeft(parent_y, x);
- } else {
- setRight(parent_y, x);
- }
- }
- if (y != z) {
- setKey(z, getKey(y));
- }
- if (this.color[y] == black) {
- deleteFixup(x);
- }
- }
-
- private void deleteFixup(int x) {
- int w;
- while ((x != this.root) && (this.color[x] == black)) {
- final int parent_x = getParent(x);
- if (x == getLeft(parent_x)) {
- w = getRight(parent_x);
- if (this.color[w] == red) {
- this.color[w] = black;
- this.color[parent_x] = red;
- leftRotate(parent_x);
- w = getRight(parent_x);
- }
- if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
- this.color[w] = red;
- x = parent_x;
- } else {
- if (this.color[getRight(w)] == black) {
- this.color[getLeft(w)] = black;
- this.color[w] = red;
- rightRotate(w);
- w = getRight(parent_x);
- }
- this.color[w] = this.color[parent_x];
- this.color[parent_x] = black;
- this.color[getRight(w)] = black;
- leftRotate(parent_x);
- x = this.root;
- }
- } else {
- w = getLeft(parent_x);
- if (this.color[w] == red) {
- this.color[w] = black;
- this.color[parent_x] = red;
- rightRotate(parent_x);
- w = getLeft(parent_x);
- }
- if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
- this.color[w] = red;
- x = getParent(x);
- } else {
- if (this.color[getLeft(w)] == black) {
- this.color[getRight(w)] = black;
- this.color[w] = red;
- leftRotate(w);
- w = getLeft(getParent(x));
- }
- this.color[w] = this.color[parent_x];
- this.color[parent_x] = black;
- this.color[getLeft(w)] = black;
- rightRotate(parent_x);
- x = this.root;
- }
- }
- }
- this.color[x] = black;
- }
/**
* Method iterator.
@@ -1153,147 +559,6 @@ public class IntArrayRBT {
return cpi;
}
- // ///////////////////////////////////////////////////////////////////////////
- // Debug utilities
-
- public boolean satisfiesRedBlackProperties() {
- // Compute depth of black nodes.
- int node = this.root;
- int blackDepth = 0;
- while (node != NIL) {
- if (this.color[node] == black) {
- ++blackDepth;
- }
- node = getLeft(node);
- }
- return satisfiesRBProps(this.root, blackDepth, 0);
- }
- private boolean satisfiesRBProps(int node, final int blackDepth, int currentBlack) {
- if (node == NIL) {
- return (currentBlack == blackDepth);
- }
- if (this.color[node] == red) {
- if (this.color[getLeft(node)] == red || this.color[getRight(node)] == red) {
- return false;
- }
- } else {
- ++currentBlack;
- }
- return (satisfiesRBProps(getLeft(node), blackDepth, currentBlack) && satisfiesRBProps(
- getRight(node), blackDepth, currentBlack));
- }
-
- public int maxDepth() {
- return maxDepth(this.root, 0);
- }
-
- public int minDepth() {
- return minDepth(this.root, 0);
- }
-
- public int nodeDepth(int k) {
- return nodeDepth(this.root, 1, k);
- }
-
- private int nodeDepth(int node, int depth, int k) {
- if (node == NIL) {
- return -1;
- }
- if (k == getKey(node)) {
- return depth;
- } else if (k < getKey(node)) {
- return nodeDepth(getLeft(node), depth + 1, k);
- } else {
- return nodeDepth(getRight(node), depth + 1, k);
- }
- }
-
- private int maxDepth(int node, int depth) {
- if (node == NIL) {
- return depth;
- }
- int depth1 = maxDepth(getLeft(node), depth + 1);
- int depth2 = maxDepth(getRight(node), depth + 1);
- return (depth1 > depth2) ? depth1 : depth2;
- }
-
- private int minDepth(int node, int depth) {
- if (node == NIL) {
- return depth;
- }
- int depth1 = maxDepth(getLeft(node), depth + 1);
- int depth2 = maxDepth(getRight(node), depth + 1);
- return (depth1 > depth2) ? depth2 : depth1;
- }
-
- public final void printKeys() {
- if (this.size() == 0) {
- System.out.println("Tree is empty.");
- return;
- }
- StringBuffer buf = new StringBuffer();
- printKeys(this.root, 0, buf);
- System.out.println(buf);
- }
-
- private final void printKeys(int node, int offset, StringBuffer buf) {
- if (node == NIL) {
- // StringUtils.printSpaces(offset, buf);
- // buf.append("NIL\n");
- return;
- }
- StringUtils.printSpaces(offset, buf);
- buf.append(Integer.toString(getKey(node)));
- if (this.color[node] == black) {
- buf.append(" BLACK");
- }
- buf.append("\n");
- printKeys(getLeft(node), offset + 2, buf);
- printKeys(getRight(node), offset + 2, buf);
- }
-
- public static void main(String[] args) {
- System.out.println("Constructing tree.");
- IntArrayRBT tree = new IntArrayRBT();
- tree.insertKeyWithDups(2);
- tree.insertKeyWithDups(1);
- // assert(tree.color[0] == black);
- // assert(tree.size() == 0);
- // assert(tree.insertKey(5) == 1);
- // assert(tree.size() == 1);
- // assert(tree.insertKeyWithDups(5) == 2);
- // assert(tree.insertKey(3) == 3);
- // assert(tree.size() == 3);
- // assert(tree.insertKey(4) == 4);
- // assert(tree.size() == 4);
- // assert(tree.insertKey(2) == 5);
- // assert(tree.size() == 5);
- // tree.printKeys();
- // System.out.println("Constructing tree.");
- // tree = new IntArrayRBT();
- // int max = 10;
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(i);
- // }
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(i);
- // }
- // tree.printKeys();
- // tree = new IntArrayRBT();
- // max = 100;
- // // System.out.println("Creating tree.");
- // for (int i = 1; i <= max; i++) {
- // tree.insertKeyWithDups(1);
- // }
- // // System.out.println("Printing tree.");
- // tree.printKeys();
- // // IntIterator it = tree.iterator();
- // // int numElements = 0;
- // // while (it.hasNext()) {
- // // it.next();
- // // ++numElements;
- // // }
- }
}
Added: 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=1540372&view=auto
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java (added)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBTcommon.java Sat Nov 9 19:28:37 2013
@@ -0,0 +1,794 @@
+/*
+ * 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.
+ */
+
+package org.apache.uima.internal.util.rb_trees;
+
+import org.apache.uima.internal.util.IntArrayUtils;
+import org.apache.uima.internal.util.StringUtils;
+
+/**
+ * Common part of Red-black tree implementation based on integer arrays. Preliminary performance measurements on
+ * j2se 1.4 indicate that the performance improvement as opposed to an object-based implementation
+ * are miniscule. This seems to indicate a much improved object creation handling in this vm.
+ * However the space improvements are substantial.
+ *
+ */
+public class IntArrayRBTcommon {
+
+ 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
+ // which is the largest index that can be stored in klrp
+ // because it is shifted left by 2
+ protected int[] klrp1;
+ protected int[] klrp2;
+ protected int[] klrp3;
+ protected static final int MAXklrp0 = 512 * 1024 * 1024;
+ protected static final int MAXklrpMask = MAXklrp0 - 1;
+
+
+ protected int getXXX(int node, int offset) {
+ if (node < MAXklrp0) {
+ return klrp[(node << 2) + offset];
+ } else {
+ final int w = node >> 29;
+ final int i = ((node & MAXklrpMask) << 2) + offset;
+ switch (w) {
+ case 1:
+ return klrp1[i];
+ case 2:
+ return klrp2[i];
+ case 3:
+ return klrp3[i];
+ default:
+ throw new RuntimeException();
+ }
+ }
+ }
+
+ 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;
+ final int i = ((node & MAXklrpMask) << 2) + offset;
+ switch (w) {
+ case 1:
+ return klrp1[i] = value;
+ case 2:
+ return klrp2[i] = value;
+ case 3:
+ return klrp3[i] = value;
+ default:
+ throw new RuntimeException();
+ }
+ }
+ }
+
+ protected int getKey(int node) {
+ if (useklrp) {
+ return getXXX(node, 0);
+ }
+ return key[node];
+ }
+
+ protected int setKey(int node, int value) {
+ if (useklrp) {
+ return setXXX(node, 0, value);
+ }
+ return key[node] = value;
+ }
+
+ protected int getLeft(int node) {
+ if (useklrp) {
+ return getXXX(node, 1);
+ }
+ return left[node];
+ }
+
+ protected int setLeft(int node, int value) {
+ if (useklrp) {
+ return setXXX(node, 1, value);
+ }
+ return left[node] = value;
+ }
+
+ protected int getRight(int node) {
+ if (useklrp) {
+ return getXXX(node, 2);
+ }
+ return right[node];
+ }
+
+ protected int setRight(int node, int value) {
+ if (useklrp) {
+ return setXXX(node, 2, value);
+ }
+ return right[node] = value;
+ }
+
+ protected int getParent(int node) {
+ if (useklrp) {
+ return getXXX(node, 3);
+ }
+ return parent[node];
+ }
+
+ protected int setParent(int node, int value) {
+ if (useklrp) {
+ return setXXX(node, 3, value);
+ }
+ return parent[node] = value;
+ }
+
+ // Colors.
+ protected boolean[] color;
+
+ // The index of the next node.
+ protected int next;
+
+ // The current size of the tree. Since we can remove nodes, since needs to
+ // be kept separate from the next free cell.
+ protected int size;
+
+ // The root of the tree.
+ protected int root;
+
+ // 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;
+
+ protected static final int default_size = 1024; // must be pwr of 2 for useklrp true
+
+ final protected int initialSize;
+
+ final protected int growth_factor = 2; // must be pwr of 2 for useklrp true
+
+ final protected int multiplication_limit = 1024 * 1024 * 2; // must be pwr of 2 for useklrp true
+
+ // The NIL sentinel
+ public static final int NIL = 0;
+
+ // The colors.
+ protected static final boolean red = true;
+
+ protected static final boolean black = false;
+
+ /**
+ * Constructor for IntArrayRBT.
+ */
+ public IntArrayRBTcommon() {
+ this(default_size);
+ }
+
+ public IntArrayRBTcommon(int initialSize) {
+ if (initialSize < 4) {
+ initialSize = 4;
+ }
+ initVars();
+ this.initialSize = nextPowerOf2(initialSize);
+ setupArrays();
+ }
+
+ protected int nextPowerOf2(int v) {
+ // v is >= 0
+ int v2 = Integer.highestOneBit(v);
+ return (v2 < v) ? (v2 << 1) : v2;
+ }
+
+ 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];
+ }
+ this.color = new boolean[initialSize];
+ setLeft(NIL, NIL);
+ setRight(NIL, NIL);
+ setParent(NIL, NIL);
+ this.color[NIL] = black;
+ }
+
+ protected void initVars() {
+ this.root = NIL;
+ this.greatestNode = NIL;
+ this.next = 1;
+ this.size = 0;
+ }
+
+ public void flush() {
+ // 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();
+ }
+ }
+ }
+
+ public final int size() {
+ return this.size;
+ }
+
+ /**
+ * There are two strategies for storing data, controlled by useklrp.
+ * If useklrp, then 4 elements are put together into one int vector,
+ * taking 4 words per element.
+ * Other elements are kept in their own vectors.
+ *
+ * The growth strategy for the 4-element one is to
+ * a) start at some minimum (a power of 2)
+ * b) grow by doubling up to 2 * 1024 *1024
+ * c) grow by adding 2 *1024 * 1024, until
+ * d) reaching the maximum size (the max index will be 1 less)
+ * e) when that size is reached, the next int[] is set up with the
+ * minimum, and it grows as above.
+ *
+ * The test for growth and growing is made individually for the different parts.
+ * For color (a boolean), the size for stopping doubling is 32 * 2 * 1024 * 1024,
+ * so the # of words is the same.
+ *
+ * @param requiredSize
+ */
+
+ protected void ensureCapacityKlrp(int requiredSize) {
+ // the klrp design stacks 4 pointers together into the int array
+ // When growing, the last array is grown by the needed amount.
+ // Edge case: if the new required size jumps up by more than
+ // about 2 million, the previous array might need to be
+ // expanded too.
+ // This could in a real edge case require all previous arrays
+ // to be expanded.
+
+ final int w = requiredSize >> 29; // w is 0-3
+ final int requiredCapacityForLastSegment = Math.max(1024, requiredSize - w * MAXklrp0);
+ switch (w) {
+ case 3: {
+ if (klrp3 == null) {
+ klrp3 = new int[requiredCapacityForLastSegment << 2];
+ } else {
+ klrp3 = ensureArrayCapacity(klrp3, requiredCapacityForLastSegment << 2);
+ }
+ maximize(klrp2);
+ maximize(klrp1);
+ maximize(klrp);
+ }
+ break;
+ case 2: {
+ if (klrp2 == null) {
+ klrp2 = new int[requiredCapacityForLastSegment << 2];
+ } else {
+ klrp2 = ensureArrayCapacity(klrp2, requiredCapacityForLastSegment << 2);
+ }
+ maximize(klrp1);
+ maximize(klrp);
+ }
+ break;
+ case 1: {
+ if (klrp1 == null) {
+ klrp1 = new int[requiredCapacityForLastSegment << 2];
+ } else {
+ klrp1 = ensureArrayCapacity(klrp1, requiredCapacityForLastSegment << 2);
+ }
+ maximize(klrp);
+ }
+ break;
+ case 0:
+// if (klrp == null) { // never true
+// klrp = new int[requiredSizeForLastSegment << 2];
+// } else {
+ klrp = ensureArrayCapacity(klrp, requiredCapacityForLastSegment << 2);
+// }
+ break;
+ default:
+ 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);
+ }
+
+ protected void ensureCapacity(int requiredSize) {
+ this.color = ensureBooleanArraySize(this.color, requiredSize);
+ }
+
+ // only called for krlp style
+ private int[] maximize(int[] array) {
+ if (array.length < MAXklrp0) {
+ int[] a = new int[MAXklrp0];
+ System.arraycopy(array, 0, a, 0, array.length);
+ return a;
+ }
+ return array;
+ }
+
+ protected int newNode(final int k) {
+ // Make sure the tree is big enough to accomodate 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);
+ }
+ }
+ }
+ if (this.next >= lenKlrp) {
+ ensureCapacityKlrp(this.next + 1);
+ }
+ }
+
+ if (this.next >= this.color.length){
+ if (!useklrp) {
+ ensureCapacityNotKrlp(this.next + 1);
+ }
+ ensureCapacity(this.next + 1);
+ }
+
+ // assert(key.length > next);
+ final int z = this.next;
+ ++this.next;
+ ++this.size;
+ setKey(z, k);
+ setLeft(z, NIL);
+ setRight(z, NIL);
+ this.color[z] = red;
+ return z;
+ }
+
+ protected final void setAsRoot(int x) {
+ this.root = x;
+ setParent(this.root, NIL);
+ }
+
+ /**
+ *
+ * @param array - the array to expand - may be klrp0, 1, 2, 3, etc.
+ * @param newSize = the total size - if in parts, the size of the part
+ * @return expanded array
+ */
+ protected final int[] ensureArrayCapacity(final int[] array, final int newSize) {
+ return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
+ }
+
+ // times 32 to have the same tuning for expanding that int arrays do, for booleans
+ private final boolean[] ensureBooleanArraySize(boolean[] array, int newSize) {
+ return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit * 32);
+ }
+
+ protected final void leftRotate(final int x) {
+ final int y = getRight(x);
+ final int left_of_y = getLeft(y);
+ setRight(x, left_of_y );
+ if (left_of_y != NIL) {
+ setParent(left_of_y , x);
+ }
+ setParent(y, getParent(x));
+ if (this.root == x) {
+ setAsRoot(y);
+ } else {
+ final int parent_x = getParent(x);
+ if (x == getLeft(parent_x)) {
+ setLeft(parent_x, y);
+ } else {
+ setRight(parent_x, y);
+ }
+ }
+ setLeft(y, x);
+ setParent(x, y);
+ }
+
+ protected final void rightRotate(final int x) {
+ final int y = getLeft(x);
+ final int right_y = getRight(y);
+ setLeft(x, right_y);
+ if (right_y != NIL) {
+ setParent(right_y, x);
+ }
+ final int parent_x = getParent(x);
+ setParent(y, parent_x);
+ if (this.root == x) {
+ setAsRoot(y);
+ } else {
+ if (x == getRight(parent_x)) {
+ setRight(parent_x, y);
+ } else {
+ setLeft(parent_x, y);
+ }
+ }
+ setRight(y, x);
+ setParent(x, y);
+ }
+
+ /**
+ * Find the first node such that k <= key[node].
+ */
+ protected 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) {
+ return node;
+ } else {
+ node = getRight(node);
+ }
+ }
+ // node == NIL
+ return NIL;
+ }
+
+ /**
+ * Find the node such that key[node] >= k and key[previous(node)] < k.
+ */
+ public int findInsertionPointNoDups(final int k) {
+ int node = this.root;
+ int found = node;
+ 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);
+ }
+ }
+ // node == NIL
+ return found;
+ }
+
+ public final boolean containsKey(int k) {
+ return (findKey(k) != NIL);
+ }
+
+ public final boolean contains(int k) {
+ return (findKey(k) != NIL);
+ }
+
+ protected final int getFirstNode() {
+ if (this.root == NIL) {
+ return NIL;
+ }
+ int node = this.root;
+ while (true) {
+ final int left_node = getLeft(node);
+ if (left_node == NIL) {
+ break;
+ }
+ 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;
+ final int rightNode = getRight(node);
+ if (rightNode != NIL) {
+ node = rightNode;
+ while (true) {
+ final int leftNode = getLeft(node);
+ if (leftNode == NIL) {
+ break;
+ }
+ node = leftNode;
+ }
+// while (getLeft(node) != NIL) {
+// node = getLeft(node);
+// }
+ } else {
+ y = getParent(node);
+ while ((y != NIL) && (node == getRight(y))) {
+ node = y;
+ y = getParent(y);
+ }
+ node = y;
+ }
+ return node;
+ }
+
+ protected final int previousNode(int node) {
+ final int leftNode = getLeft(node);
+ if (leftNode != NIL) {
+ node = leftNode;
+ while (true) {
+ final int rightNode = getRight(node);
+ if (rightNode == NIL) {
+ break;
+ }
+ 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) {
+ return NIL;
+ }
+ // node is now a left dtr, so we can go one up.
+ node = getParent(node);
+ }
+ return node;
+ }
+
+ protected void deleteNode(final int z) {
+ 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);
+ 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 (parent_y == NIL) {
+ setAsRoot(x);
+ } else {
+ if (y == getLeft(parent_y)) {
+ setLeft(parent_y, x);
+ } else {
+ setRight(parent_y, x);
+ }
+ }
+ if (y != z) {
+ setKey(z, getKey(y));
+ }
+ if (this.color[y] == black) {
+ deleteFixup(x);
+ }
+ }
+
+ protected void deleteFixup(int x) {
+ int w;
+ while ((x != this.root) && (this.color[x] == black)) {
+ final int parent_x = getParent(x);
+ if (x == getLeft(parent_x)) {
+ w = getRight(parent_x);
+ if (this.color[w] == red) {
+ this.color[w] = black;
+ this.color[parent_x] = red;
+ leftRotate(parent_x);
+ w = getRight(parent_x);
+ }
+ if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
+ this.color[w] = red;
+ x = parent_x;
+ } else {
+ if (this.color[getRight(w)] == black) {
+ this.color[getLeft(w)] = black;
+ this.color[w] = red;
+ rightRotate(w);
+ w = getRight(parent_x);
+ }
+ this.color[w] = this.color[parent_x];
+ this.color[parent_x] = black;
+ this.color[getRight(w)] = black;
+ leftRotate(parent_x);
+ x = this.root;
+ }
+ } else {
+ w = getLeft(parent_x);
+ if (this.color[w] == red) {
+ this.color[w] = black;
+ this.color[parent_x] = red;
+ rightRotate(parent_x);
+ w = getLeft(parent_x);
+ }
+ if ((this.color[getLeft(w)] == black) && (this.color[getRight(w)] == black)) {
+ this.color[w] = red;
+ x = getParent(x);
+ } else {
+ if (this.color[getLeft(w)] == black) {
+ this.color[getRight(w)] = black;
+ this.color[w] = red;
+ leftRotate(w);
+ w = getLeft(getParent(x));
+ }
+ this.color[w] = this.color[parent_x];
+ this.color[parent_x] = black;
+ this.color[getLeft(w)] = black;
+ rightRotate(parent_x);
+ x = this.root;
+ }
+ }
+ }
+ this.color[x] = black;
+ }
+
+
+ // ///////////////////////////////////////////////////////////////////////////
+ // Debug utilities
+
+ public boolean satisfiesRedBlackProperties() {
+ // Compute depth of black nodes.
+ int node = this.root;
+ int blackDepth = 0;
+ while (node != NIL) {
+ if (this.color[node] == black) {
+ ++blackDepth;
+ }
+ node = getLeft(node);
+ }
+ return satisfiesRBProps(this.root, blackDepth, 0);
+ }
+
+ protected boolean satisfiesRBProps(int node, final int blackDepth, int currentBlack) {
+ if (node == NIL) {
+ return (currentBlack == blackDepth);
+ }
+ if (this.color[node] == red) {
+ if (this.color[getLeft(node)] == red || this.color[getRight(node)] == red) {
+ return false;
+ }
+ } else {
+ ++currentBlack;
+ }
+ return (satisfiesRBProps(getLeft(node), blackDepth, currentBlack) && satisfiesRBProps(
+ getRight(node), blackDepth, currentBlack));
+ }
+
+ public int maxDepth() {
+ return maxDepth(this.root, 0);
+ }
+
+ public int minDepth() {
+ return minDepth(this.root, 0);
+ }
+
+ public int nodeDepth(int k) {
+ return nodeDepth(this.root, 1, k);
+ }
+
+ protected int nodeDepth(int node, int depth, int k) {
+ if (node == NIL) {
+ return -1;
+ }
+ if (k == getKey(node)) {
+ return depth;
+ } else if (k < getKey(node)) {
+ return nodeDepth(getLeft(node), depth + 1, k);
+ } else {
+ return nodeDepth(getRight(node), depth + 1, k);
+ }
+ }
+
+ protected int maxDepth(int node, int depth) {
+ if (node == NIL) {
+ return depth;
+ }
+ int depth1 = maxDepth(getLeft(node), depth + 1);
+ int depth2 = maxDepth(getRight(node), depth + 1);
+ return (depth1 > depth2) ? depth1 : depth2;
+ }
+
+ protected int minDepth(int node, int depth) {
+ if (node == NIL) {
+ return depth;
+ }
+ int depth1 = maxDepth(getLeft(node), depth + 1);
+ int depth2 = maxDepth(getRight(node), depth + 1);
+ return (depth1 > depth2) ? depth2 : depth1;
+ }
+
+ public final void printKeys() {
+ if (this.size() == 0) {
+ System.out.println("Tree is empty.");
+ return;
+ }
+ StringBuffer buf = new StringBuffer();
+ printKeys(this.root, 0, buf);
+ System.out.println(buf);
+ }
+
+ protected final void printKeys(int node, int offset, StringBuffer buf) {
+ if (node == NIL) {
+ // StringUtils.printSpaces(offset, buf);
+ // buf.append("NIL\n");
+ return;
+ }
+ StringUtils.printSpaces(offset, buf);
+ buf.append(Integer.toString(getKey(node)));
+ if (this.color[node] == black) {
+ buf.append(" BLACK");
+ }
+ buf.append("\n");
+ printKeys(getLeft(node), offset + 2, buf);
+ printKeys(getRight(node), offset + 2, buf);
+ }
+
+}