Package org.apache.calcite.runtime

Class BinarySearch

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

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected BinarySearch()  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <T,​K>
      int      		 lowerBound​(T[] a, K key, int imin, int imax, Function1<T,​K> keySelector, java.util.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, java.util.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, java.util.Comparator<T> comparator)
      Performs binary search of the lower bound in the given section of array.
      static <T> int lowerBound​(T[] a, T key, java.util.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, java.util.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, java.util.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, java.util.Comparator<T> comparator)
      Performs binary search of the upper bound in the given array.
      static <T> int upperBound​(T[] a, T key, java.util.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 Detail

      • BinarySearch

        protected BinarySearch()

    • Method Detail

      • lowerBound

        public static <T> int lowerBound​(T[] a,
                                 T key,
                                 java.util.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,
                                 java.util.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,
                                         java.util.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,
                                         java.util.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,
                                 java.util.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,
                                 java.util.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,
                                         java.util.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,
                                         java.util.Comparator<K> comparator)
        Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm #Deferred_detection_of_equality Adapted to find upper bound.