com.alexkasko.unsafe.offheapstruct

Class OffHeapStructSorterByReference

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructSorterByReference

public class OffHeapStructSorterByReference
extends Object

alexkasko: borrowed from https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java and adapted to OffHeapStructCollection to sort it by reference. without changing element positions in array itself.

Temporary OffHeapLongArray with the same size as collection itself will be used to hold references.

This class implements the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Version:

2009.11.29 m765.827.12i

Author:

Vladimir Yaroslavskiy, Jon Bentley, Josh Bloch

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	OffHeapStructSorterByReference.OffHeapReferenceComparator Comparator wrapper to use with references, not thread-safe
private static class	OffHeapStructSorterByReference.OffHeapStructIndexAccessor Struct's accessor implementation for off-heap stored structs
private static class	OffHeapStructSorterByReference.ReferenceIterable Iterable over the data collection using indices from specified array
private static class	OffHeapStructSorterByReference.ReferenceIterator Iterator returning data elements in the order specified by indices array

Constructor Summary

Constructors

Constructor and Description
OffHeapStructSorterByReference()

Method Summary

Methods

Modifier and Type	Method and Description
(package private) static OffHeapDisposableIterable<byte[]>	sortedIterable(OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection
(package private) static OffHeapDisposableIterable<byte[]>	sortedIterable(OffHeapStructCollection a, long fromIndex, long toIndex, Comparator<OffHeapStructAccessor> comparator) Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection

Methods inherited from class java.lang.Object

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

Constructor Detail

OffHeapStructSorterByReference

public OffHeapStructSorterByReference()

Method Detail

sortedIterable

static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a,
                                               Comparator<OffHeapStructAccessor> comparator)

Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection

Parameters:

a - the off-heap struct collection to be sorted

comparator - structs comparator

Returns:

sorted iterable over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortedIterable

static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a,
                                               long fromIndex,
                                               long toIndex,
                                               Comparator<OffHeapStructAccessor> comparator)

Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

comparator - structs comparator

Returns:

sorted iterable over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())