Package org.apache.uima.internal.util.rb_trees

Class IntArrayRBTcommon

java.lang.Object
org.apache.uima.internal.util.rb_trees.IntArrayRBTcommon
Direct Known Subclasses:
Int2IntRBT, IntArrayRBT
public class IntArrayRBTcommon extends Object
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.

  • Field Details

    • klrp

      protected int[] klrp
      klrp: Key, Left, Right, Parent Each "node" has a node address. The Left, Right, and Parent are in terms of the the node address. The key is arbitrary, but kept in sorted order. A global, "root" has the node address of the root node. The range of possible nodes is 0 to Integer.MAX_VALUE, but 0 is reserved as NIL

    • klrp1

      protected int[] klrp1

    • klrp2

      protected int[] klrp2

    • klrp3

      protected int[] klrp3

    • MAXklrp0

      protected static final int MAXklrp0
      See Also:

    • MAXklrpMask

      protected static final int MAXklrpMask
      See Also:

    • color

      protected boolean[] color

    • next

      protected int next

    • size

      protected int size

    • root

      protected int root

    • greatestNode

      public int greatestNode

    • default_size

      protected static final int default_size
      See Also:

    • initialSize

      protected final int initialSize

    • growth_factor

      protected final int growth_factor
      See Also:

    • multiplication_limit

      protected final int multiplication_limit
      See Also:

    • NIL

      public static final int NIL
      See Also:

    • red

      protected static final boolean red
      See Also:

    • black

      protected static final boolean black
      See Also:

  • Constructor Details

    • IntArrayRBTcommon

      public IntArrayRBTcommon()
      Constructor for IntArrayRBT.

    • IntArrayRBTcommon

      public IntArrayRBTcommon(int initialSize)

  • Method Details

    • getXXX

      protected int getXXX(int node, int offset)

    • setXXX

      protected int setXXX(int node, int offset, int value)

    • getLeft

      protected int getLeft(int node)

    • setLeft

      protected int setLeft(int node, int value)

    • getRight

      protected int getRight(int node)

    • setRight

      protected int setRight(int node, int value)

    • getParent

      protected int getParent(int node)

    • setParent

      protected int setParent(int node, int value)
      Parameters:
      node - -
      value - -
      Returns:
      the value

    • getKeyForNode

      protected int getKeyForNode(int node)

    • nextPowerOf2

      protected int nextPowerOf2(int v)

    • setupArrays

      protected void setupArrays()

    • initVars

      protected void initVars()

    • flush

      public void flush()

    • size

      public final int size()

    • ensureCapacityKlrp

      protected void ensureCapacityKlrp(int requiredSize)
      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.
      Parameters:
      requiredSize - -

    • newNode

      protected int newNode(int k)

    • setAsRoot

      protected final void setAsRoot(int x)

    • ensureArrayCapacity

      protected final int[] ensureArrayCapacity(int[] array, int newSize)
      Parameters:
      array - - the array to expand - may be klrp0, 1, 2, 3, etc.
      newSize - = the total size - if in parts, the size of the part
      Returns:
      expanded array

    • leftRotate

      protected final void leftRotate(int x)

    • rightRotate

      protected final void rightRotate(int x)

    • findKey

      public int findKey(int k)
      Parameters:
      k - -
      Returns:
      the first node such that k = key[node].

    • findKeyDown

      protected int findKeyDown(int k, int node)

    • findInsertionPoint

      public int findInsertionPoint(int k)
      Find 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)
      Parameters:
      k - the key
      Returns:
      the index of the node, or NIL if k > all keys

    • findInsertionPointNoDups

      public int findInsertionPointNoDups(int k)
      Find the node such that key[node] ≥ k and key[previous(node)] < k.
      Parameters:
      k - -
      Returns:
      the node such that key[node] ≥ k and key[previous(node)] < k.

    • findInsertionPointCmn

      public int findInsertionPointCmn(int k, boolean moveToLeftmost)

    • containsKey

      public final boolean containsKey(int k)

    • contains

      public final boolean contains(int k)

    • getFirstNode

      public final int getFirstNode()

    • nextNode

      public final int nextNode(int node)
      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.
      Parameters:
      node - starting point
      Returns:
      the node logically following this one.

    • previousNode

      public final int previousNode(int node)
      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
      Parameters:
      node - the current node index
      Returns:
      the previous node index or NIL

    • deleteNode

      protected void deleteNode(int z)
      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.
      Parameters:
      z - node to be removed, logically

    • deleteFixup

      protected void deleteFixup(int x)

    • compare

      protected int compare(int v1, int v2)

    • satisfiesRedBlackProperties

      public boolean satisfiesRedBlackProperties()

    • satisfiesRBProps

      protected boolean satisfiesRBProps(int node, int blackDepth, int currentBlack)

    • maxDepth

      public int maxDepth()

    • minDepth

      public int minDepth()

    • nodeDepth

      public int nodeDepth(int k)

    • nodeDepth

      protected int nodeDepth(int node, int depth, int k)

    • maxDepth

      protected int maxDepth(int node, int depth)

    • minDepth

      protected int minDepth(int node, int depth)

    • printKeys

      public final void printKeys()

    • printKeys

      protected final void printKeys(int node, int offset, StringBuilder buf)