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

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionstatic <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_equalitystatic <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.

Constructor Details

BinarySearch
protected BinarySearch()


Method Details

lowerBound
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 valueskey
 element to look forcomparator
 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
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 valueskey
 element to look forcomparator
 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 arrayK
 the type of lookup key Parameters:
a
 array that holds the valueskey
 element to look forkeySelector
 function that transforms array contents to the type of the keycomparator
 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 arrayK
 the type of lookup key Parameters:
a
 array that holds the valueskey
 element to look forkeySelector
 function that transforms array contents to the type of the keycomparator
 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
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 valueskey
 element to look forimin
 the minimal index (inclusive) to look forimax
 the maximum index (inclusive) to look forcomparator
 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
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 valueskey
 element to look forimin
 the minimal index (inclusive) to look forimax
 the maximum index (inclusive) to look forcomparator
 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.
