Package org.apache.datasketches.quantilescommon

Class GenericInequalitySearch

java.lang.Object

org.apache.datasketches.quantilescommon.GenericInequalitySearch

public final class GenericInequalitySearch
extends Object

This provides efficient, unique and unambiguous binary searching for inequality comparison criteria for ordered arrays of values that may include duplicate values. The inequality criteria include <, ≤, ==, ≥, >. All the inequality criteria use the same search algorithm. (Although == is not an inequality, it is included for convenience.)

In order to make the searching unique and unambiguous, we modified the traditional binary search algorithm to search for adjacent pairs of values {A, B} in the values array instead of just a single value, where a and b are the array indices of two adjacent values in the array. For all the search criteria, when the algorithm has narrowed the search down to a single value or adjacent pair of values, the resolve() method provides the final result of the search. If there is no valid value in the array that satisfies the search criterion, the algorithm will return -1 to the caller.

Given a sorted array of values arr[] and a search key value v, the algorithms for the searching criteria are given with each enum criterion.

Author:

Lee Rhodes

See Also:

Sketching Quantiles and Ranks Tutorial

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	GenericInequalitySearch.Inequality	The enumerator of inequalities

Constructor Summary

Constructors

Constructor	Description
GenericInequalitySearch()

Method Summary

Modifier and Type	Method	Description
static <T> int	find(T[] arr, int low, int high, T v, GenericInequalitySearch.Inequality crit, Comparator<T> comparator)	Binary Search for the index of the generic value in the given search range that satisfies the given Inequality criterion.

Methods inherited from class java.lang.Object

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

Constructor Detail

GenericInequalitySearch

public GenericInequalitySearch()

Method Detail

find

public static <T> int find(T[] arr,
                           int low,
                           int high,
                           T v,
                           GenericInequalitySearch.Inequality crit,
                           Comparator<T> comparator)

Binary Search for the index of the generic value in the given search range that satisfies the given Inequality criterion. If -1 is returned there are no values in the search range that satisfy the inequality.

Type Parameters:

T - The generic type of value to be used in the search process.

Parameters:

arr - the given array of comparable values that must be sorted. The array must not be null or empty and the values of the array must not be null (or NaN) in the range [low, high].

low - the lowest index of the lowest value in the search range, inclusive.

high - the highest index of the highest value in the search range, inclusive.

v - the value to search for. It must not be null (or NaN).

crit - one of the Inequality criteria: LT, LE, EQ, GE, GT. It must not be null.

comparator - for the type T. It must not be null. It must return: -1 if A < B, 0 if A == B, and +1 if A > B.

Returns:

the index of the value in the given search range that satisfies the Inequality criterion.