Class KeyUpdatingInterval

java.lang.Object
org.apache.commons.numbers.arrays.KeyUpdatingInterval
All Implemented Interfaces:
UpdatingInterval

final class KeyUpdatingInterval extends Object implements UpdatingInterval
An UpdatingInterval backed by an array of ordered keys.
Since:
1.2
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final int[]
    The ordered keys.
    private int
    Index of the left key.
    private int
    Index of the right key.
    private static final int
    Size to use a scan of the keys when splitting instead of binary search.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    (package private)
    KeyUpdatingInterval(int[] indices, int n)
    Create an instance with the provided indices.
    private
    KeyUpdatingInterval(int[] indices, int l, int r)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    The start (inclusive) of the interval.
    int
    The end (inclusive) of the interval.
    (package private) static int
    searchLessOrEqual(int[] a, int left, int right, int k)
    Search the data for the largest index i where a[i] is less-than-or-equal to the key; else return left - 1.
    (package private) int
    Return the current number of indices in 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.

    Methods inherited from class java.lang.Object

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

    • SCAN_SIZE

      private static final int SCAN_SIZE
      Size to use a scan of the keys when splitting instead of binary search. Note binary search has an overhead on small size due to the random left/right branching per iteration. It is much faster on very large sizes.
      See Also:
    • keys

      private final int[] keys
      The ordered keys.
    • l

      private int l
      Index of the left key.
    • r

      private int r
      Index of the right key.
  • Constructor Details

    • KeyUpdatingInterval

      KeyUpdatingInterval(int[] indices, int n)
      Create an instance with the provided indices.

      Warning: Indices must be sorted and distinct.

      Parameters:
      indices - Indices.
      n - Number of indices.
    • KeyUpdatingInterval

      private KeyUpdatingInterval(int[] indices, int l, int r)
      Parameters:
      indices - Indices.
      l - Index of left key.
      r - Index of right key.
  • Method Details

    • left

      public int left()
      Description copied from interface: UpdatingInterval
      The start (inclusive) of the interval.
      Specified by:
      left in interface UpdatingInterval
      Returns:
      start of the interval
    • right

      public int right()
      Description copied from interface: UpdatingInterval
      The end (inclusive) of the interval.
      Specified by:
      right in interface UpdatingInterval
      Returns:
      end of the interval
    • updateLeft

      public int updateLeft(int k)
      Description copied from interface: UpdatingInterval
      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
       
      Specified by:
      updateLeft in interface UpdatingInterval
      Parameters:
      k - Index to start checking from (inclusive).
      Returns:
      the new left
    • updateRight

      public int updateRight(int k)
      Description copied from interface: UpdatingInterval
      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 <--|
       
      Specified by:
      updateRight in interface UpdatingInterval
      Parameters:
      k - Index to start checking from (inclusive).
      Returns:
      the new right
    • splitLeft

      public UpdatingInterval splitLeft(int ka, int kb)
      Description copied from interface: UpdatingInterval
      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.

      Specified by:
      splitLeft in interface UpdatingInterval
      Parameters:
      ka - Split index.
      kb - Split index.
      Returns:
      the left interval
    • size

      int size()
      Return the current number of indices in the interval.
      Returns:
      the size
    • searchLessOrEqual

      static int searchLessOrEqual(int[] a, int left, int right, int k)
      Search the data for the largest index i where a[i] is less-than-or-equal to the key; else return left - 1.
       a[i] invalid input: '<'= k    :   left invalid input: '<'= i invalid input: '<'= right, or (left - 1)
       

      The data is assumed to be in ascending order, otherwise the behaviour is undefined. If the range contains multiple elements with the key value, the result index may be any that match.

      This is similar to using Arrays.binarySearch. The method differs in:

      • use of an inclusive upper bound;
      • returning the closest index with a value below key if no match was not found;
      • performing no range checks: it is assumed left <= right and they are valid indices into the array.

      An equivalent use of binary search is:

      
       int i = Arrays.binarySearch(a, left, right + 1, k);
       if (i < 0) {
           i = ~i - 1;
       }
       

      This specialisation avoids the caller checking the binary search result for the use case when the presence or absence of a key is not important; only that the returned index for an absence of a key is the largest index. When used on unique keys this method can be used to update an upper index so all keys are known to be below a key:

      
       int[] keys = ...
       // [i0, i1] contains all keys
       int i0 = 0;
       int i1 = keys.length - 1;
       // Update: [i0, i1] contains all keys <= k
       i1 = searchLessOrEqual(keys, i0, i1, k);
       
      Parameters:
      a - Data.
      left - Lower bound (inclusive).
      right - Upper bound (inclusive).
      k - Key.
      Returns:
      largest index i such that a[i] <= k, or left - 1 if no such index exists