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

Class IntArrayRBTcommon

  • Direct Known Subclasses:
    Int2IntRBT, IntArrayRBT
    public class IntArrayRBTcommon
extends java.lang.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.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected int compare​(int v1, int v2)  
      boolean contains​(int k)  
      boolean containsKey​(int k)  
      protected void deleteFixup​(int x)  
      protected void deleteNode​(int z)
      delete node z Step 1: locate a node to delete at the bottom of the tree.
      protected int[] ensureArrayCapacity​(int[] array, int newSize)  
      protected void ensureCapacityKlrp​(int requiredSize)
      There are two strategies for storing data, controlled by useklrp.
      int findInsertionPoint​(int k)
      Find the node such that key[node] ≥ k and key[previous(node)] < k.
      int findInsertionPointCmn​(int k, boolean moveToLeftmost)  
      int findInsertionPointNoDups​(int k)
      Find the node such that key[node] ≥ k and key[previous(node)] < k.
      int findKey​(int k)  
      protected int findKeyDown​(int k, int node)  
      void flush()  
      int getFirstNode()  
      protected int getKeyForNode​(int node)  
      protected int getLeft​(int node)  
      protected int getParent​(int node)  
      protected int getRight​(int node)  
      protected int getXXX​(int node, int offset)  
      protected void initVars()  
      protected void leftRotate​(int x)  
      int maxDepth()  
      protected int maxDepth​(int node, int depth)  
      int minDepth()  
      protected int minDepth​(int node, int depth)  
      protected int newNode​(int k)  
      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.
      protected int nextPowerOf2​(int v)  
      int nodeDepth​(int k)  
      protected int nodeDepth​(int node, int depth, int k)  
      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
      void printKeys()  
      protected void printKeys​(int node, int offset, java.lang.StringBuffer buf)  
      protected void rightRotate​(int x)  
      protected boolean satisfiesRBProps​(int node, int blackDepth, int currentBlack)  
      boolean satisfiesRedBlackProperties()  
      protected void setAsRoot​(int x)  
      protected int setLeft​(int node, int value)  
      protected int setParent​(int node, int value)  
      protected int setRight​(int node, int value)  
      protected void setupArrays()  
      protected int setXXX​(int node, int offset, int value)  
      int size()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • klrp

        protected int[] klrp

      • klrp1

        protected int[] klrp1

      • klrp2

        protected int[] klrp2

      • klrp3

        protected int[] klrp3

      • color

        protected boolean[] color

      • next

        protected int next

      • size

        protected int size

      • root

        protected int root

      • greatestNode

        public int greatestNode

      • initialSize

        protected final int initialSize

    • Constructor Detail

      • IntArrayRBTcommon

        public IntArrayRBTcommon()
        Constructor for IntArrayRBT.

      • IntArrayRBTcommon

        public IntArrayRBTcommon​(int initialSize)

    • Method Detail

      • 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,
                               java.lang.StringBuffer buf)