Class PositiveIntSet_impl

  • All Implemented Interfaces:
    PositiveIntSet

    public class PositiveIntSet_impl
    extends Object
    implements PositiveIntSet
    An set of non-zero integers, ability to iterate over them (possibly in a sorted way), with O(1) operations for adding, removing, and testing for contains. Optimized for adding mostly increasing integers (with some space for less-than-first-one-added). - major uses: indexes of Feature Structures. Optimize for small sets Graceful degradation for completely random integer operations on large sets; keep O(1) operations, at the expense of extra space (< 3 x size). Uses several different representations depending on the range of ints stored and the total number of ints stored. Sizes: Tiny, medium, large Ranges: semi-knowable, unknowable; if semi-knowable, dense, small-range (< 65K), large-range For all sizes, if dense, use IntBitSet (with offset) else For large, (implies large-range, too) use IntHashSet For medium, if small-range < 65K, use IntHashSet with offset else use IntHashSet Arrange switching between representations to occur infrequently, especially as cost of switching (size) grows Arrange checking for switching to occur infrequently, taking into account how underlying data structures grow (which is often by doubling) Switch when adding new member(s) if alternative representation is sufficiently smaller
    • Field Detail

      • EMPTY_INT_ARRAY

        public static final int[] EMPTY_INT_ARRAY
    • Constructor Detail

      • PositiveIntSet_impl

        public PositiveIntSet_impl()
      • PositiveIntSet_impl

        public PositiveIntSet_impl​(int initialSize,
                                   int estMin,
                                   int estMax)
        Set up a Positive Bit Set
        Parameters:
        initialSize - - if 0, don't allocate yet, wait for first add. If isBitSetDense, then this number is interpreted as the first int to be added, typically with an offset. The next two params are used only if initialSize is not 0.
        estMin - - the estimated minimum int value to be added
        estMax - - the estimated max int value to be added
    • Method Detail

      • contains

        public boolean contains​(int key)
        Specified by:
        contains in interface PositiveIntSet
        Parameters:
        key - -
        Returns:
        true if key is in the set
      • find

        public int find​(int element)
        Specified by:
        find in interface PositiveIntSet
        Parameters:
        element - an item which may be in the set
        Returns:
        -1 if the item is not in the set, or a position value that can be used with iterators to start at that item.
      • add

        public boolean add​(int key)
        Specified by:
        add in interface PositiveIntSet
        Parameters:
        key - -
        Returns:
        true if this set did not already contain the specified element
      • remove

        public boolean remove​(int key)
        Specified by:
        remove in interface PositiveIntSet
        Parameters:
        key - -
        Returns:
        true if the set had this element before the remove
      • size

        public int size()
        Specified by:
        size in interface PositiveIntSet
        Returns:
        number of elements in the set
      • toUnorderedIntArray

        public int[] toUnorderedIntArray()
      • toOrderedIntArray

        public int[] toOrderedIntArray()
      • get

        public int get​(int position)
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use DOESN"T WORK WITH INCREMENTING position VALUES
        Specified by:
        get in interface PositiveIntSet
        Parameters:
        position - - get the element at this position. This is for iterator use only, and is not related to any key
        Returns:
        the element
      • moveToFirst

        public int moveToFirst()
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use
        Specified by:
        moveToFirst in interface PositiveIntSet
        Returns:
        the position of the first element, or -1;
      • moveToLast

        public int moveToLast()
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use
        Specified by:
        moveToLast in interface PositiveIntSet
        Returns:
        the position of the last element, or -1;
      • moveToNext

        public int moveToNext​(int position)
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use
        Specified by:
        moveToNext in interface PositiveIntSet
        Parameters:
        position - -
        Returns:
        the position of the next element, or -1;
      • moveToPrevious

        public int moveToPrevious​(int position)
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use
        Specified by:
        moveToPrevious in interface PositiveIntSet
        Parameters:
        position - -
        Returns:
        the position of the next element, or -1;
      • isValid

        public boolean isValid​(int position)
        Description copied from interface: PositiveIntSet
        For FSBagIndex low level iterator use
        Specified by:
        isValid in interface PositiveIntSet
        Parameters:
        position - -
        Returns:
        true if the position is between the first and last element inclusive.
      • bulkAddTo

        public void bulkAddTo​(IntVector v)
        Description copied from interface: PositiveIntSet
        add all elements in this set to the IntVector v as a bulk operation
        Specified by:
        bulkAddTo in interface PositiveIntSet
        Parameters:
        v - - to be added to
      • toIntArray

        public int[] toIntArray()
        Specified by:
        toIntArray in interface PositiveIntSet
        Returns:
        the set as an arbitrarily ordered int array