Package org.apache.uima.internal.util
Class OrderedFsSet_array2
- java.lang.Object
-
- org.apache.uima.internal.util.OrderedFsSet_array2
-
- All Implemented Interfaces:
java.lang.Iterable<TOP>
,java.util.Collection<TOP>
,java.util.NavigableSet<TOP>
,java.util.Set<TOP>
,java.util.SortedSet<TOP>
public class OrderedFsSet_array2 extends java.lang.Object implements java.util.NavigableSet<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 Classes Modifier and Type Class Description static class
OrderedFsSet_array2.SubSet
This is used in a particular manner: only used to create iterators over that subset -- no insert/delete
-
Field Summary
Fields Modifier and Type Field Description (package private) TOP[]
a
(package private) int
a_firstUsedslot
(package private) int
a_nextFreeslot
index of slot at the end which is free, all following slots are free tooprivate static int
addNotToEndCount
private static int
addToEndCount
private java.util.ArrayList<TOP>
batch
private static int
batchAddCount
private static int
batchAddTotal
private static int[]
batchCountHistogram
java.util.Comparator<TOP>
comparatorWithID
java.util.Comparator<TOP>
comparatorWithoutID
private static int
DEFAULT_MIN_SIZE
private boolean
doingBatchAdds
private static int[]
fillHistogram
private TOP
highest
private static int[]
iterPctEmptySkip
private int
lastRemovedPos
Tricky to maintain.private static int
MAX_DOUBLE_SIZE
private int
maxSize
private static boolean
MEASURE
private static int
MIN_SIZE
private int
modificationCount
private static int[]
movePctHistogram
private static int[]
moveSizeHistogram
private int
nullBlockEnd
private int
nullBlockStart
private int
size
private java.lang.StringBuilder
tr
private static boolean
TRACE
-
Constructor Summary
Constructors Constructor Description OrderedFsSet_array2(java.util.Comparator<TOP> comparatorWithID, java.util.Comparator<TOP> comparatorWithoutID)
OrderedFsSet_array2(OrderedFsSet_array2 set)
copy constructor - not currently used (06/2017)OrderedFsSet_array2(OrderedFsSet_array2 set, boolean isReadOnly)
called to make a read-only copy
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(TOP fs)
Note: doesn't implement the return value; always returns true;boolean
addAll(java.util.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, java.util.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)TOP
ceiling(TOP fs)
int
ceilingPos(TOP fs)
void
clear()
private void
clearResets()
java.util.Comparator<? super TOP>
comparator()
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.boolean
contains(java.lang.Object o)
boolean
containsAll(java.util.Collection<?> c)
java.util.Iterator<TOP>
descendingIterator()
java.util.NavigableSet<TOP>
descendingSet()
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.private void
ensureCapacity(int incr)
private int
find(TOP fs)
Never returns an index to a "null" (deleted) item.private int
findRemaining(TOP fs)
find, within constricted range: start: a_firstUsedslot, end = nullBlockStartTOP
first()
TOP
floor(TOP fs)
int
floorPos(TOP fs)
int
getModificationCount()
private int
getNextSmallerSize(int n)
get next smaller sizejava.util.SortedSet<TOP>
headSet(TOP toElement)
java.util.NavigableSet<TOP>
headSet(TOP toElement, boolean inclusive)
TOP
higher(TOP fs)
int
higherPos(TOP fs)
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()
java.util.Iterator<TOP>
iterator()
TOP
last()
TOP
lower(TOP fs)
int
lowerPos(TOP fs)
TOP
pollFirst()
TOP
pollLast()
void
processBatch()
boolean
remove(java.lang.Object o)
boolean
removeAll(java.util.Collection<?> c)
boolean
retainAll(java.util.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
shrinkCapacity()
int
size()
java.util.NavigableSet<TOP>
subSet(TOP fromElement, boolean fromInclusive, TOP toElement, boolean toInclusive)
java.util.SortedSet<TOP>
subSet(TOP fromElement, TOP toElement)
java.util.SortedSet<TOP>
tailSet(TOP fromElement)
java.util.NavigableSet<TOP>
tailSet(TOP fromElement, boolean inclusive)
java.lang.Object[]
toArray()
<T> T[]
toArray(T[] a1)
java.lang.String
toString()
-
-
-
Field Detail
-
TRACE
private static final boolean TRACE
- See Also:
- Constant Field Values
-
MEASURE
private static final boolean MEASURE
- See Also:
- Constant Field Values
-
DEFAULT_MIN_SIZE
private static final int DEFAULT_MIN_SIZE
- See Also:
- Constant Field Values
-
MAX_DOUBLE_SIZE
private static final int MAX_DOUBLE_SIZE
- See Also:
- Constant Field Values
-
MIN_SIZE
private static final int MIN_SIZE
- See Also:
- Constant Field Values
-
a
TOP[] a
-
a_nextFreeslot
int a_nextFreeslot
index of slot at the end which is free, all following slots are free too
-
a_firstUsedslot
int a_firstUsedslot
-
batch
private final java.util.ArrayList<TOP> batch
-
comparatorWithID
public final java.util.Comparator<TOP> comparatorWithID
-
comparatorWithoutID
public final java.util.Comparator<TOP> comparatorWithoutID
-
size
private int size
-
maxSize
private int maxSize
-
highest
private TOP highest
-
nullBlockStart
private int nullBlockStart
-
nullBlockEnd
private int nullBlockEnd
-
doingBatchAdds
private boolean doingBatchAdds
-
modificationCount
private int modificationCount
-
lastRemovedPos
private int lastRemovedPos
Tricky to maintain. If holes are moved around, this value may need updating
-
tr
private java.lang.StringBuilder 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 Detail
-
OrderedFsSet_array2
public OrderedFsSet_array2(java.util.Comparator<TOP> comparatorWithID, java.util.Comparator<TOP> comparatorWithoutID)
-
OrderedFsSet_array2
public OrderedFsSet_array2(OrderedFsSet_array2 set)
copy constructor - not currently used (06/2017)- Parameters:
set
- the original to be copied
-
OrderedFsSet_array2
public OrderedFsSet_array2(OrderedFsSet_array2 set, boolean isReadOnly)
called to make a read-only copy- Parameters:
set
- -isReadOnly
- -
-
-
Method Detail
-
comparator
public java.util.Comparator<? super TOP> comparator()
- Specified by:
comparator
in interfacejava.util.SortedSet<TOP>
- See Also:
SortedSet.comparator()
-
first
public TOP first()
- Specified by:
first
in interfacejava.util.SortedSet<TOP>
- See Also:
SortedSet.first()
-
last
public TOP last()
- Specified by:
last
in interfacejava.util.SortedSet<TOP>
- See Also:
SortedSet.last()
-
size
public int size()
-
isEmpty
public boolean isEmpty()
-
contains
public boolean contains(java.lang.Object o)
-
toArray
public java.lang.Object[] toArray()
-
toArray
public <T> T[] toArray(T[] a1)
-
add
public boolean add(TOP fs)
Note: doesn't implement the return value; always returns true;
-
addNewHighest
private void addNewHighest(TOP fs)
-
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
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 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 |-| << block shifted uuuuuuuuuuuuuuufffffuuuuuuuuuuuuuuuuuuuuuuuuuuu ^ insert point after |-| << 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
private int find(TOP fs)
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
private int findRemaining(TOP fs)
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
private int binarySearch(TOP fs)
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, java.util.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
public boolean remove(java.lang.Object o)
-
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
public boolean containsAll(java.util.Collection<?> c)
-
addAll
public boolean addAll(java.util.Collection<? extends TOP> c)
-
retainAll
public boolean retainAll(java.util.Collection<?> c)
-
removeAll
public boolean removeAll(java.util.Collection<?> c)
-
clear
public void clear()
-
clearResets
private void clearResets()
-
lower
public TOP lower(TOP fs)
- Specified by:
lower
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.lower(Object)
-
lowerPos
public int lowerPos(TOP fs)
- Parameters:
fs
- element to test- Returns:
- pos of greatest element less that fs or -1 if no such
-
floor
public TOP floor(TOP fs)
- Specified by:
floor
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.floor(Object)
-
floorPos
public int floorPos(TOP fs)
- Parameters:
fs
- -- Returns:
- -
-
ceiling
public TOP ceiling(TOP fs)
- Specified by:
ceiling
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.ceiling(Object)
-
ceilingPos
public int ceilingPos(TOP fs)
- Parameters:
fs
- -- Returns:
- -
-
higher
public TOP higher(TOP fs)
- Specified by:
higher
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.higher(Object)
-
higherPos
public int higherPos(TOP fs)
- Parameters:
fs
- the Feature Structure to use for positioning- Returns:
- the position that's higher
-
pollFirst
public TOP pollFirst()
- Specified by:
pollFirst
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.pollFirst()
-
pollLast
public TOP pollLast()
- Specified by:
pollLast
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.pollLast()
-
iterator
public java.util.Iterator<TOP> iterator()
-
descendingSet
public java.util.NavigableSet<TOP> descendingSet()
- Specified by:
descendingSet
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.descendingSet()
-
descendingIterator
public java.util.Iterator<TOP> descendingIterator()
- Specified by:
descendingIterator
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.descendingIterator()
-
subSet
public java.util.NavigableSet<TOP> subSet(TOP fromElement, boolean fromInclusive, TOP toElement, boolean toInclusive)
- Specified by:
subSet
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.subSet(Object, boolean, Object, boolean)
-
headSet
public java.util.NavigableSet<TOP> headSet(TOP toElement, boolean inclusive)
- Specified by:
headSet
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.headSet(Object, boolean)
-
tailSet
public java.util.NavigableSet<TOP> tailSet(TOP fromElement, boolean inclusive)
- Specified by:
tailSet
in interfacejava.util.NavigableSet<TOP>
- See Also:
NavigableSet.tailSet(Object, boolean)
-
getModificationCount
public int getModificationCount()
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-