首页

关于cglib的定义实现ParallelSorter并行排序器对所有数据类型进行快速排序quickSort

标签:ParallelSorter,排序器,SorterTemplate,cglib     发布时间:2018-03-25   

一、前言

关于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@}