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>

public class OrderedFsSet_array2 extends Object implements 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 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_nextFreeslot
      index of slot at the end which is free, all following slots are free too
    • a_firstUsedslot

      int a_firstUsedslot
    • batch

      private final ArrayList<TOP> batch
    • comparatorWithID

      public final Comparator<TOP> comparatorWithID
    • comparatorWithoutID

      public final 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 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 Details

    • OrderedFsSet_array2

      public OrderedFsSet_array2(Comparator<TOP> comparatorWithID, 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 Details

    • comparator

      public Comparator<? super TOP> comparator()
      Specified by:
      comparator in interface SortedSet<TOP>
      See Also:
    • first

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

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

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

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

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

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

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

      public boolean add(TOP fs)
      Note: doesn't implement the return value; always returns true;
      Specified by:
      add in interface Collection<TOP>
      Specified by:
      add in interface Set<TOP>
      See Also:
    • 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 |-| 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 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, 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(Object o)
      Specified by:
      remove in interface Collection<TOP>
      Specified by:
      remove in interface Set<TOP>
      See Also:
    • 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(Collection<?> c)
      Specified by:
      containsAll in interface Collection<TOP>
      Specified by:
      containsAll in interface Set<TOP>
      See Also:
    • addAll

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

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

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

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

      private void clearResets()
    • lower

      public TOP lower(TOP fs)
      Specified by:
      lower in interface NavigableSet<TOP>
      See Also:
    • 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 NavigableSet<TOP>
      See Also:
    • floorPos

      public int floorPos(TOP fs)
      Parameters:
      fs - -
      Returns:
      -
    • ceiling

      public TOP ceiling(TOP fs)
      Specified by:
      ceiling in interface NavigableSet<TOP>
      See Also:
    • ceilingPos

      public int ceilingPos(TOP fs)
      Parameters:
      fs - -
      Returns:
      -
    • higher

      public TOP higher(TOP fs)
      Specified by:
      higher in interface NavigableSet<TOP>
      See Also:
    • 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 NavigableSet<TOP>
      See Also:
    • pollLast

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

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

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

      public Iterator<TOP> descendingIterator()
      Specified by:
      descendingIterator in interface NavigableSet<TOP>
      See Also:
    • subSet

      public NavigableSet<TOP> subSet(TOP fromElement, boolean fromInclusive, TOP toElement, boolean toInclusive)
      Specified by:
      subSet in interface NavigableSet<TOP>
      See Also:
    • headSet

      public NavigableSet<TOP> headSet(TOP toElement, boolean inclusive)
      Specified by:
      headSet in interface NavigableSet<TOP>
      See Also:
    • tailSet

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

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

      public SortedSet<TOP> headSet(TOP toElement)
      Specified by:
      headSet in interface NavigableSet<TOP>
      Specified by:
      headSet in interface SortedSet<TOP>
      See Also:
    • tailSet

      public SortedSet<TOP> tailSet(TOP fromElement)
      Specified by:
      tailSet in interface NavigableSet<TOP>
      Specified by:
      tailSet in interface SortedSet<TOP>
      See Also:
    • getModificationCount

      public int getModificationCount()
    • toString

      public String toString()
      Overrides:
      toString in class Object