Class IndexSupport


  • final class IndexSupport
    extends java.lang.Object
    Support for creating UpdatingInterval implementations and validating indices.
    Since:
    1.2
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int INSERTION_SORT_SIZE
      The upper threshold to use a modified insertion sort to find unique indices.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private IndexSupport()
      No instances.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static int ceilLog2​(int x)
      Compute ceil(log2(x)).
      (package private) static void checkFromToIndex​(int fromIndex, int toIndex, int length)
      Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is within the bounds of range from 0 (inclusive) to length (exclusive).
      (package private) static void checkIndex​(int fromIndex, int toIndex, int index)
      Checks if the index is within the half-open interval [fromIndex, toIndex).
      (package private) static void checkIndices​(int fromIndex, int toIndex, int[] k)
      Checks if the index is within the half-open interval [fromIndex, toIndex).
      private static int compressDuplicates​(int[] data, int n)
      Compress duplicates in the ascending data.
      (package private) static int countIndices​(UpdatingInterval keys, int n)
      Count the number of indices.
      (package private) static UpdatingInterval createUpdatingInterval​(int left, int right, int[] k, int n)
      Returns an interval that covers the specified indices k.
      private static boolean isAscending​(int[] data, int n)
      Test the data is in ascending order: data[i] <= data[i+1] for all i.
      private static java.lang.String msgIndexOutOfBounds​(int fromIndex, int toIndex, int index)
      Format a message when index is not within range [from, to).
      private static java.lang.String msgRangeOutOfBounds​(int fromIndex, int toIndex, int length)
      Format a message when range [from, to) is not entirely within the length.
      private static UpdatingInterval newUpdatingInterval​(int[] k, int n)
      Returns an interval that covers the specified indices k.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • INSERTION_SORT_SIZE

        private static final int INSERTION_SORT_SIZE
        The upper threshold to use a modified insertion sort to find unique indices.
        See Also:
        Constant Field Values
    • Constructor Detail

      • IndexSupport

        private IndexSupport()
        No instances.
    • Method Detail

      • createUpdatingInterval

        static UpdatingInterval createUpdatingInterval​(int left,
                                                       int right,
                                                       int[] k,
                                                       int n)
        Returns an interval that covers the specified indices k.
        Parameters:
        left - Lower bound of data (inclusive).
        right - Upper bound of data (inclusive).
        k - Indices.
        n - Count of indices (must be strictly positive).
        Returns:
        the interval
        Throws:
        java.lang.IndexOutOfBoundsException - if any index k is not within the sub-range [left, right]
      • isAscending

        private static boolean isAscending​(int[] data,
                                           int n)
        Test the data is in ascending order: data[i] <= data[i+1] for all i. Data is assumed to be at least length 1.
        Parameters:
        data - Data.
        n - Length of data.
        Returns:
        true if ascending
      • compressDuplicates

        private static int compressDuplicates​(int[] data,
                                              int n)
        Compress duplicates in the ascending data.

        Warning: Requires n > 0.

        Parameters:
        data - Indices.
        n - Number of indices.
        Returns:
        the number of unique indices
      • ceilLog2

        private static int ceilLog2​(int x)
        Compute ceil(log2(x)). This is valid for all strictly positive x.

        Returns -1 for x = 0 in place of -infinity.

        Parameters:
        x - Value.
        Returns:
        ceil(log2(x))
      • newUpdatingInterval

        private static UpdatingInterval newUpdatingInterval​(int[] k,
                                                            int n)
        Returns an interval that covers the specified indices k. The indices must be sorted.
        Parameters:
        k - Indices.
        n - Count of indices (must be strictly positive).
        Returns:
        the interval
        Throws:
        java.lang.IndexOutOfBoundsException - if any index k is not within the sub-range [left, right]
      • countIndices

        static int countIndices​(UpdatingInterval keys,
                                int n)
        Count the number of indices. Returns a negative value if the indices are sorted.
        Parameters:
        keys - Keys.
        n - Count of indices.
        Returns:
        the count of (sorted) indices
      • checkFromToIndex

        static void checkFromToIndex​(int fromIndex,
                                     int toIndex,
                                     int length)
        Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is within the bounds of range from 0 (inclusive) to length (exclusive).

        This function provides the functionality of java.utils.Objects.checkFromToIndex introduced in JDK 9. The Objects javadoc has been reproduced for reference. The return value has been changed to void.

        The sub-range is defined to be out of bounds if any of the following inequalities is true:

        • fromIndex < 0
        • fromIndex > toIndex
        • toIndex > length
        • length < 0, which is implied from the former inequalities
        Parameters:
        fromIndex - Lower-bound (inclusive) of the sub-range.
        toIndex - Upper-bound (exclusive) of the sub-range.
        length - Upper-bound (exclusive) of the range.
        Throws:
        java.lang.IndexOutOfBoundsException - if the sub-range is out of bounds
      • checkIndices

        static void checkIndices​(int fromIndex,
                                 int toIndex,
                                 int[] k)
        Checks if the index is within the half-open interval [fromIndex, toIndex).
        Parameters:
        fromIndex - Lower-bound (inclusive) of the sub-range.
        toIndex - Upper-bound (exclusive) of the sub-range.
        k - Indices.
        Throws:
        java.lang.IndexOutOfBoundsException - if any index is out of bounds
      • checkIndex

        static void checkIndex​(int fromIndex,
                               int toIndex,
                               int index)
        Checks if the index is within the half-open interval [fromIndex, toIndex).
        Parameters:
        fromIndex - Lower-bound (inclusive) of the sub-range.
        toIndex - Upper-bound (exclusive) of the sub-range.
        index - Index.
        Throws:
        java.lang.IndexOutOfBoundsException - if the index is out of bounds
      • msgRangeOutOfBounds

        private static java.lang.String msgRangeOutOfBounds​(int fromIndex,
                                                            int toIndex,
                                                            int length)
        Format a message when range [from, to) is not entirely within the length.
        Parameters:
        fromIndex - Lower-bound (inclusive) of the sub-range.
        toIndex - Upper-bound (exclusive) of the sub-range.
        length - Upper-bound (exclusive) of the range.
        Returns:
        the message
      • msgIndexOutOfBounds

        private static java.lang.String msgIndexOutOfBounds​(int fromIndex,
                                                            int toIndex,
                                                            int index)
        Format a message when index is not within range [from, to).
        Parameters:
        fromIndex - Lower-bound (inclusive) of the sub-range.
        toIndex - Upper-bound (exclusive) of the sub-range.
        index - Index.
        Returns:
        the message