Class OrderedFsSet_array<T extends FeatureStructure>

java.lang.Object
org.apache.uima.internal.util.OrderedFsSet_array<T>
All Implemented Interfaces:
Iterable<T>

public class OrderedFsSet_array<T extends FeatureStructure> extends Object implements 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 Details

    • TRACE

      private static final boolean TRACE
      See Also:
    • MEASURE

      private static final boolean MEASURE
      See Also:
    • DEFAULT_SIZE

      private static final int DEFAULT_SIZE
      See Also:
    • DEFAULT_MULTIPLICATION_LIMIT

      private static final int DEFAULT_MULTIPLICATION_LIMIT
      See Also:
    • multiplication_limit

      private final int multiplication_limit
      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
    • comparatorNoTypeWithID

      private final Comparator<TOP> comparatorNoTypeWithID
    • comparatorNoTypeWithoutID

      private final Comparator<TOP> comparatorNoTypeWithoutID
    • maxSize

      private int maxSize
    • tr

      private 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 Details

    • OrderedFsSet_array

      public OrderedFsSet_array(Comparator<TOP> comparatorNoTypeWithID, 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 Details

    • size

      public int size()
    • isEmpty

      public boolean isEmpty()
    • add

      public boolean add(T fs1)
    • add

      public boolean add(T fs1, Comparator<TOP> comparator)
      Parameters:
      fs1 - item to add
      comparator - 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 left
      highest - 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:
      -
    • find

      public int find(TOP fs, Comparator<TOP> comparator)
    • binarySearch

      public int binarySearch(TOP[] _a, int start, int end, TOP fs, Comparator<TOP> _comparatorWithID)
      Parameters:
      _a - the array
      start - the index representing the lower bound (inclusive) to search for
      end - the index representing the upper bound (exclusive) to search for
      fs - - 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(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:
    • binarySearchLeftMostEqual

      public int binarySearchLeftMostEqual(TOP fs, int start, int end, 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 for
      start - the index representing the lower bound (inclusive) to search for
      end - 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 Iterator<T> iterator()
      Specified by:
      iterator in interface Iterable<T extends FeatureStructure>
    • toArray

      public TOP[] toArray()
    • toArray

      public <U> U[] toArray(U[] a1)
    • getAtPos

      public T getAtPos(int pos)
    • toString

      public String toString()
      Overrides:
      toString in class Object