com.alexkasko.unsafe.offheapstruct

Class OffHeapStructBinarySearch

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructBinarySearch

public class OffHeapStructBinarySearch
extends Object

Binary search implementation borrowed from https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/Arrays.java and adapted to OffHeapStructCollection

Author:

alexkasko Date: 7/4/13

See Also:

OffHeapLongSorter, OffHeapStructSorter

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	OffHeapStructBinarySearch.IndexRange OffHeapStructCollection index range representation.

Constructor Summary

Constructors

Constructor and Description
OffHeapStructBinarySearch()

Method Summary

Methods

Modifier and Type	Method and Description
static long	binarySearchByIntKey(OffHeapStructCollection collection, long value, int keyOffset) Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key.
static long	binarySearchByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key.
static long	binarySearchByLongKey(OffHeapStructCollection collection, long value, int keyOffset) Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key.
static long	binarySearchByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key.
static void	binarySearchRangeByIntKey(OffHeapStructCollection collection, long value, int keyOffset, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key.
static void	binarySearchRangeByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key.
static void	binarySearchRangeByLongKey(OffHeapStructCollection collection, long value, int keyOffset, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key.
static void	binarySearchRangeByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key.

Methods inherited from class java.lang.Object

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

Constructor Detail

OffHeapStructBinarySearch

public OffHeapStructBinarySearch()

Method Detail

binarySearchByLongKey

public static long binarySearchByLongKey(OffHeapStructCollection collection,
                         long value,
                         int keyOffset)

Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

value - the element to find.

keyOffset - long key field offset within stuct bounds

Returns:

the non-negative index of the element, or a negative index which is -index - 1 where the element would be inserted.

binarySearchByLongKey

public static long binarySearchByLongKey(OffHeapStructCollection collection,
                         long startIndex,
                         long endIndex,
                         long value,
                         int keyOffset)

Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key. in the range specified by fromIndex (inclusive) and toIndex (exclusive). Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted collection to search.

startIndex - the inclusive start index.

endIndex - the exclusive end index.

value - the element to find.

keyOffset - long key field offset within stuct bounds

Returns:

the non-negative index of the element, or a negative index which is -index - 1 where the element would be inserted.

Throws:

IllegalArgumentException - if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()

binarySearchRangeByLongKey

public static void binarySearchRangeByLongKey(OffHeapStructCollection collection,
                              long value,
                              int keyOffset,
                              OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key. Returns range of indices having given value or empty range. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

value - the element to find.

keyOffset - long key field offset within stuct bounds

out - range instance, will be set with start/end indices having given value or with empty value

binarySearchRangeByLongKey

public static void binarySearchRangeByLongKey(OffHeapStructCollection collection,
                              long startIndex,
                              long endIndex,
                              long value,
                              int keyOffset,
                              OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection using long struct key. Returns range of indices having given value or empty range. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

startIndex - the inclusive start index.

endIndex - the exclusive end index.

value - the element to find.

keyOffset - long key field offset within stuct bounds

out - range instance, will be set with start/end indices having given value or with empty value

binarySearchByIntKey

public static long binarySearchByIntKey(OffHeapStructCollection collection,
                        long value,
                        int keyOffset)

Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

value - the element to find.

keyOffset - int key field offset within stuct bounds

Returns:

the non-negative index of the element, or a negative index which is -index - 1 where the element would be inserted.

binarySearchByIntKey

public static long binarySearchByIntKey(OffHeapStructCollection collection,
                        long startIndex,
                        long endIndex,
                        long value,
                        int keyOffset)

Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key. in the range specified by fromIndex (inclusive) and toIndex (exclusive). Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted collection to search.

startIndex - the inclusive start index.

endIndex - the exclusive end index.

value - the element to find.

keyOffset - int key field offset within stuct bounds

Returns:

the non-negative index of the element, or a negative index which is -index - 1 where the element would be inserted.

Throws:

IllegalArgumentException - if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()

binarySearchRangeByIntKey

public static void binarySearchRangeByIntKey(OffHeapStructCollection collection,
                             long value,
                             int keyOffset,
                             OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key. Returns range of indices having given value or empty range. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

value - the element to find.

keyOffset - int key field offset within stuct bounds

out - range instance, will be set with start/end indices having given value or with empty value

binarySearchRangeByIntKey

public static void binarySearchRangeByIntKey(OffHeapStructCollection collection,
                             long startIndex,
                             long endIndex,
                             long value,
                             int keyOffset,
                             OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection using int struct key. Returns range of indices having given value or empty range. Searching in an unsorted collection has an undefined result. It's also undefined which element is found if there are multiple occurrences of the same element.

Parameters:

collection - the sorted array to search.

startIndex - the inclusive start index.

endIndex - the exclusive end index.

value - the element to find.

keyOffset - int key field offset within stuct bounds

out - range instance, will be set with start/end indices having given value or with empty value