Package org.apache.uima.internal.util
Class IntHashSet
java.lang.Object
org.apache.uima.internal.util.Common_hash_support
org.apache.uima.internal.util.IntHashSet
- All Implemented Interfaces:
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
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from class org.apache.uima.internal.util.Common_hash_support
Common_hash_support.CommonCopyOld2New, Common_hash_support.CommonKeyIterator
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
private short[]
private int[]
private int
private int
private int
private static final int
private static final int
static final int
Fields inherited from class org.apache.uima.internal.util.Common_hash_support
found_removed, histogram, initialCapacity, loadFactor, maxProbe, MIN_CAPACITY, MIN_CAPACITY_SHRINK, MIN_SIZE, removed, secondTimeShrinkable, sizeWhichTriggersExpansion, TUNE
Fields inherited from interface org.apache.uima.internal.util.PositiveIntSet
IS_TRACE_MODE_SWITCH
-
Constructor Summary
ConstructorsConstructorDescriptionIntHashSet
(int initialCapacity) IntHashSet
(int initialSizeBeforeExpanding, int offset) -
Method Summary
Modifier and TypeMethodDescriptionboolean
add
(int rawKey) private void
addInner2
(short adjKey) private void
addInner4
(int rawKey) used for increasing table sizevoid
add all elements in this set to the IntVector v as a bulk operationvoid
clear()
remove all members of the setprotected void
boolean
contains
(int rawKey) protected void
copy_to_new_table
(int new_capacity, int old_capacity, Common_hash_support.CommonCopyOld2New commonCopy) 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.private boolean
find4AndAddIfMissing
(int rawKey) private int
findPosition
(int rawKey) private int
findPosition4
(int rawKey) private int
findPositionAdjKey
(int adjKey) 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.private int
getAdjKey
(int rawKey) return the adjusted key.int
int
(package private) int
private int
getRawFromAdjKey
(int adjKey) Only call this if using short values with offsetstatic int
int
protected boolean
is_valid_key
(int pos) private boolean
isAdjKeyOutOfRange
(int adjKey) (package private) boolean
boolean
isValid
(int position) For FSBagIndex low level iterator useiterator()
protected int
int
For FSBagIndex low level iterator useint
For FSBagIndex low level iterator useint
moveToNext
(int position) For FSBagIndex low level iterator useint
moveToPrevious
(int position) For FSBagIndex low level iterator useprotected void
newKeysAndValues
(int capacity) boolean
remove
(int rawKey) mostPositive and mostNegative are not updated for removes.private void
void
private void
static int
tableSpace
(int numberOfElements) int[]
toString()
boolean
Method called by handleHashSet in PositiveIntSet to indicate if adding this many items would cause an expansionboolean
wontExpand
(int n) Method called by handleHashSet in PositiveIntSet to indicate if adding this many items would cause an expansionMethods inherited from class org.apache.uima.internal.util.Common_hash_support
commonPutOrAddNotFound, commonRemove, debugValidate, findPosition, getCapacity, incrementSize, moveToNextFilled, moveToPreviousFilled, newTable, resetHistogram, size, tableSpace
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.apache.uima.internal.util.PositiveIntSet
forAllInts, size
-
Field Details
-
SIZE_NEEDING_4_BYTES
public static final int SIZE_NEEDING_4_BYTES- See Also:
-
REMOVED4
private static final int REMOVED4- See Also:
-
REMOVED2
private static final int REMOVED2- See Also:
-
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 Details
-
IntHashSet
public IntHashSet() -
IntHashSet
public IntHashSet(int initialCapacity) -
IntHashSet
public IntHashSet(int initialSizeBeforeExpanding, int offset) - Parameters:
initialSizeBeforeExpanding
- - you can add this many before expansionoffset
- - for values in the short range, the amount to subtract before storing. If == MIN_VALUE, then force 4 byte ints
-
-
Method Details
-
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() -
clear
public void clear()Description copied from interface:PositiveIntSet
remove all members of the set- Specified by:
clear
in interfacePositiveIntSet
- Overrides:
clear
in classCommon_hash_support
-
isAdjKeyOutOfRange
private boolean isAdjKeyOutOfRange(int adjKey) -
contains
public boolean contains(int rawKey) - Specified by:
contains
in interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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.
-
showHistogram
public void showHistogram()- Overrides:
showHistogram
in classCommon_hash_support
-
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 interfacePositiveIntSet
- Parameters:
pos
- - get the element at this position. This is for iterator use only, and is not related to any key- Returns:
- the element
-
iterator
- Specified by:
iterator
in interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- Parameters:
position
- -- Returns:
- true if the position is between the first and last element inclusive.
-
bulkAddTo
Description copied from interface:PositiveIntSet
add all elements in this set to the IntVector v as a bulk operation- Specified by:
bulkAddTo
in interfacePositiveIntSet
- Parameters:
v
- - to be added to
-
toIntArray
public int[] toIntArray()- Specified by:
toIntArray
in interfacePositiveIntSet
- Returns:
- the set as an arbitrarily ordered int array
-
toString
-
isShortHashSet
boolean isShortHashSet() -
getOffset
int getOffset() -
is_valid_key
protected boolean is_valid_key(int pos) - Specified by:
is_valid_key
in classCommon_hash_support
-
keys_length
protected int keys_length()- Specified by:
keys_length
in classCommon_hash_support
-
newKeysAndValues
protected void newKeysAndValues(int capacity) - Specified by:
newKeysAndValues
in classCommon_hash_support
-
clearKeysAndValues
protected void clearKeysAndValues()- Specified by:
clearKeysAndValues
in classCommon_hash_support
-
copy_to_new_table
protected void copy_to_new_table(int new_capacity, int old_capacity, Common_hash_support.CommonCopyOld2New commonCopy) - Specified by:
copy_to_new_table
in classCommon_hash_support
-