Class IntHashSet

  • All Implemented Interfaces:
    PositiveIntSet

    public class IntHashSet
    extends Common_hash_support
    implements PositiveIntSet
    A set of non-zero ints. Can be negative. 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 Detail

      • offset

        private int offset
      • keys4

        private int[] keys4
      • keys2

        private short[] keys2
      • isMake4

        private boolean isMake4
      • mostPositive

        private int mostPositive
      • mostNegative

        private int mostNegative
    • Constructor Detail

      • IntHashSet

        public IntHashSet()
      • IntHashSet

        public IntHashSet​(int initialCapacity)
      • IntHashSet

        public IntHashSet​(int initialSizeBeforeExpanding,
                          int offset)
        Parameters:
        initialSizeBeforeExpanding - - 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 Detail

      • tableSpace

        public static int tableSpace​(int numberOfElements)
      • wontExpand

        public boolean wontExpand()
        Method called by handleHashSet in PositiveIntSet to indicate if adding this many items would cause an expansion
        Returns:
        true if would not expand
      • wontExpand

        public boolean wontExpand​(int n)
        Method called by handleHashSet in PositiveIntSet to indicate if adding this many items would cause an expansion
        Parameters:
        n - the number of items added
        Returns:
        true if would not expand
      • getSpaceUsedInWords

        public int getSpaceUsedInWords()
      • getSpaceOverheadInWords

        public static int getSpaceOverheadInWords()
      • getRawFromAdjKey

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

        private void resetTable()
      • 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)
        This method is part of the PositiveSet API, and is defined to return an int that could be used with iterators to position them. For this case, it is not used, because the iterators don't support positioning this way because they are not sorted.
        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.
      • findPosition

        private int findPosition​(int rawKey)
        Parameters:
        rawKey - the key value to find
        Returns:
        the position in the table if present, otherwise the position of the slot where the key value would be added, unless the new value is at a position which would require the key2 form to be switched to the key4 form, in which case, -1 is returned (means not found, and requires conversion to 4 byte keys)
      • findPosition4

        private int findPosition4​(int rawKey)
      • findPositionAdjKey

        private int findPositionAdjKey​(int adjKey)
      • 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, a range from negative to positive, but never 0
      • 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
      • find4AndAddIfMissing

        private boolean find4AndAddIfMissing​(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
      • 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.
      • get

        public int get​(int pos)
        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:
        pos - - get the element at this position. This is for iterator use only, and is not related to any key
        Returns:
        the element
      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • isShortHashSet

        boolean isShortHashSet()
      • getOffset

        int getOffset()