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
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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
IntHashSet.IntHashSetIterator
-
Nested classes/interfaces inherited from class org.apache.uima.internal.util.Common_hash_support
Common_hash_support.CommonCopyOld2New, Common_hash_support.CommonKeyIterator
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
isMake4
private short[]
keys2
private int[]
keys4
private int
mostNegative
private int
mostPositive
private int
offset
private static int
REMOVED2
private static int
REMOVED4
static int
SIZE_NEEDING_4_BYTES
-
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
Constructors Constructor Description IntHashSet()
IntHashSet(int initialCapacity)
IntHashSet(int initialSizeBeforeExpanding, int offset)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(int rawKey)
private void
addInner2(short adjKey)
private void
addInner4(int rawKey)
used for increasing table sizevoid
bulkAddTo(IntVector v)
add all elements in this set to the IntVector v as a bulk operationvoid
clear()
remove all members of the setprotected void
clearKeysAndValues()
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
getMostNegative()
int
getMostPositive()
(package private) int
getOffset()
private int
getRawFromAdjKey(int adjKey)
Only call this if using short values with offsetstatic int
getSpaceOverheadInWords()
int
getSpaceUsedInWords()
protected boolean
is_valid_key(int pos)
private boolean
isAdjKeyOutOfRange(int adjKey)
(package private) boolean
isShortHashSet()
boolean
isValid(int position)
For FSBagIndex low level iterator useIntListIterator
iterator()
protected int
keys_length()
int
moveToFirst()
For FSBagIndex low level iterator useint
moveToLast()
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
resetTable()
void
showHistogram()
private void
switchTo4byte()
static int
tableSpace(int numberOfElements)
int[]
toIntArray()
java.lang.String
toString()
boolean
wontExpand()
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 expansion-
Methods 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 Detail
-
SIZE_NEEDING_4_BYTES
public static final int SIZE_NEEDING_4_BYTES
- See Also:
- Constant Field Values
-
REMOVED4
private static final int REMOVED4
- See Also:
- Constant Field Values
-
REMOVED2
private static final int REMOVED2
- See Also:
- Constant Field Values
-
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 expansionoffset
- - 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()
-
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
public IntListIterator 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
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 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
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
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
-
-