ParallelSorter.java
/*
* Copyright 2003 The Apache Software Foundation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package net.sf.cglib.util;
import java.lang.reflect.*;
import java.util.Comparator;
import net.sf.cglib.core.*;
import org.objectweb.asm.ClassVisitor;
/**
* For the efficient sorting of multiple arrays in parallel.
* <p>
* 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.
* <p>
* 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.
* <p>
* 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.
* <p>
* The mergesort algorithm here is an "in-place" variant, which while
* slower, does not require a temporary array.
*
* @author Chris Nokleberg
*/
abstract public class ParallelSorter extends SorterTemplate {
protected Object[] a;
private Comparer comparer;
protected ParallelSorter() {
}
abstract public ParallelSorter newInstance(Object[] arrays);
/**
* Create a new ParallelSorter object for a set of arrays. You may
* sort the arrays multiple times via the same ParallelSorter object.
* @param 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.
* @param loader ClassLoader for generated class, uses "current" if null
*/
public static ParallelSorter create(Object[] arrays) {
Generator gen = new Generator();
gen.setArrays(arrays);
return gen.create();
}
private int len() {
return ((Object[])a[0]).length;
}
/**
* Sort the arrays using the quicksort algorithm.
* @param index array (column) to sort by
*/
public void quickSort(int index) {
quickSort(index, 0, len(), null);
}
/**
* Sort the arrays using the quicksort algorithm.
* @param index array (column) to sort by
* @param lo starting array index (row), inclusive
* @param hi ending array index (row), exclusive
*/
public void quickSort(int index, int lo, int hi) {
quickSort(index, lo, hi, null);
}
/**
* Sort the arrays using the quicksort algorithm.
* @param index array (column) to sort by
* @param cmp Comparator to use if the specified column is non-primitive
*/
public void quickSort(int index, Comparator cmp) {
quickSort(index, 0, len(), cmp);
}
/**
* Sort the arrays using the quicksort algorithm.
* @param index array (column) to sort by
* @param lo starting array index (row), inclusive
* @param hi ending array index (row), exclusive
* @param cmp Comparator to use if the specified column is non-primitive
*/
public void quickSort(int index, int lo, int hi, Comparator cmp) {
chooseComparer(index, cmp);
super.quickSort(lo, hi - 1);
}
/**
* @param index array (column) to sort by
*/
public void mergeSort(int index) {
mergeSort(index, 0, len(), null);
}
/**
* Sort the arrays using an in-place merge sort.
* @param index array (column) to sort by
* @param lo starting array index (row), inclusive
* @param hi ending array index (row), exclusive
*/
public void mergeSort(int index, int lo, int hi) {
mergeSort(index, lo, hi, null);
}
/**
* Sort the arrays using an in-place merge sort.
* @param index array (column) to sort by
* @param lo starting array index (row), inclusive
* @param hi ending array index (row), exclusive
*/
public void mergeSort(int index, Comparator cmp) {
mergeSort(index, 0, len(), cmp);
}
/**
* Sort the arrays using an in-place merge sort.
* @param index array (column) to sort by
* @param lo starting array index (row), inclusive
* @param hi ending array index (row), exclusive
* @param cmp Comparator to use if the specified column is non-primitive
*/
public void mergeSort(int index, int lo, int hi, Comparator cmp) {
chooseComparer(index, cmp);
super.mergeSort(lo, hi - 1);
}
private void chooseComparer(int index, Comparator cmp) {
Object array = a[index];
Class type = array.getClass().getComponentType();
if (type.equals(Integer.TYPE)) {
comparer = new IntComparer((int[])array);
} else if (type.equals(Long.TYPE)) {
comparer = new LongComparer((long[])array);
} else if (type.equals(Double.TYPE)) {
comparer = new DoubleComparer((double[])array);
} else if (type.equals(Float.TYPE)) {
comparer = new FloatComparer((float[])array);
} else if (type.equals(Short.TYPE)) {
comparer = new ShortComparer((short[])array);
} else if (type.equals(Byte.TYPE)) {
comparer = new ByteComparer((byte[])array);
} else if (cmp != null) {
comparer = new ComparatorComparer((Object[])array, cmp);
} else {
comparer = new ObjectComparer((Object[])array);
}
}
protected int compare(int i, int j) {
return comparer.compare(i, j);
}
interface Comparer {
int compare(int i, int j);
}
static class ComparatorComparer implements Comparer {
private Object[] a;
private Comparator cmp;
public ComparatorComparer(Object[] a, Comparator cmp) {
this.a = a;
this.cmp = cmp;
}
public int compare(int i, int j) {
return cmp.compare(a[i], a[j]);
}
}
static class ObjectComparer implements Comparer {
private Object[] a;
public ObjectComparer(Object[] a) { this.a = a; }
public int compare(int i, int j) {
return ((Comparable)a[i]).compareTo(a[j]);
}
}
static class IntComparer implements Comparer {
private int[] a;
public IntComparer(int[] a) { this.a = a; }
public int compare(int i, int j) { return a[i] - a[j]; }
}
static class LongComparer implements Comparer {
private long[] a;
public LongComparer(long[] a) { this.a = a; }
public int compare(int i, int j) {
long vi = a[i];
long vj = a[j];
return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
}
}
static class FloatComparer implements Comparer {
private float[] a;
public FloatComparer(float[] a) { this.a = a; }
public int compare(int i, int j) {
float vi = a[i];
float vj = a[j];
return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
}
}
static class DoubleComparer implements Comparer {
private double[] a;
public DoubleComparer(double[] a) { this.a = a; }
public int compare(int i, int j) {
double vi = a[i];
double vj = a[j];
return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
}
}
static class ShortComparer implements Comparer {
private short[] a;
public ShortComparer(short[] a) { this.a = a; }
public int compare(int i, int j) { return a[i] - a[j]; }
}
static class ByteComparer implements Comparer {
private byte[] a;
public ByteComparer(byte[] a) { this.a = a; }
public int compare(int i, int j) { return a[i] - a[j]; }
}
public static class Generator extends AbstractClassGenerator {
private static final Source SOURCE = new Source(ParallelSorter.class.getName());
private Object[] arrays;
public Generator() {
super(SOURCE);
}
protected ClassLoader getDefaultClassLoader() {
return null; // TODO
}
public void setArrays(Object[] arrays) {
this.arrays = arrays;
}
public ParallelSorter create() {
return (ParallelSorter)super.create(ClassesKey.create(arrays));
}
public void generateClass(ClassVisitor v) throws Exception {
if (arrays.length == 0) {
throw new IllegalArgumentException("No arrays specified to sort");
}
for (int i = 0; i < arrays.length; i++) {
if (!arrays[i].getClass().isArray()) {
throw new IllegalArgumentException(arrays[i].getClass() + " is not an array");
}
}
new ParallelSorterEmitter(v, getClassName(), arrays);
}
protected Object firstInstance(Class type) {
return ((ParallelSorter)ReflectUtils.newInstance(type)).newInstance(arrays);
}
protected Object nextInstance(Object instance) {
return ((ParallelSorter)instance).newInstance(arrays);
}
}
}