Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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;
 
 
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(s):
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.

Parameters:
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
 
     public static ParallelSorter create(Object[] arrays) {
         Generator gen = new Generator();
         gen.setArrays(arrays);
         return gen.create();
     }
 
     private int len() {
         return ((Object[])[0]).length;
     }

    
Sort the arrays using the quicksort algorithm.

Parameters:
index array (column) to sort by
 
     public void quickSort(int index) {
         quickSort(index, 0, len(), null);
     }

    
Sort the arrays using the quicksort algorithm.

Parameters:
index array (column) to sort by
lo starting array index (row), inclusive
hi ending array index (row), exclusive
 
     public void quickSort(int indexint loint hi) {
         quickSort(indexlohinull);
     }

    
Sort the arrays using the quicksort algorithm.

Parameters:
index array (column) to sort by
cmp Comparator to use if the specified column is non-primitive
 
     public void quickSort(int indexComparator cmp) {
        quickSort(index, 0, len(), cmp);
    }

    
Sort the arrays using the quicksort algorithm.

Parameters:
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
    public void quickSort(int indexint loint hiComparator cmp) {
        chooseComparer(indexcmp);
        super.quickSort(lo, hi - 1);
    }

    

Parameters:
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.

Parameters:
index array (column) to sort by
lo starting array index (row), inclusive
hi ending array index (row), exclusive
    public void mergeSort(int indexint loint hi) {
        mergeSort(indexlohinull);
    }

    
Sort the arrays using an in-place merge sort.

Parameters:
index array (column) to sort by
lo starting array index (row), inclusive
hi ending array index (row), exclusive
    public void mergeSort(int indexComparator cmp) {
        mergeSort(index, 0, len(), cmp);
    }

    
Sort the arrays using an in-place merge sort.

Parameters:
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
    public void mergeSort(int indexint loint hiComparator cmp) {
        chooseComparer(indexcmp);
        super.mergeSort(lo, hi - 1);
    }
    
    private void chooseComparer(int indexComparator cmp) {
        Object array = [index];
        Class type = array.getClass().getComponentType();
        if (type.equals(.)) {
             = new IntComparer((int[])array);
        } else if (type.equals(.)) {
             = new LongComparer((long[])array);
        } else if (type.equals(.)) {
             = new DoubleComparer((double[])array);
        } else if (type.equals(.)) {
             = new FloatComparer((float[])array);
        } else if (type.equals(.)) {
             = new ShortComparer((short[])array);
        } else if (type.equals(.)) {
             = new ByteComparer((byte[])array);
        } else if (cmp != null) {
             = new ComparatorComparer((Object[])arraycmp);
        } else {
             = new ObjectComparer((Object[])array);
        } 
    }
    protected int compare(int iint j) {
        return .compare(ij);
    }
    interface Comparer {
        int compare(int iint j);
    }
    static class ComparatorComparer implements Comparer {
        private Object[] a;
        private Comparator cmp;
        public ComparatorComparer(Object[] aComparator cmp) {
            this. = a;
            this. = cmp;
        }
        public int compare(int iint j) {
            return .compare([i], [j]);
        }
    }
    
    static class ObjectComparer implements Comparer {
        private Object[] a;
        public ObjectComparer(Object[] a) { this. = a; }
        public int compare(int iint j) {
            return ((Comparable)[i]).compareTo([j]);
        }
    }
    static class IntComparer implements Comparer {
        private int[] a;
        public IntComparer(int[] a) { this. = a; }
        public int compare(int iint j) { return [i] - [j]; }
    }
    static class LongComparer implements Comparer {
        private long[] a;
        public LongComparer(long[] a) { this. = a; }
        public int compare(int iint j) {
            long vi = [i];
            long vj = [j];
            return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
        }
    }
    static class FloatComparer implements Comparer {
        private float[] a;
        public FloatComparer(float[] a) { this. = a; }
        public int compare(int iint j) {
            float vi = [i];
            float vj = [j];
            return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
        }
    }
    
    static class DoubleComparer implements Comparer {
        private double[] a;
        public DoubleComparer(double[] a) { this. = a; }
        public int compare(int iint j) {
            double vi = [i];
            double vj = [j];
            return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
        }
    }
    static class ShortComparer implements Comparer {
        private short[] a;
        public ShortComparer(short[] a) { this. = a; }
        public int compare(int iint j) { return [i] - [j]; }
    }
    static class ByteComparer implements Comparer {
        private byte[] a;
        public ByteComparer(byte[] a) { this. = a; }
        public int compare(int iint j) { return [i] - [j]; }
    }
    public static class Generator extends AbstractClassGenerator {
        private static final Source SOURCE = new Source(ParallelSorter.class.getName());
        private Object[] arrays;
        public Generator() {
            super();
        }
        protected ClassLoader getDefaultClassLoader() {
            return null// TODO
        }
        public void setArrays(Object[] arrays) {
            this. = arrays;
        }
        public ParallelSorter create() {
            return (ParallelSorter)super.create(ClassesKey.create());
        }
        public void generateClass(ClassVisitor vthrows Exception {
            if (. == 0) {
                throw new IllegalArgumentException("No arrays specified to sort");
            }
            for (int i = 0; i < .i++) {
                if (![i].getClass().isArray()) {
                    throw new IllegalArgumentException([i].getClass() + " is not an array");
                }
            }
            new ParallelSorterEmitter(vgetClassName(), );
        }
        
        protected Object firstInstance(Class type) {
            return ((ParallelSorter)ReflectUtils.newInstance(type)).newInstance();
        }
        protected Object nextInstance(Object instance) {
            return ((ParallelSorter)instance).newInstance();
        }
    }
New to GrepCode? Check out our FAQ X