Package org.apache.calcite.runtime

Class BinarySearch

java.lang.Object
org.apache.calcite.runtime.BinarySearch
public class BinarySearch extends Object
Binary search for the implementation of RANGE BETWEEN XXX PRECEDING/FOLLOWING clause.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    BinarySearch()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static <T, K> int
    lowerBound(T[] a, K key, int imin, int imax, Function1<T,K> keySelector, Comparator<K> comparator)
    Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm #Deferred_detection_of_equality
    static <T, K> int
    lowerBound(T[] a, K key, Function1<T,K> keySelector, Comparator<K> comparator)
    Performs binary search of the lower bound in the given array.
    static <T> int
    lowerBound(T[] a, T key, int imin, int imax, Comparator<T> comparator)
    Performs binary search of the lower bound in the given section of array.
    static <T> int
    lowerBound(T[] a, T key, Comparator<T> comparator)
    Performs binary search of the lower bound in the given array.
    static <T, K> int
    upperBound(T[] a, K key, int imin, int imax, Function1<T,K> keySelector, Comparator<K> comparator)
    Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm #Deferred_detection_of_equality Adapted to find upper bound.
    static <T, K> int
    upperBound(T[] a, K key, Function1<T,K> keySelector, Comparator<K> comparator)
    Performs binary search of the upper bound in the given array.
    static <T> int
    upperBound(T[] a, T key, int imin, int imax, Comparator<T> comparator)
    Performs binary search of the upper bound in the given array.
    static <T> int
    upperBound(T[] a, T key, Comparator<T> comparator)
    Performs binary search of the upper bound in the given array.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • BinarySearch

      protected BinarySearch()

  • Method Details

    • lowerBound

      public static <T> int lowerBound(T[] a, T key, Comparator<T> comparator)
      Performs binary search of the lower bound in the given array. It is assumed that the array is sorted. The method is guaranteed to return the minimal index of the element that is greater or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      Parameters:
      a - array that holds the values
      key - element to look for
      comparator - comparator that compares keys
      Returns:
      minimal index of the element that is greater or equal to the given key. Returns -1 when all elements exceed the given key or the array is empty. Returns a.length when all elements are less than the given key.

    • upperBound

      public static <T> int upperBound(T[] a, T key, Comparator<T> comparator)
      Performs binary search of the upper bound in the given array. It is assumed that the array is sorted. The method is guaranteed to return the maximal index of the element that is less or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      Parameters:
      a - array that holds the values
      key - element to look for
      comparator - comparator that compares keys
      Returns:
      maximal index of the element that is less or equal to the given key. Returns -1 when all elements are less than the given key or the array is empty. Returns a.length when all elements exceed the given key.

    • lowerBound

      public static <T, K> int lowerBound(T[] a, K key, Function1<T,K> keySelector, Comparator<K> comparator)
      Performs binary search of the lower bound in the given array. The elements in the array are transformed before the comparison. It is assumed that the array is sorted. The method is guaranteed to return the minimal index of the element that is greater or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      K - the type of lookup key
      Parameters:
      a - array that holds the values
      key - element to look for
      keySelector - function that transforms array contents to the type of the key
      comparator - comparator that compares keys
      Returns:
      minimal index of the element that is greater or equal to the given key. Returns -1 when all elements exceed the given key or the array is empty. Returns a.length when all elements are less than the given key.

    • upperBound

      public static <T, K> int upperBound(T[] a, K key, Function1<T,K> keySelector, Comparator<K> comparator)
      Performs binary search of the upper bound in the given array. The elements in the array are transformed before the comparison. It is assumed that the array is sorted. The method is guaranteed to return the maximal index of the element that is less or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      K - the type of lookup key
      Parameters:
      a - array that holds the values
      key - element to look for
      keySelector - function that transforms array contents to the type of the key
      comparator - comparator that compares keys
      Returns:
      maximal index of the element that is less or equal to the given key. Returns -1 when all elements are less than the given key or the array is empty. Returns a.length when all elements exceed the given key.

    • lowerBound

      public static <T> int lowerBound(T[] a, T key, int imin, int imax, Comparator<T> comparator)
      Performs binary search of the lower bound in the given section of array. It is assumed that the array is sorted. The method is guaranteed to return the minimal index of the element that is greater or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      Parameters:
      a - array that holds the values
      key - element to look for
      imin - the minimal index (inclusive) to look for
      imax - the maximum index (inclusive) to look for
      comparator - comparator that compares keys
      Returns:
      minimal index of the element that is greater or equal to the given key. Returns -1 when all elements exceed the given key or the array is empty. Returns a.length when all elements are less than the given key.

    • upperBound

      public static <T> int upperBound(T[] a, T key, int imin, int imax, Comparator<T> comparator)
      Performs binary search of the upper bound in the given array. It is assumed that the array is sorted. The method is guaranteed to return the maximal index of the element that is less or equal to the given key.
      Type Parameters:
      T - the type of elements in array
      Parameters:
      a - array that holds the values
      key - element to look for
      imin - the minimal index (inclusive) to look for
      imax - the maximum index (inclusive) to look for
      comparator - comparator that compares keys
      Returns:
      maximal index of the element that is less or equal to the given key. Returns -1 when all elements are less than the given key or the array is empty. Returns a.length when all elements exceed the given key.

    • lowerBound

      public static <T, K> int lowerBound(T[] a, K key, int imin, int imax, Function1<T,K> keySelector, Comparator<K> comparator)
      Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm #Deferred_detection_of_equality

    • upperBound

      public static <T, K> int upperBound(T[] a, K key, int imin, int imax, Function1<T,K> keySelector, Comparator<K> comparator)
      Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm #Deferred_detection_of_equality Adapted to find upper bound.