Package org.apache.uima.internal.util
Class PositiveIntSet_impl
- java.lang.Object
-
- org.apache.uima.internal.util.PositiveIntSet_impl
-
- All Implemented Interfaces:
PositiveIntSet
public class PositiveIntSet_impl extends Object implements PositiveIntSet
An set of non-zero integers, ability to iterate over them (possibly in a sorted way), with O(1) operations for adding, removing, and testing for contains. Optimized for adding mostly increasing integers (with some space for less-than-first-one-added). - major uses: indexes of Feature Structures. Optimize for small sets Graceful degradation for completely random integer operations on large sets; keep O(1) operations, at the expense of extra space (< 3 x size). Uses several different representations depending on the range of ints stored and the total number of ints stored. Sizes: Tiny, medium, large Ranges: semi-knowable, unknowable; if semi-knowable, dense, small-range (< 65K), large-range For all sizes, if dense, use IntBitSet (with offset) else For large, (implies large-range, too) use IntHashSet For medium, if small-range < 65K, use IntHashSet with offset else use IntHashSet Arrange switching between representations to occur infrequently, especially as cost of switching (size) grows Arrange checking for switching to occur infrequently, taking into account how underlying data structures grow (which is often by doubling) Switch when adding new member(s) if alternative representation is sufficiently smaller
-
-
Field Summary
Fields Modifier and Type Field Description static int[]
EMPTY_INT_ARRAY
-
Constructor Summary
Constructors Constructor Description PositiveIntSet_impl()
PositiveIntSet_impl(int initialSize, int estMin, int estMax)
Set up a Positive Bit Set
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(int key)
void
bulkAddTo(IntVector v)
add all elements in this set to the IntVector v as a bulk operationvoid
clear()
remove all members of the setboolean
contains(int key)
int
find(int element)
int
get(int position)
For FSBagIndex low level iterator use DOESN"T WORK WITH INCREMENTING position VALUESIntListIterator
getOrderedIterator()
IntListIterator
getUnorderedIterator()
boolean
isValid(int position)
For FSBagIndex low level iterator useIntListIterator
iterator()
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 useboolean
remove(int key)
int
size()
int[]
toIntArray()
int[]
toOrderedIntArray()
String
toString()
int[]
toUnorderedIntArray()
-
-
-
Constructor Detail
-
PositiveIntSet_impl
public PositiveIntSet_impl()
-
PositiveIntSet_impl
public PositiveIntSet_impl(int initialSize, int estMin, int estMax)
Set up a Positive Bit Set- Parameters:
initialSize
- - if 0, don't allocate yet, wait for first add. If isBitSetDense, then this number is interpreted as the first int to be added, typically with an offset. The next two params are used only if initialSize is not 0.estMin
- - the estimated minimum int value to be addedestMax
- - the estimated max int value to be added
-
-
Method Detail
-
iterator
public IntListIterator iterator()
- Specified by:
iterator
in interfacePositiveIntSet
- Returns:
- an iterator (may be ordered or unordered) over the members of the set
-
getUnorderedIterator
public IntListIterator getUnorderedIterator()
-
getOrderedIterator
public IntListIterator getOrderedIterator()
-
clear
public void clear()
Description copied from interface:PositiveIntSet
remove all members of the set- Specified by:
clear
in interfacePositiveIntSet
-
contains
public boolean contains(int key)
- Specified by:
contains
in interfacePositiveIntSet
- Parameters:
key
- -- Returns:
- true if key is in the set
-
find
public int find(int element)
- Specified by:
find
in interfacePositiveIntSet
- Parameters:
element
- 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.
-
add
public boolean add(int key)
- Specified by:
add
in interfacePositiveIntSet
- Parameters:
key
- -- Returns:
- true if this set did not already contain the specified element
-
remove
public boolean remove(int key)
- Specified by:
remove
in interfacePositiveIntSet
- Parameters:
key
- -- Returns:
- true if the set had this element before the remove
-
size
public int size()
- Specified by:
size
in interfacePositiveIntSet
- Returns:
- number of elements in the set
-
toUnorderedIntArray
public int[] toUnorderedIntArray()
-
toOrderedIntArray
public int[] toOrderedIntArray()
-
get
public int get(int position)
Description copied from interface:PositiveIntSet
For FSBagIndex low level iterator use DOESN"T WORK WITH INCREMENTING position VALUES- Specified by:
get
in interfacePositiveIntSet
- Parameters:
position
- - 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 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
-
-