/*
 * 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.

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/**
 * 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.
Params:
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/**
     * 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.
Params:
index – array (column) to sort by/**
     * 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.
Params:
index – array (column) to sort by
lo – starting array index (row), inclusive
hi – ending array index (row), exclusive/**
     * 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.
Params:
index – array (column) to sort by
cmp – Comparator to use if the specified column is non-primitive/**
     * 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.
Params:
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/**
     * 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);
    }

    
Params:
index – array (column) to sort by/**
     * @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.
Params:
index – array (column) to sort by
lo – starting array index (row), inclusive
hi – ending array index (row), exclusive/**
     * 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.
Params:
index – array (column) to sort by
lo – starting array index (row), inclusive
hi – ending array index (row), exclusive/**
     * 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.
Params:
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/**
     * 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);
        }
    }
}