001: /*
002: * Sort.java
003: *
004: * Brazil project web application Framework,
005: * export version: 1.1
006: * Copyright (c) 1999 Sun Microsystems, Inc.
007: *
008: * Sun Public License Notice
009: *
010: * The contents of this file are subject to the Sun Public License Version
011: * 1.0 (the "License"). You may not use this file except in compliance with
012: * the License. A copy of the License is included as the file "license.terms",
013: * and also available at http://www.sun.com/
014: *
015: * The Original Code is from:
016: * Brazil project web application Framework release 1.1.
017: * The Initial Developer of the Original Code is: suhler.
018: * Portions created by suhler are Copyright (C) Sun Microsystems, Inc.
019: * All Rights Reserved.
020: *
021: * Contributor(s): cstevens, suhler.
022: *
023: * Version: 1.5
024: * Created by suhler on 99/08/05
025: * Last modified by cstevens on 99/10/14 12:57:25
026: */
027:
028: package sunlabs.brazil.util;
029:
030: import java.util.Vector;
031: import java.lang.reflect.Array;
032:
033: /**
034: * Placeholder for useful sorting utilities.
035: *
036: * Sort a vector of Strings
037: *
038: * @author Stephen Uhler (stephen.uhler@sun.com)
039: * @author Colin Stevens (colin.stevens@sun.com)
040: * @version 1.5, 99/10/14
041: */
042:
043: public class Sort {
044: /**
045: * Sort a vector of strings using the Qsort algorithm.
046: * The compareTo method of the String class is used for comparison
047: */
048:
049: public static void qsort(Vector strings) {
050: qsort(strings, 0, strings.size() - 1);
051: }
052:
053: private static void qsort(Vector A, int p, int r) {
054: while (p < r) {
055: int q = partition(A, p, r);
056: qsort(A, p, q);
057: p = q + 1;
058: }
059: }
060:
061: private static int partition(Vector A, int p, int r) {
062: int z = (r + p) / 2;
063: String x = A.elementAt(z).toString();
064: int i = p - 1;
065: int j = r + 1;
066:
067: while (true) {
068: while (x.compareTo(A.elementAt(--j).toString()) < 0)
069: ;
070: while (x.compareTo(A.elementAt(++i).toString()) > 0)
071: ;
072:
073: if (i >= j) {
074: return j;
075: }
076:
077: Object o = A.elementAt(i);
078: A.setElementAt(A.elementAt(j), i);
079: A.setElementAt(o, j);
080: }
081: }
082:
083: /**
084: * This interface is used by the <code>Sort</code> class to compare
085: * elements when an array is being sorted.
086: *
087: * @author Colin Stevens (colin.stevens@sun.com)
088: * @version 1.5, 99/10/14
089: */
090: public interface Compare {
091: /**
092: * Compare two elements in the given array. The implementor must
093: * know what the actual type of the array is and cast it to that
094: * type in order to do the comparison.
095: *
096: * @param array
097: * Array being sorted.
098: *
099: * @param index1
100: * The index in the given array of the first element to
101: * compare.
102: *
103: * @param index2
104: * The index in the given array of the second element to
105: * compare.
106: *
107: * @return The implementation must return a number less than,
108: * equal to, or greater than zero to indicate whether
109: * the array element at <code>index1</code> should be
110: * considered less than, equal to, or greater than the
111: * array element at <code>index2</code>.
112: */
113: int compare(Object array, int index1, int index2);
114: }
115:
116: /**
117: * Sorts an array of the basic types (ints, floats, bytes, etc.) or
118: * Strings. The sort is in increasing order, and is case-sensitive
119: * for strings. Sorting an array of booleans or an array of objects
120: * other than Strings is not supported.
121: *
122: * @param array
123: * The array to sort in place.
124: *
125: * @throws IllegalArgumentException
126: * if <code>array</code> is not an array of the types listed
127: * above.
128: */
129: public static void qsort(Object array)
130: throws IllegalArgumentException {
131: qsort(array, new StandardCompare(array));
132: }
133:
134: /**
135: * Sorts an array. The specified comparator is used to control the
136: * sorting order. Arrays of any type may be sorted, depending upon
137: * what the comparator accepts.
138: *
139: * @param array
140: * The array to sort in place.
141: *
142: * @param compare
143: * The comparator for sort order.
144: *
145: * @throws IllegalArgumentException
146: * if <code>array</code> is not an array.
147: */
148: public static void qsort(Object array, Compare compare)
149: throws IllegalArgumentException {
150: qsort(array, 0, Array.getLength(array) - 1, compare);
151: }
152:
153: private static void qsort(Object A, int p, int r, Compare compare) {
154: while (p < r) {
155: int q = partition(A, p, r, compare);
156: qsort(A, p, q, compare);
157: p = q + 1;
158: }
159: }
160:
161: private static int partition(Object A, int p, int r, Compare compare) {
162: int z = (r + p) / 2;
163: int i = p - 1;
164: int j = r + 1;
165:
166: while (true) {
167: while (compare.compare(A, z, --j) < 0) {
168: /* do nothing. */
169: }
170: while (compare.compare(A, z, ++i) > 0) {
171: /* do nothing. */
172: }
173: if (i >= j) {
174: return j;
175: }
176:
177: Object o = Array.get(A, i);
178: Array.set(A, i, Array.get(A, j));
179: Array.set(A, j, o);
180:
181: if (z == i) {
182: z = j;
183: } else if (z == j) {
184: z = i;
185: }
186: }
187: }
188:
189: private static final class StandardCompare implements Sort.Compare {
190: /*
191: * Keep the two expected cases near the front.
192: */
193: private static final int STRING = 0;
194: private static final int INT = 1;
195:
196: private static final int BYTE = 2;
197: private static final int CHAR = 3;
198: private static final int SHORT = 4;
199: private static final int LONG = 5;
200: private static final int FLOAT = 6;
201: private static final int DOUBLE = 7;
202:
203: int type;
204:
205: StandardCompare(Object array) throws IllegalArgumentException {
206: if (array.getClass().isArray() == false) {
207: /*
208: * Let the qsort routine throw the "not an array exception".
209: */
210: return;
211: } else if (array instanceof String[]) {
212: type = STRING;
213: } else if (array instanceof int[]) {
214: type = INT;
215: } else if (array instanceof byte[]) {
216: type = BYTE;
217: } else if (array instanceof char[]) {
218: type = CHAR;
219: } else if (array instanceof short[]) {
220: type = SHORT;
221: } else if (array instanceof long[]) {
222: type = LONG;
223: } else if (array instanceof float[]) {
224: type = FLOAT;
225: } else if (array instanceof double[]) {
226: type = DOUBLE;
227: } else {
228: throw new IllegalArgumentException(
229: "cannot sort array of"
230: + array.getClass().getComponentType()
231: .getName());
232: }
233: }
234:
235: public int compare(Object array, int index1, int index2) {
236: switch (type) {
237: case STRING: {
238: String[] a = (String[]) array;
239: String str1 = a[index1];
240: String str2 = a[index2];
241: return str1.compareTo(str2);
242: }
243: case INT: {
244: int[] a = (int[]) array;
245: int i1 = a[index1];
246: int i2 = a[index2];
247: return i1 - i2;
248: }
249: case BYTE: {
250: byte[] a = (byte[]) array;
251: byte b1 = a[index1];
252: byte b2 = a[index2];
253: return b1 - b2;
254: }
255: case CHAR: {
256: char[] a = (char[]) array;
257: char c1 = a[index1];
258: char c2 = a[index2];
259: return c1 - c2;
260: }
261: case SHORT: {
262: short[] a = (short[]) array;
263: short s1 = a[index1];
264: short s2 = a[index2];
265: return s1 - s2;
266: }
267: case LONG: {
268: long[] a = (long[]) array;
269: long l1 = a[index1];
270: long l2 = a[index2];
271: if (l1 > l2) {
272: return 1;
273: } else if (l2 == l2) {
274: return 0;
275: } else {
276: return -1;
277: }
278: }
279: case FLOAT: {
280: float[] a = (float[]) array;
281: float f1 = a[index1];
282: float f2 = a[index2];
283: if (f1 > f2) {
284: return 1;
285: } else if (f1 == f2) {
286: return 0;
287: } else {
288: return -1;
289: }
290: }
291: case DOUBLE: {
292: double[] a = (double[]) array;
293: double d1 = a[index1];
294: double d2 = a[index2];
295: if (d1 > d2) {
296: return 1;
297: } else if (d1 == d2) {
298: return 0;
299: } else {
300: return -1;
301: }
302: }
303: }
304: return 0;
305: }
306: }
307: }
|