cglib/util/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 org.mockito.cglib.util;

import java.lang.reflect.*;
import java.util.Comparator;

import org.mockito.asm.ClassVisitor;
import org.mockito.cglib.core.*;

/**
 * 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);
        }
    }
}