Package org.apache.uima.internal.util
Class OrderedFsSet_array<T extends FeatureStructure>
java.lang.Object
org.apache.uima.internal.util.OrderedFsSet_array<T>
- All Implemented Interfaces:
Iterable<T>
This one is being used, the other one (ending in 2) may be put back into service for large sizes,
later. (7/2017)
A set of FSs, ordered using a comparator Not thread-safe, use on single thread only
Use: set-sorted indexes in UIMA
Entries kept in order in 1 big TOP[]
have ensureCapacity - grows by doubling up to multiplication-limit point, then by addition
Adds optimized:
- maintain high mark, if >, add to end
shifting optimization:
for removes: shift space to back or front, whichever is closer
for adds: shift space from back or front, whichever is closer
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) TOP[]
(package private) int
(package private) int
index of slot at the end which is free, all following slots are free tooprivate static int
private static int
private static int
private static int[]
private final Comparator
<TOP> private final Comparator
<TOP> private static final int
private static final int
private static int[]
private static int[]
private int
private static final boolean
private static int[]
private static int[]
private final int
private StringBuilder
private static final boolean
-
Constructor Summary
ConstructorsConstructorDescriptionOrderedFsSet_array
(Comparator<TOP> comparatorNoTypeWithID, Comparator<TOP> comparatorNoTypeWithoutID) OrderedFsSet_array
(OrderedFsSet_array<T> set, boolean isReadOnly) called to make a read-only copy -
Method Summary
Modifier and TypeMethodDescriptionboolean
boolean
add
(T fs1, Comparator<TOP> comparator) int
binarySearch
(TOP[] _a, int start, int end, TOP fs, Comparator<TOP> _comparatorWithID) int
binarySearchLeftMostEqual
(TOP fs, int start, int end, Comparator<TOP> comparator) Guaranteed by caller to have an equal (withoutID) item, but might be the "end" item searching up to find it.void
clear()
private void
int
find
(TOP fs, Comparator<TOP> comparator) int
findWithoutID
(TOP fs) using NoType because all callers of this have already used the type of fs to select the right index.getAtPos
(int pos) private int
insertSpace
(int insertPosOfAddedSpace, boolean highest) This is called when inserting new items.boolean
isEmpty()
iterator()
private int
move 1/2 of space at front to endprivate int
move 1/2 of space at end to frontboolean
Removes the exactly matching (including ID) FS if present Only called when type of FS matches this index's type, so the NoType comparator is used.int
size()
TOP[]
toArray()
<U> U[]
toArray
(U[] a1) toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
TRACE
private static final boolean TRACE- See Also:
-
MEASURE
private static final boolean MEASURE- See Also:
-
DEFAULT_SIZE
private static final int DEFAULT_SIZE- See Also:
-
DEFAULT_MULTIPLICATION_LIMIT
private static final int DEFAULT_MULTIPLICATION_LIMIT- See Also:
-
multiplication_limit
private final int multiplication_limit- See Also:
-
a
TOP[] a -
a_nextFreeslot
int a_nextFreeslotindex of slot at the end which is free, all following slots are free too -
a_firstUsedslot
int a_firstUsedslot -
comparatorNoTypeWithID
-
comparatorNoTypeWithoutID
-
maxSize
private int maxSize -
tr
-
addToEndCount
private static int addToEndCount -
batchCountHistogram
private static int[] batchCountHistogram -
batchAddCount
private static int batchAddCount -
batchAddTotal
private static int batchAddTotal -
moveSizeHistogram
private static int[] moveSizeHistogram -
movePctHistogram
private static int[] movePctHistogram -
fillHistogram
private static int[] fillHistogram -
iterPctEmptySkip
private static int[] iterPctEmptySkip
-
-
Constructor Details
-
OrderedFsSet_array
public OrderedFsSet_array(Comparator<TOP> comparatorNoTypeWithID, Comparator<TOP> comparatorNoTypeWithoutID) -
OrderedFsSet_array
called to make a read-only copy- Parameters:
set
- -isReadOnly
- -
-
-
Method Details
-
size
public int size() -
isEmpty
public boolean isEmpty() -
add
-
add
- Parameters:
fs1
- item to addcomparator
- either the comparator without type with ID for sorted indexes, or the comparator withoutType without ID for set indexes- Returns:
- true if fs was added (not already present)
-
ensureCapacity
private void ensureCapacity() -
insertSpace
private int insertSpace(int insertPosOfAddedSpace, boolean highest) This is called when inserting new items. May be called to insert at top Side effects: a_firstUsedslot adjusted if insert before first a_nextFreeslot adjusted if after last Rebalancing: normally not done, instead just the smaller distance to front/back things are moved by 1 position. for highest insert when out of space there rebalance by moving 1/2 the space from front to end. for lowest insert when out of space there rebalance by moving 1/2 the space from end to front.- Parameters:
insertPosOfAddedSpace
- position where new item goes 1 to the lefthighest
- true if inserting at end- Returns:
- adjusted insertPosOfAddedSpace, the free spot is just to the left of this position
-
rebalanceMoveSpaceToEnd
private int rebalanceMoveSpaceToEnd()move 1/2 of space at front to end- Returns:
- amount of space shifted to end, amount to decr insertPosOfAddedSpace
-
rebalanceMoveSpaceToFront
private int rebalanceMoveSpaceToFront()move 1/2 of space at end to front- Returns:
- amount of space shifted to end, amount to incr insertPosOfAddedSpace
-
findWithoutID
using NoType because all callers of this have already used the type of fs to select the right index.- Parameters:
fs
- -- Returns:
- -
-
find
-
binarySearch
- Parameters:
_a
- the arraystart
- the index representing the lower bound (inclusive) to search forend
- the index representing the upper bound (exclusive) to search forfs
- - the fs to search for_comparatorWithID
- -- Returns:
- - the index of the found item, or if not found, the (-index) -1 of the position one more than where the item would go
-
remove
Removes the exactly matching (including ID) FS if present Only called when type of FS matches this index's type, so the NoType comparator is used.- Parameters:
o
- the object (must be a FS of the type of this index) to remove- Returns:
- true if it was removed, false if it wasn't in the index
-
clear
public void clear()- See Also:
-
binarySearchLeftMostEqual
Guaranteed by caller to have an equal (withoutID) item, but might be the "end" item searching up to find it.- Parameters:
fs
- - the fs to search forstart
- the index representing the lower bound (inclusive) to search forend
- the index representing the upper bound (exclusive) to search for Not called unless there's one equal item below this.comparator
- the comparator to use (with or without type)- Returns:
- - the index of the leftmost equal (without id) item
-
iterator
- Specified by:
iterator
in interfaceIterable<T extends FeatureStructure>
-
toArray
-
toArray
public <U> U[] toArray(U[] a1) -
getAtPos
-
toString
-