Class OrderedFsSet_array<T extends FeatureStructure>

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

      • DEFAULT_MULTIPLICATION_LIMIT

        private static final int DEFAULT_MULTIPLICATION_LIMIT
        See Also:
        Constant Field Values
      • 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 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,
                        java.util.Comparator<TOP> comparator)
      • binarySearch

        public int binarySearch​(TOP[] _a,
                                int start,
                                int end,
                                TOP fs,
                                java.util.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​(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 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 java.util.Iterator<T> iterator()
        Specified by:
        iterator in interface java.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 class java.lang.Object