Package org.apache.commons.numbers.arrays

Interface UpdatingInterval

  • All Known Implementing Classes:
    BitIndexUpdatingInterval, KeyUpdatingInterval
    interface UpdatingInterval
    An interval that contains indices used for partitioning an array into multiple regions.

    The interval provides the following functionality:

    • Return the supported bounds of the interval [left <= right].
    • Update the left or right bound of the interval using an index k inside the interval.
    • Split the interval around two indices k1 and k2.

    Note that the interval provides the supported bounds. If an search index k is outside the supported bounds the result is undefined.

    Implementations may assume indices are positive.

    Since:
    1.2

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      int left()
      The start (inclusive) of the interval.
      int right()
      The end (inclusive) of the interval.
      UpdatingInterval splitLeft​(int ka, int kb)
      Split the interval using two splitting indices.
      int updateLeft​(int k)
      Update the left bound of the interval so k <= left.
      int updateRight​(int k)
      Update the right bound of the interval so right <= k.

    • Method Detail

      • left

        int left()
        The start (inclusive) of the interval.
        Returns:
        start of the interval

      • right

        int right()
        The end (inclusive) of the interval.
        Returns:
        end of the interval

      • updateLeft

        int updateLeft​(int k)
        Update the left bound of the interval so k <= left.

        Note: Requires left < k <= right, i.e. there exists a valid interval above the index. 

        
 l-----------k----------r
             |--> l
        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the new left

      • updateRight

        int updateRight​(int k)
        Update the right bound of the interval so right <= k.

        Note: Requires left <= k < right, i.e. there exists a valid interval below the index. 

        
 l-----------k----------r
        r <--|
        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the new right

      • splitLeft

        UpdatingInterval splitLeft​(int ka,
                           int kb)
        Split the interval using two splitting indices. Returns the left interval that occurs before the specified split index ka, and updates the current interval left bound to after the specified split index kb.

        Note: Requires left < ka <= kb < right, i.e. there exists a valid interval both above and below the splitting indices. 

        
 l-----------ka-kb----------r
      r1 <--|     |--> l1

 r1 < ka
 l1 > kb

        If ka <= left or kb >= right the result is undefined.

        Parameters:
        ka - Split index.
        kb - Split index.
        Returns:
        the left interval