net.sf.cglib
Class ParallelSorter

java.lang.Object
  |
  +--net.sf.cglib.SorterTemplate
        |
        +--net.sf.cglib.ParallelSorter

public abstract class ParallelSorter

extends net.sf.cglib.SorterTemplate

For the efficient sorting of multiple arrays in parallel.

Given two arrays of equal length and varying types, the standard technique for sorting them in parallel is to create a new temporary object for each row, store the objects in a temporary array, sort the array using a custom comparator, and the extract the original values back into their respective arrays. This is wasteful in both time and memory.

This class generates bytecode customized to the particular set of arrays you need to sort, in such a way that both arrays are sorted in-place, simultaneously.

Two sorting algorithms are provided. Quicksort is best when you only need to sort by a single column, as it requires very few comparisons and swaps. Mergesort is best used when sorting multiple columns, as it is a "stable" sort--that is, it does not affect the relative order of equal objects from previous sorts.

The mergesort algorithm here is an "in-place" variant, which while slower, does not require a temporary array.

Author:

Chris Nokleberg

Field Summary

protected java.lang.Object[]

a

Constructor Summary

protected

ParallelSorter()

Method Summary

protected int	compare(int i, int j)
static ParallelSorter	create(java.lang.Object[] arrays) Helper method, has same effect as return create(arrays, null);
static ParallelSorter	create(java.lang.Object[] arrays, java.lang.ClassLoader loader) Create a new ParallelSorter object for a set of arrays.
void	mergeSort(int index)
void	mergeSort(int index, java.util.Comparator cmp) Sort the arrays using an in-place merge sort.
protected void	mergeSort(int lo, int hi)
void	mergeSort(int index, int lo, int hi) Sort the arrays using an in-place merge sort.
void	mergeSort(int index, int lo, int hi, java.util.Comparator cmp) Sort the arrays using an in-place merge sort.
protected abstract ParallelSorter	newInstance(java.lang.Object[] arrays)
void	quickSort(int index) Sort the arrays using the quicksort algorithm.
void	quickSort(int index, java.util.Comparator cmp) Sort the arrays using the quicksort algorithm.
protected void	quickSort(int lo, int hi)
void	quickSort(int index, int lo, int hi) Sort the arrays using the quicksort algorithm.
void	quickSort(int index, int lo, int hi, java.util.Comparator cmp) Sort the arrays using the quicksort algorithm.
protected abstract void	swap(int i, int j)

Methods inherited from class java.lang.Object

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

Field Detail

a

protected java.lang.Object[] a

Constructor Detail

ParallelSorter

protected ParallelSorter()

Method Detail

newInstance

protected abstract ParallelSorter newInstance(java.lang.Object[] arrays)

create

public static ParallelSorter create(java.lang.Object[] arrays)

Helper method, has same effect as

return create(arrays, null);

See Also:

create(Object[], ClassLoader)

create

public static ParallelSorter create(java.lang.Object[] arrays,
                                    java.lang.ClassLoader loader)

Create a new ParallelSorter object for a set of arrays. You may sort the arrays multiple times via the same ParallelSorter object.

Parameters:

arrays - An array of arrays to sort. The arrays may be a mix of primitive and non-primitive types, but should all be the same length.

loader - ClassLoader for generated class, uses "current" if null

quickSort

public void quickSort(int index)

Sort the arrays using the quicksort algorithm.

Parameters:

index - array (column) to sort by

quickSort

public void quickSort(int index,
                      int lo,
                      int hi)

Sort the arrays using the quicksort algorithm.

Parameters:

index - array (column) to sort by

lo - starting array index (row), inclusive

hi - ending array index (row), exclusive

quickSort

public void quickSort(int index,
                      java.util.Comparator cmp)

Sort the arrays using the quicksort algorithm.

Parameters:

index - array (column) to sort by

cmp - Comparator to use if the specified column is non-primitive

quickSort

public void quickSort(int index,
                      int lo,
                      int hi,
                      java.util.Comparator cmp)

Sort the arrays using the quicksort algorithm.

Parameters:

index - array (column) to sort by

lo - starting array index (row), inclusive

hi - ending array index (row), exclusive

cmp - Comparator to use if the specified column is non-primitive

mergeSort

public void mergeSort(int index)

Parameters:

index - array (column) to sort by

mergeSort

public void mergeSort(int index,
                      int lo,
                      int hi)

Sort the arrays using an in-place merge sort.

Parameters:

index - array (column) to sort by

lo - starting array index (row), inclusive

hi - ending array index (row), exclusive

mergeSort

public void mergeSort(int index,
                      java.util.Comparator cmp)

Sort the arrays using an in-place merge sort.

Parameters:

index - array (column) to sort by

lo - starting array index (row), inclusive

hi - ending array index (row), exclusive

mergeSort

public void mergeSort(int index,
                      int lo,
                      int hi,
                      java.util.Comparator cmp)

Sort the arrays using an in-place merge sort.

Parameters:

index - array (column) to sort by

lo - starting array index (row), inclusive

hi - ending array index (row), exclusive

cmp - Comparator to use if the specified column is non-primitive

compare

protected int compare(int i,
                      int j)

Overrides:

compare in class net.sf.cglib.SorterTemplate

swap

protected abstract void swap(int i,
                             int j)

quickSort

protected void quickSort(int lo,
                         int hi)

mergeSort

protected void mergeSort(int lo,
                         int hi)