Class 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
    • Field Detail

      • 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 interface java.util.SortedSet<TOP>
        See Also:
        SortedSet.comparator()
      • first

        public TOP first()
        Specified by:
        first in interface java.util.SortedSet<TOP>
        See Also:
        SortedSet.first()
      • last

        public TOP last()
        Specified by:
        last in interface java.util.SortedSet<TOP>
        See Also:
        SortedSet.last()
      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<TOP>
        Specified by:
        size in interface java.util.Set<TOP>
        See Also:
        Set.size()
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<TOP>
        Specified by:
        isEmpty in interface java.util.Set<TOP>
        See Also:
        Set.isEmpty()
      • contains

        public boolean contains​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<TOP>
        Specified by:
        contains in interface java.util.Set<TOP>
        See Also:
        Set.contains(Object)
      • toArray

        public java.lang.Object[] toArray()
        Specified by:
        toArray in interface java.util.Collection<TOP>
        Specified by:
        toArray in interface java.util.Set<TOP>
        See Also:
        Set.toArray()
      • toArray

        public <T> T[] toArray​(T[] a1)
        Specified by:
        toArray in interface java.util.Collection<TOP>
        Specified by:
        toArray in interface java.util.Set<TOP>
        See Also:
        Set.toArray(Object[])
      • add

        public boolean add​(TOP fs)
        Note: doesn't implement the return value; always returns true;
        Specified by:
        add in interface java.util.Collection<TOP>
        Specified by:
        add in interface java.util.Set<TOP>
        See Also:
        Set.add(Object)
      • 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 add
        itemToAdd - -
      • 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 into
        nbrNewSlots - - 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 into
        nbrNewSlots - - 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 for
        start - the index representing the lower bound (inclusive) to search for
        end - 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)
        Specified by:
        remove in interface java.util.Collection<TOP>
        Specified by:
        remove in interface java.util.Set<TOP>
        See Also:
        Set.remove(Object)
      • 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)
        Specified by:
        containsAll in interface java.util.Collection<TOP>
        Specified by:
        containsAll in interface java.util.Set<TOP>
        See Also:
        Set.containsAll(Collection)
      • addAll

        public boolean addAll​(java.util.Collection<? extends TOP> c)
        Specified by:
        addAll in interface java.util.Collection<TOP>
        Specified by:
        addAll in interface java.util.Set<TOP>
        See Also:
        Set.addAll(Collection)
      • retainAll

        public boolean retainAll​(java.util.Collection<?> c)
        Specified by:
        retainAll in interface java.util.Collection<TOP>
        Specified by:
        retainAll in interface java.util.Set<TOP>
        See Also:
        Set.retainAll(Collection)
      • removeAll

        public boolean removeAll​(java.util.Collection<?> c)
        Specified by:
        removeAll in interface java.util.Collection<TOP>
        Specified by:
        removeAll in interface java.util.Set<TOP>
        See Also:
        Set.removeAll(Collection)
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<TOP>
        Specified by:
        clear in interface java.util.Set<TOP>
        See Also:
        Set.clear()
      • clearResets

        private void clearResets()
      • lower

        public TOP lower​(TOP fs)
        Specified by:
        lower in interface java.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 interface java.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 interface java.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 interface java.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 interface java.util.NavigableSet<TOP>
        See Also:
        NavigableSet.pollFirst()
      • pollLast

        public TOP pollLast()
        Specified by:
        pollLast in interface java.util.NavigableSet<TOP>
        See Also:
        NavigableSet.pollLast()
      • iterator

        public java.util.Iterator<TOP> iterator()
        Specified by:
        iterator in interface java.util.Collection<TOP>
        Specified by:
        iterator in interface java.lang.Iterable<TOP>
        Specified by:
        iterator in interface java.util.NavigableSet<TOP>
        Specified by:
        iterator in interface java.util.Set<TOP>
        See Also:
        Iterable.iterator()
      • descendingSet

        public java.util.NavigableSet<TOP> descendingSet()
        Specified by:
        descendingSet in interface java.util.NavigableSet<TOP>
        See Also:
        NavigableSet.descendingSet()
      • descendingIterator

        public java.util.Iterator<TOP> descendingIterator()
        Specified by:
        descendingIterator in interface java.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 interface java.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 interface java.util.NavigableSet<TOP>
        See Also:
        NavigableSet.headSet(Object, boolean)
      • tailSet

        public java.util.NavigableSet<TOP> tailSet​(TOP fromElement,
                                                   boolean inclusive)
        Specified by:
        tailSet in interface java.util.NavigableSet<TOP>
        See Also:
        NavigableSet.tailSet(Object, boolean)
      • subSet

        public java.util.SortedSet<TOP> subSet​(TOP fromElement,
                                               TOP toElement)
        Specified by:
        subSet in interface java.util.NavigableSet<TOP>
        Specified by:
        subSet in interface java.util.SortedSet<TOP>
        See Also:
        NavigableSet.subSet(Object, Object)
      • headSet

        public java.util.SortedSet<TOP> headSet​(TOP toElement)
        Specified by:
        headSet in interface java.util.NavigableSet<TOP>
        Specified by:
        headSet in interface java.util.SortedSet<TOP>
        See Also:
        NavigableSet.headSet(Object)
      • tailSet

        public java.util.SortedSet<TOP> tailSet​(TOP fromElement)
        Specified by:
        tailSet in interface java.util.NavigableSet<TOP>
        Specified by:
        tailSet in interface java.util.SortedSet<TOP>
        See Also:
        NavigableSet.tailSet(Object)
      • getModificationCount

        public int getModificationCount()
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object