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:
java.lang.Iterable<T>
public class OrderedFsSet_array<T extends FeatureStructure> extends java.lang.Object implements java.lang.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
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
addToEndCount
private static int
batchAddCount
private static int
batchAddTotal
private static int[]
batchCountHistogram
private java.util.Comparator<TOP>
comparatorNoTypeWithID
private java.util.Comparator<TOP>
comparatorNoTypeWithoutID
private static int
DEFAULT_MULTIPLICATION_LIMIT
private static int
DEFAULT_SIZE
private static int[]
fillHistogram
private static int[]
iterPctEmptySkip
private int
maxSize
private static boolean
MEASURE
private static int[]
movePctHistogram
private static int[]
moveSizeHistogram
private int
multiplication_limit
private java.lang.StringBuilder
tr
private static boolean
TRACE
-
Constructor Summary
Constructors Constructor Description OrderedFsSet_array(java.util.Comparator<TOP> comparatorNoTypeWithID, java.util.Comparator<TOP> comparatorNoTypeWithoutID)
OrderedFsSet_array(OrderedFsSet_array<T> set, boolean isReadOnly)
called to make a read-only copy
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(T fs1)
boolean
add(T fs1, java.util.Comparator<TOP> comparator)
int
binarySearch(TOP[] _a, int start, int end, TOP fs, java.util.Comparator<TOP> _comparatorWithID)
int
binarySearchLeftMostEqual(TOP fs, int start, int end, java.util.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
ensureCapacity()
int
find(TOP fs, java.util.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.T
getAtPos(int pos)
private int
insertSpace(int insertPosOfAddedSpace, boolean highest)
This is called when inserting new items.boolean
isEmpty()
java.util.Iterator<T>
iterator()
private int
rebalanceMoveSpaceToEnd()
move 1/2 of space at front to endprivate int
rebalanceMoveSpaceToFront()
move 1/2 of space at end to frontboolean
remove(java.lang.Object o)
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)
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_SIZE
private static final int DEFAULT_SIZE
- See Also:
- Constant Field Values
-
DEFAULT_MULTIPLICATION_LIMIT
private static final int DEFAULT_MULTIPLICATION_LIMIT
- See Also:
- Constant Field Values
-
multiplication_limit
private final int multiplication_limit
- 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
-
comparatorNoTypeWithID
private final java.util.Comparator<TOP> comparatorNoTypeWithID
-
comparatorNoTypeWithoutID
private final java.util.Comparator<TOP> comparatorNoTypeWithoutID
-
maxSize
private int maxSize
-
tr
private java.lang.StringBuilder 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 Detail
-
OrderedFsSet_array
public OrderedFsSet_array(java.util.Comparator<TOP> comparatorNoTypeWithID, java.util.Comparator<TOP> comparatorNoTypeWithoutID)
-
OrderedFsSet_array
public OrderedFsSet_array(OrderedFsSet_array<T> set, boolean isReadOnly)
called to make a read-only copy- Parameters:
set
- -isReadOnly
- -
-
-
Method Detail
-
size
public int size()
-
isEmpty
public boolean isEmpty()
-
add
public boolean add(T fs1)
-
add
public boolean add(T fs1, java.util.Comparator<TOP> comparator)
- 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
public int findWithoutID(TOP fs)
using NoType because all callers of this have already used the type of fs to select the right index.- Parameters:
fs
- -- Returns:
- -
-
binarySearch
public int binarySearch(TOP[] _a, int start, int end, TOP fs, java.util.Comparator<TOP> _comparatorWithID)
- 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
public boolean remove(java.lang.Object o)
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:
Set.clear()
-
binarySearchLeftMostEqual
public int binarySearchLeftMostEqual(TOP fs, int start, int end, java.util.Comparator<TOP> comparator)
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
public java.util.Iterator<T> iterator()
- Specified by:
iterator
in interfacejava.lang.Iterable<T extends FeatureStructure>
-
toArray
public TOP[] toArray()
-
toArray
public <U> U[] toArray(U[] a1)
-
getAtPos
public T getAtPos(int pos)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-