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 booleanprivate short[]private int[]private intprivate intprivate intprivate static final intprivate static final intstatic final intFields 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, TUNEFields 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 TypeMethodDescriptionbooleanadd(int rawKey) private voidaddInner2(short adjKey) private voidaddInner4(int rawKey) used for increasing table sizevoidadd all elements in this set to the IntVector v as a bulk operationvoidclear()remove all members of the setprotected voidbooleancontains(int rawKey) protected voidcopy_to_new_table(int new_capacity, int old_capacity, Common_hash_support.CommonCopyOld2New commonCopy) intfind(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 booleanfind4AndAddIfMissing(int rawKey) private intfindPosition(int rawKey) private intfindPosition4(int rawKey) private intfindPositionAdjKey(int adjKey) intget(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 intgetAdjKey(int rawKey) return the adjusted key.intint(package private) intprivate intgetRawFromAdjKey(int adjKey) Only call this if using short values with offsetstatic intintprotected booleanis_valid_key(int pos) private booleanisAdjKeyOutOfRange(int adjKey) (package private) booleanbooleanisValid(int position) For FSBagIndex low level iterator useiterator()protected intintFor FSBagIndex low level iterator useintFor FSBagIndex low level iterator useintmoveToNext(int position) For FSBagIndex low level iterator useintmoveToPrevious(int position) For FSBagIndex low level iterator useprotected voidnewKeysAndValues(int capacity) booleanremove(int rawKey) mostPositive and mostNegative are not updated for removes.private voidvoidprivate voidstatic inttableSpace(int numberOfElements) int[]toString()booleanMethod called by handleHashSet in PositiveIntSet to indicate if adding this many items would cause an expansionbooleanwontExpand(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, tableSpaceMethods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, waitMethods 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:PositiveIntSetremove all members of the set- Specified by:
clearin interfacePositiveIntSet- Overrides:
clearin classCommon_hash_support
-
isAdjKeyOutOfRange
private boolean isAdjKeyOutOfRange(int adjKey) -
contains
public boolean contains(int rawKey) - Specified by:
containsin 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:
findin 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:
addin 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:
removein 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:
showHistogramin 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:
getin 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:
iteratorin interfacePositiveIntSet- Returns:
- an iterator (may be ordered or unordered) over the members of the set
-
moveToFirst
public int moveToFirst()Description copied from interface:PositiveIntSetFor FSBagIndex low level iterator use- Specified by:
moveToFirstin interfacePositiveIntSet- Returns:
- the position of the first element, or -1;
-
moveToLast
public int moveToLast()Description copied from interface:PositiveIntSetFor FSBagIndex low level iterator use- Specified by:
moveToLastin interfacePositiveIntSet- Returns:
- the position of the last element, or -1;
-
moveToNext
public int moveToNext(int position) Description copied from interface:PositiveIntSetFor FSBagIndex low level iterator use- Specified by:
moveToNextin interfacePositiveIntSet- Parameters:
position- -- Returns:
- the position of the next element, or -1;
-
moveToPrevious
public int moveToPrevious(int position) Description copied from interface:PositiveIntSetFor FSBagIndex low level iterator use- Specified by:
moveToPreviousin interfacePositiveIntSet- Parameters:
position- -- Returns:
- the position of the next element, or -1;
-
isValid
public boolean isValid(int position) Description copied from interface:PositiveIntSetFor FSBagIndex low level iterator use- Specified by:
isValidin interfacePositiveIntSet- Parameters:
position- -- Returns:
- true if the position is between the first and last element inclusive.
-
bulkAddTo
Description copied from interface:PositiveIntSetadd all elements in this set to the IntVector v as a bulk operation- Specified by:
bulkAddToin interfacePositiveIntSet- Parameters:
v- - to be added to
-
toIntArray
public int[] toIntArray()- Specified by:
toIntArrayin 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_keyin classCommon_hash_support
-
keys_length
protected int keys_length()- Specified by:
keys_lengthin classCommon_hash_support
-
newKeysAndValues
protected void newKeysAndValues(int capacity) - Specified by:
newKeysAndValuesin classCommon_hash_support
-
clearKeysAndValues
protected void clearKeysAndValues()- Specified by:
clearKeysAndValuesin 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_tablein classCommon_hash_support
-