Package org.apache.uima.internal.util
Class OrderedFsSet_array2
java.lang.Object
org.apache.uima.internal.util.OrderedFsSet_array2
- All Implemented Interfaces:
Iterable<TOP>
,Collection<TOP>
,NavigableSet<TOP>
,Set<TOP>
,SortedSet<TOP>
This one not in current use Maybe be put back into service when the array becomes large and it
starts outperforming the other
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 ArrayList
Adds optimized:
- maintain high mark, if >, add to end
- batch adds other than above
-- do when reference needed
-- sort the to be added
- to add to pos p, shift elements in p to higher, insert
shifting optimization:
removes replace element with null
shift until hit null
nullBlock - a group of nulls (free space) together
- might be created by a batch add which
adds a block of space all at once
- might arise from encountering 1 or more "nulls" created
by removes
- id by nullBlockStart (inclusive) and nullBlockEnd (exclusive)
bitset: 1 for avail slot
used to compute move for array copy
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
This is used in a particular manner: only used to create iterators over that subset -- no insert/delete -
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 static int[]
final Comparator
<TOP> final Comparator
<TOP> private static final int
private boolean
private static int[]
private TOP
private static int[]
private int
Tricky to maintain.private static final int
private int
private static final boolean
private static final int
private int
private static int[]
private static int[]
private int
private int
private int
private StringBuilder
private static final boolean
-
Constructor Summary
ConstructorsConstructorDescriptionOrderedFsSet_array2
(Comparator<TOP> comparatorWithID, Comparator<TOP> comparatorWithoutID) copy constructor - not currently used (06/2017)OrderedFsSet_array2
(OrderedFsSet_array2 set, boolean isReadOnly) called to make a read-only copy -
Method Summary
Modifier and TypeMethodDescriptionboolean
Note: doesn't implement the return value; always returns true;boolean
addAll
(Collection<? extends TOP> c) private void
addNewHighest
(TOP fs) private int
binarySearch
(TOP fs) Special version of binary search that ignores null valuesstatic int
binarySearch
(TOP fs, int start, int end, TOP[] _a, int _nullBlockStart, int _nullBlockEnd, Comparator<TOP> _comparatorWithID) At the start, the start and end positions are guaranteed to refer to non-null entries But during operation, lower may refer to "null" entries (upper always non-null)int
ceilingPos
(TOP fs) void
clear()
private void
Comparator
<? super TOP> private void
When the main array between the first used slot and the next free slot has too many nulls representing removed items, scan and gc them.boolean
boolean
containsAll
(Collection<?> c) private void
Because multiple threads can be "reading" the CAS and using iterators, the sync must insure that the setting of batch.size() to 0 occurs after all the adding is done.private void
ensureCapacity
(int incr) private int
Never returns an index to a "null" (deleted) item.private int
findRemaining
(TOP fs) find, within constricted range: start: a_firstUsedslot, end = nullBlockStartfirst()
int
int
private int
getNextSmallerSize
(int n) get next smaller sizeint
private void
incrSize()
private void
insertItem
(int indexToUpdate, TOP itemToAdd) side effects: increment size reset a_firstUsedslot if adding in front ( a_nextFreeslot not updated, because this method only called to inserting before end ) nullBlockEnd reduced conditionally lastRemovedPos is reset if that position is usedprivate int
insertSpace
(int positionToInsert, int origNbrNewSlots) This is called when inserting new items from the batch.boolean
isEmpty()
iterator()
last()
int
pollLast()
void
boolean
boolean
removeAll
(Collection<?> c) boolean
retainAll
(Collection<?> c) private int
shiftFreespaceDown
(int insertPoint, int nbrNewSlots) Shift a block of free space lower in the array.private int
shiftFreespaceUp
(int newInsertPoint, int nbrNewSlots) Shift a block of free space higher in the array.private boolean
int
size()
Object[]
toArray()
<T> T[]
toArray
(T[] a1) toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream
Methods inherited from interface java.util.SortedSet
spliterator
-
Field Details
-
TRACE
private static final boolean TRACE- See Also:
-
MEASURE
private static final boolean MEASURE- See Also:
-
DEFAULT_MIN_SIZE
private static final int DEFAULT_MIN_SIZE- See Also:
-
MAX_DOUBLE_SIZE
private static final int MAX_DOUBLE_SIZE- See Also:
-
MIN_SIZE
private static final int MIN_SIZE- 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 -
batch
-
comparatorWithID
-
comparatorWithoutID
-
size
private int size -
maxSize
private int maxSize -
highest
-
nullBlockStart
private int nullBlockStart -
nullBlockEnd
private int nullBlockEnd -
doingBatchAdds
private boolean doingBatchAdds -
modificationCount
private int modificationCount -
lastRemovedPos
private int lastRemovedPosTricky to maintain. If holes are moved around, this value may need updating -
tr
-
addToEndCount
private static int addToEndCount -
addNotToEndCount
private static int addNotToEndCount -
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_array2
-
OrderedFsSet_array2
copy constructor - not currently used (06/2017)- Parameters:
set
- the original to be copied
-
OrderedFsSet_array2
called to make a read-only copy- Parameters:
set
- -isReadOnly
- -
-
-
Method Details
-
comparator
- Specified by:
comparator
in interfaceSortedSet<TOP>
- See Also:
-
first
-
last
-
size
public int size() -
isEmpty
public boolean isEmpty() -
contains
-
toArray
-
toArray
public <T> T[] toArray(T[] a1) -
add
Note: doesn't implement the return value; always returns true; -
addNewHighest
-
incrSize
private void incrSize() -
ensureCapacity
private void ensureCapacity(int incr) -
shrinkCapacity
private boolean shrinkCapacity() -
getNextSmallerSize
private int getNextSmallerSize(int n) get next smaller size- Parameters:
n
- number of increments- Returns:
- the size
-
processBatch
public void processBatch() -
doProcessBatch
private void doProcessBatch()Because multiple threads can be "reading" the CAS and using iterators, the sync must insure that the setting of batch.size() to 0 occurs after all the adding is done. This keeps other threads blocked until the batch is completely processed. -
insertItem
side effects: increment size reset a_firstUsedslot if adding in front ( a_nextFreeslot not updated, because this method only called to inserting before end ) nullBlockEnd reduced conditionally lastRemovedPos is reset if that position is used- Parameters:
indexToUpdate
- - the index in the array to update with the item to additemToAdd
- -
-
insertSpace
private int insertSpace(int positionToInsert, int origNbrNewSlots) This is called when inserting new items from the batch. It does a bulk insert of space for all the items in the batch. Attempts to move a small amount with a multi-part strategy: - make use of existing "nulls" at the insert spot -- if not enough, --- if just need one more, compute distance from 3 possible source: -- front, end, and lastRemovedPos (if not already included in existing "nulls") combine with a new additional block that is moved down from the top. - make use of both beginning and end free space. If there is already a "null" at the insert spot, use that space. - if there are enough nulls, return Sets (as side effect) nullBlockStart and nullBlockEnd The setting includes all of the nulls, both what might have been present at the insert spot and any added new ones. nullBlockStart refs a null, nullBlockEnd refs a non-null (or null if things are being inserted at the end) position - the insert position- Parameters:
positionToInsert
- position containing a value, to free up by moving the current free block so that the last free element is at that (adjusted up) position.nbrNewSlots
-- Returns:
- adjusted positionToInsert, the free spot is just to the left of this position
-
shiftFreespaceDown
private int shiftFreespaceDown(int insertPoint, int nbrNewSlots) Shift a block of free space lower in the array. This is done by shifting the space at the insert point for length = start of free block - insert point to the right by the nbrNewSlots and then resetting (filling) the freed up space with null Example: u = used, f = free space before |--| uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuffffffffuuuuuuu ^ insert point after |--| uuuuuuuuuuuuuuuuuuuuuuuuuuuuffffffffuuuuuuuuuuu ^ insert point before |------------------------------| uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuffffffffuuuuuuu ^ insert point after |------------------------------| ffffffffuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point before |------------------------------| ffffuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuffffffffuuuuuuu ^ insert point after |------------------------------| ffffffffffffuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point move up by nbrNewSlots length to move = nullBlockStart - insert point new insert point is nbrOfFreeSlots higher (this points to a filled spot, prev spot is free) fill goes from original newInsertPoint, for min(nbrNewSlots, length of move) There may be nulls already at the insert point, or encountered along the way. - nulls along the way are kept, unchanged - nulls at the insert point are incorporated; the freespace added is combined (need to verify) hidden param: nullBlockStart side effect: lastRemovedPosition maybe updated- Parameters:
insertPoint
- index of slot array, currently occupied, where an item is to be set intonbrNewSlots
- - the size of the inserted space- Returns:
- the updated insert point, now moved up
-
shiftFreespaceUp
private int shiftFreespaceUp(int newInsertPoint, int nbrNewSlots) Shift a block of free space higher in the array. This is done by shifting the space at the insert point of length = insert point - (end+1) of free block to the left by the nbrNewSlots and then resetting (filling) the freed up space with null Example: u = used, f = free space before |-| invalid input: '<'invalid input: '<' block shifted uuuuuuuuuuuuuuufffffuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point after |-| invalid input: '<'invalid input: '<' block shifted uuuuuuuuuuuuuuuuuufffffuuuuuuuuuuuuuuuuuuu ^ insert point before |----| uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuffffuuuuuuu ^ insert point note: insert point is never beyond last because those are added immediately after |----| uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuffffu ^ insert point before |--| uuuuuuuuuuuufuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point after |--| uuuuuuuuuuuuuuuufuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point |--------| before ffffuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point |--------| uuuuuuuuuuffffuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point move down by nbrNewSlots length to move = insert point - null block end (which is 1 plus index of last free) new insert point is the same as the old one (this points to a filled spot, prev spot is free) fill goes from original null block end, for min(nbrNewSlots, length of move) hidden param: nullBlock Start, nullBlockEnd = 1 past end of last free slot- Parameters:
newInsertPoint
- index of slot array, currently occupied, where an item is to be set intonbrNewSlots
- - the size of the inserted space- Returns:
- the updated insert point, now moved up
-
find
Never returns an index to a "null" (deleted) item. If all items are LT key, returns - size - 1- Parameters:
fs
- the key- Returns:
- the lowest position whose item is equal to or greater than fs; if not equal, the item's position is returned as -insertionPoint - 1. If the key is greater than all elements, return -size - 1).
-
findRemaining
find, within constricted range: start: a_firstUsedslot, end = nullBlockStart- Parameters:
fs
- -- Returns:
- - the slot matching, or the one just above, if none match, but limited to the nullBlockStart position. If the answer is not found, and the insert position is the nullBlockStart, then return the nullBlockEnd as the position (using the not-found encoding).
-
binarySearch
Special version of binary search that ignores null values- Parameters:
fs
- the value to look for- Returns:
- the position whose non-null value is equal to fs, or is gt fs (in which case, return (-pos) - 1)
-
binarySearch
public static int binarySearch(TOP fs, int start, int end, TOP[] _a, int _nullBlockStart, int _nullBlockEnd, Comparator<TOP> _comparatorWithID) At the start, the start and end positions are guaranteed to refer to non-null entries But during operation, lower may refer to "null" entries (upper always non-null)- 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_a
- the array_nullBlockStart
- inclusive_nullBlockEnd
- exclusive_comparatorWithID
- -- Returns:
- - the index of the found item, or if not found, the (-index) -1 of the poosition one more than where the item would go
-
remove
-
compressOutRemoves
private void compressOutRemoves()When the main array between the first used slot and the next free slot has too many nulls representing removed items, scan and gc them. assumes: first used slot is not null, nextFreeslot - 1 is not null -
containsAll
- Specified by:
containsAll
in interfaceCollection<TOP>
- Specified by:
containsAll
in interfaceSet<TOP>
- See Also:
-
addAll
-
retainAll
-
removeAll
-
clear
public void clear() -
clearResets
private void clearResets() -
lower
- Specified by:
lower
in interfaceNavigableSet<TOP>
- See Also:
-
lowerPos
- Parameters:
fs
- element to test- Returns:
- pos of greatest element less that fs or -1 if no such
-
floor
- Specified by:
floor
in interfaceNavigableSet<TOP>
- See Also:
-
floorPos
- Parameters:
fs
- -- Returns:
- -
-
ceiling
- Specified by:
ceiling
in interfaceNavigableSet<TOP>
- See Also:
-
ceilingPos
- Parameters:
fs
- -- Returns:
- -
-
higher
- Specified by:
higher
in interfaceNavigableSet<TOP>
- See Also:
-
higherPos
- Parameters:
fs
- the Feature Structure to use for positioning- Returns:
- the position that's higher
-
pollFirst
- Specified by:
pollFirst
in interfaceNavigableSet<TOP>
- See Also:
-
pollLast
- Specified by:
pollLast
in interfaceNavigableSet<TOP>
- See Also:
-
iterator
-
descendingSet
- Specified by:
descendingSet
in interfaceNavigableSet<TOP>
- See Also:
-
descendingIterator
- Specified by:
descendingIterator
in interfaceNavigableSet<TOP>
- See Also:
-
subSet
public NavigableSet<TOP> subSet(TOP fromElement, boolean fromInclusive, TOP toElement, boolean toInclusive) - Specified by:
subSet
in interfaceNavigableSet<TOP>
- See Also:
-
headSet
- Specified by:
headSet
in interfaceNavigableSet<TOP>
- See Also:
-
tailSet
- Specified by:
tailSet
in interfaceNavigableSet<TOP>
- See Also:
-
subSet
-
headSet
-
tailSet
-
getModificationCount
public int getModificationCount() -
toString
-