com.alexkasko.unsafe.offheapstruct

Class OffHeapStructBinarySearchWithComparator

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructBinarySearchWithComparator

public class OffHeapStructBinarySearchWithComparator
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 with comparators. Search methods are not static in this class to prevent internal comparator wrapper object creation on each search call. All operations on instances of this class are NOT thread-safe.

Author:

alexkasko Date: 9/13/13

Field Summary

Fields

Modifier and Type	Field and Description
private OffHeapStructCollection	col
private OffHeapStructComparator	comp

Constructor Summary

Constructors

Constructor and Description
OffHeapStructBinarySearchWithComparator(OffHeapStructCollection collection, Comparator<OffHeapStructAccessor> comparator) Constructor

Method Summary

Methods

Modifier and Type	Method and Description
long	binarySearch(byte[] struct) Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance).
long	binarySearch(long startIndex, long endIndex, byte[] struct) Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance).
void	binarySearchRange(byte[] struct, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance).
void	binarySearchRange(long startIndex, long endIndex, byte[] struct, OffHeapStructBinarySearch.IndexRange out) Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance).
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

col

private final OffHeapStructCollection col

comp

private final OffHeapStructComparator comp

Constructor Detail

OffHeapStructBinarySearchWithComparator

public OffHeapStructBinarySearchWithComparator(OffHeapStructCollection collection,
                                       Comparator<OffHeapStructAccessor> comparator)

Constructor

Parameters:

collection - collection to search over

comparator - comparator to use for comparing provided structure while searching

Method Detail

binarySearch

public long binarySearch(byte[] struct)

Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance). 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:

struct - the structure to find

Returns:

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

binarySearch

public long binarySearch(long startIndex,
                long endIndex,
                byte[] struct)

Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance). 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:

startIndex - the inclusive start index.

endIndex - the exclusive end index.

struct - the structure to find

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()

binarySearchRange

public void binarySearchRange(byte[] struct,
                     OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance). 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:

struct - the structure to find

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

binarySearchRange

public void binarySearchRange(long startIndex,
                     long endIndex,
                     byte[] struct,
                     OffHeapStructBinarySearch.IndexRange out)

Performs a binary search for value in the ascending sorted off-heap struct collection comparing provided struct using comparator (both collection and comparator are bound to searcher instance). 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:

startIndex - the inclusive start index.

endIndex - the exclusive end index.

struct - the structure to find

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

toString

public String toString()

Overrides:

toString in class Object