1 /*
2 * The Apache Software License, Version 1.1
3 *
4 * Copyright (c) 2003 The Apache Software Foundation. All rights
5 * reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 * if any, must include the following acknowledgment:
21 * "This product includes software developed by the
22 * Apache Software Foundation (http://www.apache.org/)."
23 * Alternately, this acknowledgment may appear in the software itself,
24 * if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "Apache" and "Apache Software Foundation" must
27 * not be used to endorse or promote products derived from this
28 * software without prior written permission. For written
29 * permission, please contact apache@apache.org.
30 *
31 * 5. Products derived from this software may not be called "Apache",
32 * nor may "Apache" appear in their name, without prior written
33 * permission of the Apache Software Foundation.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46 * SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Apache Software Foundation. For more
51 * information on the Apache Software Foundation, please see
52 * <http://www.apache.org/>;.
53 */
54 package net.sf.cglib.util;
55
56 import java.lang.reflect.*;
57 import java.util.Comparator;
58 import net.sf.cglib.core.*;
59 import org.objectweb.asm.ClassVisitor;
60
61 /***
62 * For the efficient sorting of multiple arrays in parallel.
63 * <p>
64 * Given two arrays of equal length and varying types, the standard
65 * technique for sorting them in parallel is to create a new temporary
66 * object for each row, store the objects in a temporary array, sort the
67 * array using a custom comparator, and the extract the original values
68 * back into their respective arrays. This is wasteful in both time and
69 * memory.
70 * <p>
71 * This class generates bytecode customized to the particular set of
72 * arrays you need to sort, in such a way that both arrays are sorted
73 * in-place, simultaneously.
74 * <p>
75 * Two sorting algorithms are provided.
76 * Quicksort is best when you only need to sort by a single column, as
77 * it requires very few comparisons and swaps. Mergesort is best used
78 * when sorting multiple columns, as it is a "stable" sort--that is, it
79 * does not affect the relative order of equal objects from previous sorts.
80 * <p>
81 * The mergesort algorithm here is an "in-place" variant, which while
82 * slower, does not require a temporary array.
83 *
84 * @author Chris Nokleberg
85 */
86 abstract public class ParallelSorter extends SorterTemplate {
87 protected Object[] a;
88 private Comparer comparer;
89
90 protected ParallelSorter() {
91 }
92
93 abstract public ParallelSorter newInstance(Object[] arrays);
94
95 /***
96 * Create a new ParallelSorter object for a set of arrays. You may
97 * sort the arrays multiple times via the same ParallelSorter object.
98 * @param arrays An array of arrays to sort. The arrays may be a mix
99 * of primitive and non-primitive types, but should all be the same
100 * length.
101 * @param loader ClassLoader for generated class, uses "current" if null
102 */
103 public static ParallelSorter create(Object[] arrays) {
104 Generator gen = new Generator();
105 gen.setArrays(arrays);
106 return gen.create();
107 }
108
109 private int len() {
110 return ((Object[])a[0]).length;
111 }
112
113 /***
114 * Sort the arrays using the quicksort algorithm.
115 * @param index array (column) to sort by
116 */
117 public void quickSort(int index) {
118 quickSort(index, 0, len(), null);
119 }
120
121 /***
122 * Sort the arrays using the quicksort algorithm.
123 * @param index array (column) to sort by
124 * @param lo starting array index (row), inclusive
125 * @param hi ending array index (row), exclusive
126 */
127 public void quickSort(int index, int lo, int hi) {
128 quickSort(index, lo, hi, null);
129 }
130
131 /***
132 * Sort the arrays using the quicksort algorithm.
133 * @param index array (column) to sort by
134 * @param cmp Comparator to use if the specified column is non-primitive
135 */
136 public void quickSort(int index, Comparator cmp) {
137 quickSort(index, 0, len(), cmp);
138 }
139
140 /***
141 * Sort the arrays using the quicksort algorithm.
142 * @param index array (column) to sort by
143 * @param lo starting array index (row), inclusive
144 * @param hi ending array index (row), exclusive
145 * @param cmp Comparator to use if the specified column is non-primitive
146 */
147 public void quickSort(int index, int lo, int hi, Comparator cmp) {
148 chooseComparer(index, cmp);
149 super.quickSort(lo, hi - 1);
150 }
151
152 /***
153 * @param index array (column) to sort by
154 */
155 public void mergeSort(int index) {
156 mergeSort(index, 0, len(), null);
157 }
158
159 /***
160 * Sort the arrays using an in-place merge sort.
161 * @param index array (column) to sort by
162 * @param lo starting array index (row), inclusive
163 * @param hi ending array index (row), exclusive
164 */
165 public void mergeSort(int index, int lo, int hi) {
166 mergeSort(index, lo, hi, null);
167 }
168
169 /***
170 * Sort the arrays using an in-place merge sort.
171 * @param index array (column) to sort by
172 * @param lo starting array index (row), inclusive
173 * @param hi ending array index (row), exclusive
174 */
175 public void mergeSort(int index, Comparator cmp) {
176 mergeSort(index, 0, len(), cmp);
177 }
178
179 /***
180 * Sort the arrays using an in-place merge sort.
181 * @param index array (column) to sort by
182 * @param lo starting array index (row), inclusive
183 * @param hi ending array index (row), exclusive
184 * @param cmp Comparator to use if the specified column is non-primitive
185 */
186 public void mergeSort(int index, int lo, int hi, Comparator cmp) {
187 chooseComparer(index, cmp);
188 super.mergeSort(lo, hi - 1);
189 }
190
191 private void chooseComparer(int index, Comparator cmp) {
192 Object array = a[index];
193 Class type = array.getClass().getComponentType();
194 if (type.equals(Integer.TYPE)) {
195 comparer = new IntComparer((int[])array);
196 } else if (type.equals(Long.TYPE)) {
197 comparer = new LongComparer((long[])array);
198 } else if (type.equals(Double.TYPE)) {
199 comparer = new DoubleComparer((double[])array);
200 } else if (type.equals(Float.TYPE)) {
201 comparer = new FloatComparer((float[])array);
202 } else if (type.equals(Short.TYPE)) {
203 comparer = new ShortComparer((short[])array);
204 } else if (type.equals(Byte.TYPE)) {
205 comparer = new ByteComparer((byte[])array);
206 } else if (cmp != null) {
207 comparer = new ComparatorComparer((Object[])array, cmp);
208 } else {
209 comparer = new ObjectComparer((Object[])array);
210 }
211 }
212
213 protected int compare(int i, int j) {
214 return comparer.compare(i, j);
215 }
216
217 interface Comparer {
218 int compare(int i, int j);
219 }
220
221 static class ComparatorComparer implements Comparer {
222 private Object[] a;
223 private Comparator cmp;
224
225 public ComparatorComparer(Object[] a, Comparator cmp) {
226 this.a = a;
227 this.cmp = cmp;
228 }
229
230 public int compare(int i, int j) {
231 return cmp.compare(a[i], a[j]);
232 }
233 }
234
235 static class ObjectComparer implements Comparer {
236 private Object[] a;
237 public ObjectComparer(Object[] a) { this.a = a; }
238 public int compare(int i, int j) {
239 return ((Comparable)a[i]).compareTo(a[j]);
240 }
241 }
242
243 static class IntComparer implements Comparer {
244 private int[] a;
245 public IntComparer(int[] a) { this.a = a; }
246 public int compare(int i, int j) { return a[i] - a[j]; }
247 }
248
249 static class LongComparer implements Comparer {
250 private long[] a;
251 public LongComparer(long[] a) { this.a = a; }
252 public int compare(int i, int j) {
253 long vi = a[i];
254 long vj = a[j];
255 return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
256 }
257 }
258
259 static class FloatComparer implements Comparer {
260 private float[] a;
261 public FloatComparer(float[] a) { this.a = a; }
262 public int compare(int i, int j) {
263 float vi = a[i];
264 float vj = a[j];
265 return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
266 }
267 }
268
269 static class DoubleComparer implements Comparer {
270 private double[] a;
271 public DoubleComparer(double[] a) { this.a = a; }
272 public int compare(int i, int j) {
273 double vi = a[i];
274 double vj = a[j];
275 return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
276 }
277 }
278
279 static class ShortComparer implements Comparer {
280 private short[] a;
281 public ShortComparer(short[] a) { this.a = a; }
282 public int compare(int i, int j) { return a[i] - a[j]; }
283 }
284
285 static class ByteComparer implements Comparer {
286 private byte[] a;
287 public ByteComparer(byte[] a) { this.a = a; }
288 public int compare(int i, int j) { return a[i] - a[j]; }
289 }
290
291 public static class Generator extends AbstractClassGenerator {
292 private static final Source SOURCE = new Source(ParallelSorter.class.getName());
293
294 private Object[] arrays;
295
296 public Generator() {
297 super(SOURCE);
298 }
299
300 protected ClassLoader getDefaultClassLoader() {
301 return null; // TODO
302 }
303
304 public void setArrays(Object[] arrays) {
305 this.arrays = arrays;
306 }
307
308 public ParallelSorter create() {
309 return (ParallelSorter)super.create(ClassesKey.create(arrays));
310 }
311
312 public void generateClass(ClassVisitor v) throws Exception {
313 if (arrays.length == 0) {
314 throw new IllegalArgumentException("No arrays specified to sort");
315 }
316 for (int i = 0; i < arrays.length; i++) {
317 if (!arrays[i].getClass().isArray()) {
318 throw new IllegalArgumentException(arrays[i].getClass() + " is not an array");
319 }
320 }
321 new ParallelSorterEmitter(v, getClassName(), arrays);
322 }
323
324 protected Object firstInstance(Class type) {
325 return ((ParallelSorter)ReflectUtils.newInstance(type)).newInstance(arrays);
326 }
327
328 protected Object nextInstance(Object instance) {
329 return ((ParallelSorter)instance).newInstance(arrays);
330 }
331 }
332 }
This page was automatically generated by Maven