一、前言
关于cglib源码包(相关jar下载)分别基于net.sf.cglib.util.SorterTemplate排序模板、net.sf.cglib.util.ParallelSorter并行排序器,实现对任何数据类型进行排序处理,其中并定义内部自定义排序接口net.sf.cglib.util.ParallelSorter.Comparer、各种数据类型实现类(ComparatorComparer组合排序类、ObjectComparer对象排序类、LongComparer、IntComparer、ByteComparer..等),详情参见示例说明。
二、示例代码
1.主排序类ParallelSorter
package net.sf.cglib.util;@b@@b@import java.lang.reflect.*;@b@import java.util.Comparator;@b@import net.sf.cglib.core.*;@b@import org.objectweb.asm.ClassVisitor;@b@@b@ @b@abstract public class ParallelSorter extends SorterTemplate {@b@ protected Object[] a;@b@ private Comparer comparer;@b@ @b@ protected ParallelSorter() {@b@ }@b@@b@ abstract public ParallelSorter newInstance(Object[] arrays);@b@@b@ @b@ public static ParallelSorter create(Object[] arrays) {@b@ Generator gen = new Generator();@b@ gen.setArrays(arrays);@b@ return gen.create();@b@ }@b@@b@ private int len() {@b@ return ((Object[])a[0]).length;@b@ }@b@@b@ /**@b@ * Sort the arrays using the quicksort algorithm.@b@ * @param index array (column) to sort by@b@ */@b@ public void quickSort(int index) {@b@ quickSort(index, 0, len(), null);@b@ }@b@@b@ /**@b@ * Sort the arrays using the quicksort algorithm.@b@ * @param index array (column) to sort by@b@ * @param lo starting array index (row), inclusive@b@ * @param hi ending array index (row), exclusive@b@ */@b@ public void quickSort(int index, int lo, int hi) {@b@ quickSort(index, lo, hi, null);@b@ }@b@@b@ /**@b@ * Sort the arrays using the quicksort algorithm.@b@ * @param index array (column) to sort by@b@ * @param cmp Comparator to use if the specified column is non-primitive@b@ */@b@ public void quickSort(int index, Comparator cmp) {@b@ quickSort(index, 0, len(), cmp);@b@ }@b@@b@ /**@b@ * Sort the arrays using the quicksort algorithm.@b@ * @param index array (column) to sort by@b@ * @param lo starting array index (row), inclusive@b@ * @param hi ending array index (row), exclusive@b@ * @param cmp Comparator to use if the specified column is non-primitive@b@ */@b@ public void quickSort(int index, int lo, int hi, Comparator cmp) {@b@ chooseComparer(index, cmp);@b@ super.quickSort(lo, hi - 1);@b@ }@b@@b@ /**@b@ * @param index array (column) to sort by@b@ */@b@ public void mergeSort(int index) {@b@ mergeSort(index, 0, len(), null);@b@ }@b@@b@ /**@b@ * Sort the arrays using an in-place merge sort.@b@ * @param index array (column) to sort by@b@ * @param lo starting array index (row), inclusive@b@ * @param hi ending array index (row), exclusive@b@ */@b@ public void mergeSort(int index, int lo, int hi) {@b@ mergeSort(index, lo, hi, null);@b@ }@b@@b@ /**@b@ * Sort the arrays using an in-place merge sort.@b@ * @param index array (column) to sort by@b@ * @param lo starting array index (row), inclusive@b@ * @param hi ending array index (row), exclusive@b@ */@b@ public void mergeSort(int index, Comparator cmp) {@b@ mergeSort(index, 0, len(), cmp);@b@ }@b@@b@ /**@b@ * Sort the arrays using an in-place merge sort.@b@ * @param index array (column) to sort by@b@ * @param lo starting array index (row), inclusive@b@ * @param hi ending array index (row), exclusive@b@ * @param cmp Comparator to use if the specified column is non-primitive@b@ */@b@ public void mergeSort(int index, int lo, int hi, Comparator cmp) {@b@ chooseComparer(index, cmp);@b@ super.mergeSort(lo, hi - 1);@b@ }@b@ @b@ private void chooseComparer(int index, Comparator cmp) {@b@ Object array = a[index];@b@ Class type = array.getClass().getComponentType();@b@ if (type.equals(Integer.TYPE)) {@b@ comparer = new IntComparer((int[])array);@b@ } else if (type.equals(Long.TYPE)) {@b@ comparer = new LongComparer((long[])array);@b@ } else if (type.equals(Double.TYPE)) {@b@ comparer = new DoubleComparer((double[])array);@b@ } else if (type.equals(Float.TYPE)) {@b@ comparer = new FloatComparer((float[])array);@b@ } else if (type.equals(Short.TYPE)) {@b@ comparer = new ShortComparer((short[])array);@b@ } else if (type.equals(Byte.TYPE)) {@b@ comparer = new ByteComparer((byte[])array);@b@ } else if (cmp != null) {@b@ comparer = new ComparatorComparer((Object[])array, cmp);@b@ } else {@b@ comparer = new ObjectComparer((Object[])array);@b@ } @b@ }@b@@b@ protected int compare(int i, int j) {@b@ return comparer.compare(i, j);@b@ }@b@@b@ interface Comparer {@b@ int compare(int i, int j);@b@ }@b@@b@ static class ComparatorComparer implements Comparer {@b@ private Object[] a;@b@ private Comparator cmp;@b@@b@ public ComparatorComparer(Object[] a, Comparator cmp) {@b@ this.a = a;@b@ this.cmp = cmp;@b@ }@b@@b@ public int compare(int i, int j) {@b@ return cmp.compare(a[i], a[j]);@b@ }@b@ }@b@ @b@ static class ObjectComparer implements Comparer {@b@ private Object[] a;@b@ public ObjectComparer(Object[] a) { this.a = a; }@b@ public int compare(int i, int j) {@b@ return ((Comparable)a[i]).compareTo(a[j]);@b@ }@b@ }@b@@b@ static class IntComparer implements Comparer {@b@ private int[] a;@b@ public IntComparer(int[] a) { this.a = a; }@b@ public int compare(int i, int j) { return a[i] - a[j]; }@b@ }@b@@b@ static class LongComparer implements Comparer {@b@ private long[] a;@b@ public LongComparer(long[] a) { this.a = a; }@b@ public int compare(int i, int j) {@b@ long vi = a[i];@b@ long vj = a[j];@b@ return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;@b@ }@b@ }@b@@b@ static class FloatComparer implements Comparer {@b@ private float[] a;@b@ public FloatComparer(float[] a) { this.a = a; }@b@ public int compare(int i, int j) {@b@ float vi = a[i];@b@ float vj = a[j];@b@ return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;@b@ }@b@ }@b@ @b@ static class DoubleComparer implements Comparer {@b@ private double[] a;@b@ public DoubleComparer(double[] a) { this.a = a; }@b@ public int compare(int i, int j) {@b@ double vi = a[i];@b@ double vj = a[j];@b@ return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;@b@ }@b@ }@b@@b@ static class ShortComparer implements Comparer {@b@ private short[] a;@b@ public ShortComparer(short[] a) { this.a = a; }@b@ public int compare(int i, int j) { return a[i] - a[j]; }@b@ }@b@@b@ static class ByteComparer implements Comparer {@b@ private byte[] a;@b@ public ByteComparer(byte[] a) { this.a = a; }@b@ public int compare(int i, int j) { return a[i] - a[j]; }@b@ }@b@@b@ public static class Generator extends AbstractClassGenerator {@b@ private static final Source SOURCE = new Source(ParallelSorter.class.getName());@b@@b@ private Object[] arrays;@b@@b@ public Generator() {@b@ super(SOURCE);@b@ }@b@@b@ protected ClassLoader getDefaultClassLoader() {@b@ return null; // TODO@b@ }@b@@b@ public void setArrays(Object[] arrays) {@b@ this.arrays = arrays;@b@ }@b@@b@ public ParallelSorter create() {@b@ return (ParallelSorter)super.create(ClassesKey.create(arrays));@b@ }@b@@b@ public void generateClass(ClassVisitor v) throws Exception {@b@ if (arrays.length == 0) {@b@ throw new IllegalArgumentException("No arrays specified to sort");@b@ }@b@ for (int i = 0; i < arrays.length; i++) {@b@ if (!arrays[i].getClass().isArray()) {@b@ throw new IllegalArgumentException(arrays[i].getClass() + " is not an array");@b@ }@b@ }@b@ new ParallelSorterEmitter(v, getClassName(), arrays);@b@ }@b@ @b@ protected Object firstInstance(Class type) {@b@ return ((ParallelSorter)ReflectUtils.newInstance(type)).newInstance(arrays);@b@ }@b@@b@ protected Object nextInstance(Object instance) {@b@ return ((ParallelSorter)instance).newInstance(arrays);@b@ }@b@ }@b@}
2.基类排序模板类SorterTemplate
package net.sf.cglib.util;@b@@b@import java.util.*;@b@@b@abstract class SorterTemplate {@b@ private static final int MERGESORT_THRESHOLD = 12;@b@ private static final int QUICKSORT_THRESHOLD = 7;@b@@b@ abstract protected void swap(int i, int j);@b@ abstract protected int compare(int i, int j);@b@@b@ protected void quickSort(int lo, int hi) {@b@ quickSortHelper(lo, hi);@b@ insertionSort(lo, hi);@b@ }@b@@b@ private void quickSortHelper(int lo, int hi) {@b@ for (;;) {@b@ int diff = hi - lo;@b@ if (diff <= QUICKSORT_THRESHOLD) {@b@ break;@b@ }@b@ int i = (hi + lo) / 2;@b@ if (compare(lo, i) > 0) {@b@ swap(lo, i);@b@ }@b@ if (compare(lo, hi) > 0) {@b@ swap(lo, hi);@b@ }@b@ if (compare(i, hi) > 0) {@b@ swap(i, hi);@b@ }@b@ int j = hi - 1;@b@ swap(i, j);@b@ i = lo;@b@ int v = j;@b@ for (;;) {@b@ while (compare(++i, v) < 0) {@b@ /* nothing */;@b@ }@b@ while (compare(--j, v) > 0) {@b@ /* nothing */;@b@ }@b@ if (j < i) {@b@ break;@b@ }@b@ swap(i, j);@b@ }@b@ swap(i, hi - 1);@b@ if (j - lo <= hi - i + 1) {@b@ quickSortHelper(lo, j);@b@ lo = i + 1;@b@ } else {@b@ quickSortHelper(i + 1, hi);@b@ hi = j;@b@ }@b@ }@b@ }@b@ @b@ private void insertionSort(int lo, int hi) {@b@ for (int i = lo + 1 ; i <= hi; i++) {@b@ for (int j = i; j > lo; j--) {@b@ if (compare(j - 1, j) > 0) {@b@ swap(j - 1, j);@b@ } else {@b@ break;@b@ }@b@ }@b@ }@b@ }@b@@b@ protected void mergeSort(int lo, int hi) {@b@ int diff = hi - lo;@b@ if (diff <= MERGESORT_THRESHOLD) {@b@ insertionSort(lo, hi);@b@ return;@b@ }@b@ int mid = lo + diff / 2;@b@ mergeSort(lo, mid);@b@ mergeSort(mid, hi);@b@ merge(lo, mid, hi, mid - lo, hi - mid);@b@ }@b@@b@ private void merge(int lo, int pivot, int hi, int len1, int len2) {@b@ if (len1 == 0 || len2 == 0) {@b@ return;@b@ }@b@ if (len1 + len2 == 2) {@b@ if (compare(pivot, lo) < 0) {@b@ swap(pivot, lo);@b@ }@b@ return;@b@ }@b@ int first_cut, second_cut;@b@ int len11, len22;@b@ if (len1 > len2) {@b@ len11 = len1 / 2;@b@ first_cut = lo + len11;@b@ second_cut = lower(pivot, hi, first_cut);@b@ len22 = second_cut - pivot;@b@ } else {@b@ len22 = len2 / 2;@b@ second_cut = pivot + len22;@b@ first_cut = upper(lo, pivot, second_cut);@b@ len11 = first_cut - lo;@b@ }@b@ rotate(first_cut, pivot, second_cut);@b@ int new_mid = first_cut + len22;@b@ merge(lo, first_cut, new_mid, len11, len22);@b@ merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);@b@ }@b@@b@ private void rotate(int lo, int mid, int hi) {@b@ int lot = lo;@b@ int hit = mid - 1;@b@ while (lot < hit) {@b@ swap(lot++, hit--);@b@ }@b@ lot = mid; hit = hi - 1;@b@ while (lot < hit) {@b@ swap(lot++, hit--);@b@ }@b@ lot = lo; hit = hi - 1;@b@ while (lot < hit) {@b@ swap(lot++, hit--);@b@ }@b@ }@b@@b@ private int lower(int lo, int hi, int val) {@b@ int len = hi - lo;@b@ while (len > 0) {@b@ int half = len / 2;@b@ int mid= lo + half;@b@ if (compare(mid, val) < 0) {@b@ lo = mid + 1;@b@ len = len - half -1;@b@ } else {@b@ len = half;@b@ }@b@ }@b@ return lo;@b@ }@b@@b@ private int upper(int lo, int hi, int val) {@b@ int len = hi - lo;@b@ while (len > 0) {@b@ int half = len / 2;@b@ int mid = lo + half;@b@ if (compare(val, mid) < 0) {@b@ len = half;@b@ } else {@b@ lo = mid + 1;@b@ len = len - half -1;@b@ }@b@ }@b@ return lo;@b@ }@b@}