Package org.apache.uima.internal.util
Class IntHashSet
java.lang.Object
org.apache.uima.internal.util.IntHashSet
- All Implemented Interfaces:
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
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final float
private int[]
private final int
private short[]
private int[]
private final float
private int
private int
private int
private int
private int
private boolean
private int
static final int
private int
private static final boolean
-
Constructor Summary
Constructors -
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 setboolean
contains
(int rawKey) int
find
(int rawKey) private boolean
find4
(int rawKey) 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.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.private int
getAdjKey
(int rawKey) return the adjusted key.private int
int
int
(package private) int
private int
getRawFromAdjKey
(int adjKey) Only call this if using short values with offsetstatic int
int
private void
private void
private boolean
isAdjKeyOutOfRange
(int adjKey) (package private) boolean
boolean
isValid
(int position) For FSBagIndex low level iterator useiterator()
int
For FSBagIndex low level iterator useint
For FSBagIndex low level iterator useint
moveToNext
(int position) For FSBagIndex low level iterator useprivate int
moveToNextFilled
(int pos) advance pos until it points to a non 0 or is 1 past endint
moveToPrevious
(int position) For FSBagIndex low level iterator useprivate int
moveToPreviousFilled
(int pos) decrement pos until it points to a non 0 or is -1private void
newTable
(int capacity) private void
newTableKeepSize
(int capacity, boolean make4) (package private) static int
nextHigherPowerOf2
(int i) boolean
remove
(int rawKey) mostPositive and mostNegative are not updated for removes.private void
private void
private void
void
int
size()
private void
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.static int
tableSpace
(int numberOfElements, Float factor) int[]
toString()
boolean
boolean
wontExpand
(int n)
-
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 expansionoffset
- - 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
- 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 interfacePositiveIntSet
-
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 interfacePositiveIntSet
- Parameters:
rawKey
- -- Returns:
- true if key is in the set
-
find
public int find(int rawKey) - 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.
-
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 interfacePositiveIntSet
- 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 interfacePositiveIntSet
- Parameters:
rawKey
- the value to remove- Returns:
- true if the key was present
-
size
public int size()- Specified by:
size
in interfacePositiveIntSet
- 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 interfacePositiveIntSet
- 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
- 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()
-