Class Int2IntRBT


  • public class Int2IntRBT
    extends IntArrayRBTcommon
    A map<int, int> uses IntArrayRBTcommon Int to Int Map, based on IntArrayRBT, used in no-duplicates mode Implements Map - like interface: keys and values are ints Entry set not (yet) impl no keySet() no values()
    • Field Detail

      • values

        protected int[] values
      • prevValue

        private int prevValue
      • lastNodeGotten

        private int lastNodeGotten
    • Constructor Detail

      • Int2IntRBT

        public Int2IntRBT()
        Constructor for IntArrayRBT.
      • Int2IntRBT

        public Int2IntRBT​(int initialSize)
    • Method Detail

      • getValue

        private int getValue​(int node)
      • clear

        public void clear()
      • ensureCapacityKlrp

        protected void ensureCapacityKlrp​(int requiredSize)
        Description copied from class: IntArrayRBTcommon
        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.
        Overrides:
        ensureCapacityKlrp in class IntArrayRBTcommon
        Parameters:
        requiredSize - -
      • treeInsert

        private int treeInsert​(int k,
                               int v)
        Parameters:
        k - the key to insert
        v - the value to insert (or replace, if key already present)
        Returns:
        negative index if key is found
      • get

        public int get​(int k)
        Get the value for a given key
        Parameters:
        k - -
        Returns:
        the value
      • getMostlyClose

        public int getMostlyClose​(int k)
      • put

        public int put​(int k,
                       int v)
        adds a k, v pair. if k already present, replaces v. returns previous value, or 0 if no prev value
        Parameters:
        k - -
        v - -
        Returns:
        previous value or 0 if key not previously present
      • findKeyFast

        protected int findKeyFast​(int k)
        Fast version of findKey Keeps the last node referenced *** NOT THREAD SAFE *** Tries to shorten the search path, conditionally
        Parameters:
        k - -
        Returns:
        -
      • findKeyFromLast

        private int findKeyFromLast​(int k)