001: /*
002: * Copyright 2003 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package net.sf.cglib.util;
017:
018: import java.lang.reflect.*;
019: import java.util.Comparator;
020: import net.sf.cglib.core.*;
021: import org.objectweb.asm.ClassVisitor;
022:
023: /**
024: * For the efficient sorting of multiple arrays in parallel.
025: * <p>
026: * Given two arrays of equal length and varying types, the standard
027: * technique for sorting them in parallel is to create a new temporary
028: * object for each row, store the objects in a temporary array, sort the
029: * array using a custom comparator, and the extract the original values
030: * back into their respective arrays. This is wasteful in both time and
031: * memory.
032: * <p>
033: * This class generates bytecode customized to the particular set of
034: * arrays you need to sort, in such a way that both arrays are sorted
035: * in-place, simultaneously.
036: * <p>
037: * Two sorting algorithms are provided.
038: * Quicksort is best when you only need to sort by a single column, as
039: * it requires very few comparisons and swaps. Mergesort is best used
040: * when sorting multiple columns, as it is a "stable" sort--that is, it
041: * does not affect the relative order of equal objects from previous sorts.
042: * <p>
043: * The mergesort algorithm here is an "in-place" variant, which while
044: * slower, does not require a temporary array.
045: *
046: * @author Chris Nokleberg
047: */
048: abstract public class ParallelSorter extends SorterTemplate {
049: protected Object[] a;
050: private Comparer comparer;
051:
052: protected ParallelSorter() {
053: }
054:
055: abstract public ParallelSorter newInstance(Object[] arrays);
056:
057: /**
058: * Create a new ParallelSorter object for a set of arrays. You may
059: * sort the arrays multiple times via the same ParallelSorter object.
060: * @param arrays An array of arrays to sort. The arrays may be a mix
061: * of primitive and non-primitive types, but should all be the same
062: * length.
063: * @param loader ClassLoader for generated class, uses "current" if null
064: */
065: public static ParallelSorter create(Object[] arrays) {
066: Generator gen = new Generator();
067: gen.setArrays(arrays);
068: return gen.create();
069: }
070:
071: private int len() {
072: return ((Object[]) a[0]).length;
073: }
074:
075: /**
076: * Sort the arrays using the quicksort algorithm.
077: * @param index array (column) to sort by
078: */
079: public void quickSort(int index) {
080: quickSort(index, 0, len(), null);
081: }
082:
083: /**
084: * Sort the arrays using the quicksort algorithm.
085: * @param index array (column) to sort by
086: * @param lo starting array index (row), inclusive
087: * @param hi ending array index (row), exclusive
088: */
089: public void quickSort(int index, int lo, int hi) {
090: quickSort(index, lo, hi, null);
091: }
092:
093: /**
094: * Sort the arrays using the quicksort algorithm.
095: * @param index array (column) to sort by
096: * @param cmp Comparator to use if the specified column is non-primitive
097: */
098: public void quickSort(int index, Comparator cmp) {
099: quickSort(index, 0, len(), cmp);
100: }
101:
102: /**
103: * Sort the arrays using the quicksort algorithm.
104: * @param index array (column) to sort by
105: * @param lo starting array index (row), inclusive
106: * @param hi ending array index (row), exclusive
107: * @param cmp Comparator to use if the specified column is non-primitive
108: */
109: public void quickSort(int index, int lo, int hi, Comparator cmp) {
110: chooseComparer(index, cmp);
111: super .quickSort(lo, hi - 1);
112: }
113:
114: /**
115: * @param index array (column) to sort by
116: */
117: public void mergeSort(int index) {
118: mergeSort(index, 0, len(), null);
119: }
120:
121: /**
122: * Sort the arrays using an in-place merge sort.
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 mergeSort(int index, int lo, int hi) {
128: mergeSort(index, lo, hi, null);
129: }
130:
131: /**
132: * Sort the arrays using an in-place merge sort.
133: * @param index array (column) to sort by
134: * @param lo starting array index (row), inclusive
135: * @param hi ending array index (row), exclusive
136: */
137: public void mergeSort(int index, Comparator cmp) {
138: mergeSort(index, 0, len(), cmp);
139: }
140:
141: /**
142: * Sort the arrays using an in-place merge sort.
143: * @param index array (column) to sort by
144: * @param lo starting array index (row), inclusive
145: * @param hi ending array index (row), exclusive
146: * @param cmp Comparator to use if the specified column is non-primitive
147: */
148: public void mergeSort(int index, int lo, int hi, Comparator cmp) {
149: chooseComparer(index, cmp);
150: super .mergeSort(lo, hi - 1);
151: }
152:
153: private void chooseComparer(int index, Comparator cmp) {
154: Object array = a[index];
155: Class type = array.getClass().getComponentType();
156: if (type.equals(Integer.TYPE)) {
157: comparer = new IntComparer((int[]) array);
158: } else if (type.equals(Long.TYPE)) {
159: comparer = new LongComparer((long[]) array);
160: } else if (type.equals(Double.TYPE)) {
161: comparer = new DoubleComparer((double[]) array);
162: } else if (type.equals(Float.TYPE)) {
163: comparer = new FloatComparer((float[]) array);
164: } else if (type.equals(Short.TYPE)) {
165: comparer = new ShortComparer((short[]) array);
166: } else if (type.equals(Byte.TYPE)) {
167: comparer = new ByteComparer((byte[]) array);
168: } else if (cmp != null) {
169: comparer = new ComparatorComparer((Object[]) array, cmp);
170: } else {
171: comparer = new ObjectComparer((Object[]) array);
172: }
173: }
174:
175: protected int compare(int i, int j) {
176: return comparer.compare(i, j);
177: }
178:
179: interface Comparer {
180: int compare(int i, int j);
181: }
182:
183: static class ComparatorComparer implements Comparer {
184: private Object[] a;
185: private Comparator cmp;
186:
187: public ComparatorComparer(Object[] a, Comparator cmp) {
188: this .a = a;
189: this .cmp = cmp;
190: }
191:
192: public int compare(int i, int j) {
193: return cmp.compare(a[i], a[j]);
194: }
195: }
196:
197: static class ObjectComparer implements Comparer {
198: private Object[] a;
199:
200: public ObjectComparer(Object[] a) {
201: this .a = a;
202: }
203:
204: public int compare(int i, int j) {
205: return ((Comparable) a[i]).compareTo(a[j]);
206: }
207: }
208:
209: static class IntComparer implements Comparer {
210: private int[] a;
211:
212: public IntComparer(int[] a) {
213: this .a = a;
214: }
215:
216: public int compare(int i, int j) {
217: return a[i] - a[j];
218: }
219: }
220:
221: static class LongComparer implements Comparer {
222: private long[] a;
223:
224: public LongComparer(long[] a) {
225: this .a = a;
226: }
227:
228: public int compare(int i, int j) {
229: long vi = a[i];
230: long vj = a[j];
231: return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
232: }
233: }
234:
235: static class FloatComparer implements Comparer {
236: private float[] a;
237:
238: public FloatComparer(float[] a) {
239: this .a = a;
240: }
241:
242: public int compare(int i, int j) {
243: float vi = a[i];
244: float vj = a[j];
245: return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
246: }
247: }
248:
249: static class DoubleComparer implements Comparer {
250: private double[] a;
251:
252: public DoubleComparer(double[] a) {
253: this .a = a;
254: }
255:
256: public int compare(int i, int j) {
257: double vi = a[i];
258: double vj = a[j];
259: return (vi == vj) ? 0 : (vi > vj) ? 1 : -1;
260: }
261: }
262:
263: static class ShortComparer implements Comparer {
264: private short[] a;
265:
266: public ShortComparer(short[] a) {
267: this .a = a;
268: }
269:
270: public int compare(int i, int j) {
271: return a[i] - a[j];
272: }
273: }
274:
275: static class ByteComparer implements Comparer {
276: private byte[] a;
277:
278: public ByteComparer(byte[] a) {
279: this .a = a;
280: }
281:
282: public int compare(int i, int j) {
283: return a[i] - a[j];
284: }
285: }
286:
287: public static class Generator extends AbstractClassGenerator {
288: private static final Source SOURCE = new Source(
289: ParallelSorter.class.getName());
290:
291: private Object[] arrays;
292:
293: public Generator() {
294: super (SOURCE);
295: }
296:
297: protected ClassLoader getDefaultClassLoader() {
298: return null; // TODO
299: }
300:
301: public void setArrays(Object[] arrays) {
302: this .arrays = arrays;
303: }
304:
305: public ParallelSorter create() {
306: return (ParallelSorter) super .create(ClassesKey
307: .create(arrays));
308: }
309:
310: public void generateClass(ClassVisitor v) throws Exception {
311: if (arrays.length == 0) {
312: throw new IllegalArgumentException(
313: "No arrays specified to sort");
314: }
315: for (int i = 0; i < arrays.length; i++) {
316: if (!arrays[i].getClass().isArray()) {
317: throw new IllegalArgumentException(arrays[i]
318: .getClass()
319: + " is not an array");
320: }
321: }
322: new ParallelSorterEmitter(v, getClassName(), arrays);
323: }
324:
325: protected Object firstInstance(Class type) {
326: return ((ParallelSorter) ReflectUtils.newInstance(type))
327: .newInstance(arrays);
328: }
329:
330: protected Object nextInstance(Object instance) {
331: return ((ParallelSorter) instance).newInstance(arrays);
332: }
333: }
334: }
|