Class IntHashSet

java.lang.Object
org.apache.uima.internal.util.IntHashSet
All Implemented Interfaces:
PositiveIntSet

public class IntHashSet extends Object implements PositiveIntSet
A set of non-zero ints. 0 reserved internally to indicate "not in the map"; you will get an exception if you try to store 0 as a value. 0 will be returned if the value is missing from the map. allowed range is Integer.MIN_VALUE + 1 to Integer.MAX_VALUE 0 is the value for an empty cell Integer.MIN_VALUE is the value for a deleted (removed) value based on Int2IntHashMap This impl is for use in a single thread case only Supports shrinking (reallocating the big table) Supports representing ints as "short" 2byte values if possible, together with an offset amount. Because of the offset, the adjusted key could be == to the offset, so we subtract 1 from it to preserve 0 value as being the null / empty. For short values, the range is: Short.MIN_VALUE+2 to Short.MAX_VALUE after Offset, with the "0" value moved down by 1 and the Short.MIN_VALUE used for deleted (removed) items Automatically switches to full int representation if needed
  • Field Details

    • SIZE_NEEDING_4_BYTES

      public static final int SIZE_NEEDING_4_BYTES
      See Also:
    • DEFAULT_LOAD_FACTOR

      public static final float DEFAULT_LOAD_FACTOR
      See Also:
    • TUNE

      private static final boolean TUNE
      See Also:
    • loadFactor

      private final float loadFactor
      See Also:
    • initialCapacity

      private final int initialCapacity
    • histogram

      private int[] histogram
    • maxProbe

      private int maxProbe
    • sizeWhichTriggersExpansion

      private int sizeWhichTriggersExpansion
    • size

      private int size
    • nbrRemoved

      private int nbrRemoved
    • offset

      private int offset
    • keys4

      private int[] keys4
    • keys2

      private short[] keys2
    • secondTimeShrinkable

      private boolean secondTimeShrinkable
    • mostPositive

      private int mostPositive
    • mostNegative

      private int mostNegative
  • Constructor Details

    • IntHashSet

      public IntHashSet()
    • IntHashSet

      public IntHashSet(int initialCapacity)
    • IntHashSet

      public IntHashSet(int initialCapacity, int offset)
      Parameters:
      initialCapacity - - you can add this many before expansion
      offset - - for values in the short range, the amount to subtract before storing. If == MIN_VALUE, then force 4 byte ints
  • Method Details

    • nextHigherPowerOf2

      static int nextHigherPowerOf2(int i)
    • tableSpace

      public int tableSpace(int numberOfElements)
      The number of 32 bit words that are reserved when creating a table to hold the specified number of elements The number is a power of 2. The number is at least 16. The number is such that you could add this many elements without triggering the capacity expansion.
      Parameters:
      numberOfElements - -
      Returns:
      -
    • tableSpace

      public static int tableSpace(int numberOfElements, Float factor)
      Parameters:
      numberOfElements - -
      factor - -
      Returns:
      capacity of the main table (either 2 byte or 4 byte entries)
    • newTableKeepSize

      private void newTableKeepSize(int capacity, boolean make4)
    • incrementSize

      private void incrementSize()
    • wontExpand

      public boolean wontExpand()
    • wontExpand

      public boolean wontExpand(int n)
    • getSpaceUsedInWords

      public int getSpaceUsedInWords()
    • getSpaceOverheadInWords

      public static int getSpaceOverheadInWords()
    • getCapacity

      private int getCapacity()
    • getRawFromAdjKey

      private int getRawFromAdjKey(int adjKey)
      Only call this if using short values with offset
      Parameters:
      adjKey -
      Returns:
      raw key
    • increaseTableCapacity

      private void increaseTableCapacity()
    • newTable

      private void newTable(int capacity)
    • resetHistogram

      private void resetHistogram()
    • resetArray

      private void resetArray()
    • resetTable

      private void resetTable()
    • clear

      public void clear()
      Description copied from interface: PositiveIntSet
      remove all members of the set
      Specified by:
      clear in interface PositiveIntSet
    • findPosition

      private int findPosition(int adjKey)
      returns a position in the key/value table if the key is not found, then the position will be to the place where the key would be put upon adding, and the current internal value of keys[position] would be 0. if the key is found, then keys[position] == key
      Parameters:
      adjKey - - raw key - offset (-1 if this value is 0 or negative, to skip 0, if shorts)
      Returns:
      the probeAddr in keys array - might have a 0 value, or the key value if found
    • isAdjKeyOutOfRange

      private boolean isAdjKeyOutOfRange(int adjKey)
    • contains

      public boolean contains(int rawKey)
      Specified by:
      contains in interface PositiveIntSet
      Parameters:
      rawKey - -
      Returns:
      true if key is in the set
    • find

      public int find(int rawKey)
      Specified by:
      find in interface PositiveIntSet
      Parameters:
      rawKey - an item which may be in the set
      Returns:
      -1 if the item is not in the set, or a position value that can be used with iterators to start at that item.
    • getAdjKey

      private int getAdjKey(int rawKey)
      return the adjusted key. never called for 4 byte form for 2 byte key mode, subtract the offset, and adjust by -1 if 0 or less Note: returned value can be less than Short.MIN_VALUE
      Parameters:
      rawKey -
      Returns:
      adjusted key
    • switchTo4byte

      private void switchTo4byte()
    • add

      public boolean add(int rawKey)
      Specified by:
      add in interface PositiveIntSet
      Parameters:
      rawKey - -
      Returns:
      true if this set did not already contain the specified element
    • find4

      private boolean find4(int rawKey)
    • addInner4

      private void addInner4(int rawKey)
      used for increasing table size
      Parameters:
      rawKey -
    • addInner2

      private void addInner2(short adjKey)
    • remove

      public boolean remove(int rawKey)
      mostPositive and mostNegative are not updated for removes. So these values may be inaccurate, but mostPositive is always >= actual most positive, and mostNegative is always <= actual most negative. No conversion from int to short Can't replace the item with a 0 because other keys that were stored in the table which previously collided with the removed item won't be found. UIMA-4204
      Specified by:
      remove in interface PositiveIntSet
      Parameters:
      rawKey - the value to remove
      Returns:
      true if the key was present
    • size

      public int size()
      Specified by:
      size in interface PositiveIntSet
      Returns:
      number of elements in the set
    • getMostPositive

      public int getMostPositive()
      Returns:
      a value that is >= the actual most positive value in the table. it will be == unless a remove operation has removed a most positive value
    • getMostNegative

      public int getMostNegative()
      Returns:
      a value that is <= the actual least positive value in the table. It will be == unless remove operations has removed a least positive value.
    • showHistogram

      public void showHistogram()
    • get

      public int get(int index)
      For iterator use, position is a magic number returned by the internal find For short keys, the value stored for adjKey == 0 is -1, adjKey == -1 is -2, etc.
      Specified by:
      get in interface PositiveIntSet
      Parameters:
      index - - get the element at this position. This is for iterator use only, and is not related to any key
      Returns:
      the element
    • moveToNextFilled

      private int moveToNextFilled(int pos)
      advance pos until it points to a non 0 or is 1 past end
      Parameters:
      pos -
      Returns:
      updated pos
    • moveToPreviousFilled

      private int moveToPreviousFilled(int pos)
      decrement pos until it points to a non 0 or is -1
      Parameters:
      pos -
      Returns:
      updated pos
    • iterator

      public IntListIterator iterator()
      Specified by:
      iterator in interface PositiveIntSet
      Returns:
      an iterator (may be ordered or unordered) over the members of the set
    • moveToFirst

      public int moveToFirst()
      Description copied from interface: PositiveIntSet
      For FSBagIndex low level iterator use
      Specified by:
      moveToFirst in interface PositiveIntSet
      Returns:
      the position of the first element, or -1;
    • moveToLast

      public int moveToLast()
      Description copied from interface: PositiveIntSet
      For FSBagIndex low level iterator use
      Specified by:
      moveToLast in interface PositiveIntSet
      Returns:
      the position of the last element, or -1;
    • moveToNext

      public int moveToNext(int position)
      Description copied from interface: PositiveIntSet
      For FSBagIndex low level iterator use
      Specified by:
      moveToNext in interface PositiveIntSet
      Parameters:
      position - -
      Returns:
      the position of the next element, or -1;
    • moveToPrevious

      public int moveToPrevious(int position)
      Description copied from interface: PositiveIntSet
      For FSBagIndex low level iterator use
      Specified by:
      moveToPrevious in interface PositiveIntSet
      Parameters:
      position - -
      Returns:
      the position of the next element, or -1;
    • isValid

      public boolean isValid(int position)
      Description copied from interface: PositiveIntSet
      For FSBagIndex low level iterator use
      Specified by:
      isValid in interface PositiveIntSet
      Parameters:
      position - -
      Returns:
      true if the position is between the first and last element inclusive.
    • bulkAddTo

      public void bulkAddTo(IntVector v)
      Description copied from interface: PositiveIntSet
      add all elements in this set to the IntVector v as a bulk operation
      Specified by:
      bulkAddTo in interface PositiveIntSet
      Parameters:
      v - - to be added to
    • toIntArray

      public int[] toIntArray()
      Specified by:
      toIntArray in interface PositiveIntSet
      Returns:
      the set as an arbitrarily ordered int array
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • isShortHashSet

      boolean isShortHashSet()
    • getOffset

      int getOffset()