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

    Modifier and Type
    Method
    Description
    int
    The start (inclusive) of the interval.
    int
    The end (inclusive) of the interval.
    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 Details

    • 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