001: /*
002: * QSort.java
003: *
004: * Copyright (c) 1997 Cornell University.
005: * Copyright (c) 1997 Sun Microsystems, Inc.
006: *
007: * See the file "license.terms" for information on usage and
008: * redistribution of this file, and for a DISCLAIMER OF ALL
009: * WARRANTIES.
010: *
011: * RCS: @(#) $Id: QSort.java,v 1.4 2006/06/28 17:38:50 mdejong Exp $
012: *
013: */
014:
015: package tcl.lang;
016:
017: /*
018: * This file is adapted from the JDK 1.0 QSortAlgorithm.java demo program.
019: * Original copyright notice is preserveed below.
020: *
021: * @(#)QSortAlgorithm.java 1.3 29 Feb 1996 James Gosling
022: *
023: * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
024: *
025: * Permission to use, copy, modify, and distribute this software
026: * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
027: * without fee is hereby granted.
028: * Please refer to the file http://www.javasoft.com/copy_trademarks.html
029: * for further important copyright and trademark information and to
030: * http://www.javasoft.com/licensing.html for further important
031: * licensing information for the Java (tm) Technology.
032: *
033: * SUN MAKES NO REPRESENTATIONS OR WARRANTIES. ABOUT THE SUITABILITY OF
034: * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
035: * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
036: * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
037: * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
038: * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
039: *
040: * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
041: * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
042: * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
043: * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
044: * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
045: * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
046: * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN
047: * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
048: * HIGH RISK ACTIVITIES.
049: */
050:
051: /**
052: * Sorts an array of TclObjects.
053: */
054: final class QSort {
055: static final int ASCII = 0;
056: static final int INTEGER = 1;
057: static final int REAL = 2;
058: static final int COMMAND = 3;
059: static final int DICTIONARY = 4;
060:
061: // Data used during sort.
062:
063: private int sortMode;
064: private int sortIndex;
065: private boolean sortIncreasing;
066: private String sortCommand;
067: private Interp sortInterp;
068:
069: /**
070: * This is a generic version of C.A.R Hoare's Quick Sort
071: * algorithm. This will handle arrays that are already
072: * sorted, and arrays with duplicate keys.<BR>
073: *
074: * If you think of a one dimensional array as going from
075: * the lowest index on the left to the highest index on the right
076: * then the parameters to this function are lowest index or
077: * left and highest index or right. The first time you call
078: * this function it will be with the parameters 0, a.length - 1.
079: *
080: * @param a an integer array
081: * @param lo0 left boundary of array partition
082: * @param hi0 right boundary of array partition
083: */
084: private final void quickSort(TclObject a[], int lo0, int hi0)
085: throws TclException {
086: int lo = lo0;
087: int hi = hi0;
088: TclObject mid;
089:
090: if (hi0 > lo0) {
091: // Arbitrarily establishing partition element as the midpoint of
092: // the array.
093: mid = a[(lo0 + hi0) / 2];
094:
095: // loop through the array until indices cross
096: while (lo <= hi) {
097: // find the first element that is greater than or equal to
098: // the partition element starting from the left Index.
099:
100: while ((lo < hi0) && (compare(a[lo], mid) < 0)) {
101: ++lo;
102: }
103:
104: // find an element that is smaller than or equal to
105: // the partition element starting from the right Index.
106:
107: while ((hi > lo0) && (compare(a[hi], mid) > 0)) {
108: --hi;
109: }
110:
111: // if the indexes have not crossed, swap
112: if (lo <= hi) {
113: swap(a, lo, hi);
114: ++lo;
115: --hi;
116: }
117: }
118:
119: // If the right index has not reached the left side of array
120: // must now sort the left partition.
121:
122: if (lo0 < hi) {
123: quickSort(a, lo0, hi);
124: }
125:
126: // If the left index has not reached the right side of array
127: // must now sort the right partition.
128:
129: if (lo < hi0) {
130: quickSort(a, lo, hi0);
131: }
132: }
133: }
134:
135: /**
136: * Swaps two items in the array.
137: *
138: * @param a the array.
139: * @param i index of first item.
140: * @param j index of first item.
141: */
142: private static final void swap(TclObject a[], int i, int j) {
143: TclObject T;
144: T = a[i];
145: a[i] = a[j];
146: a[j] = T;
147: }
148:
149: /**
150: * Starts the quick sort with the given parameters.
151: *
152: * @param interp if cmd is specified, it is evaluated inside this
153: * interp.
154: * @param a the array of TclObject's to sort.
155: * @param mode the sortng mode.
156: * @param increasing true if the sorted array should be in increasing
157: * order.
158: * @param cmd the command to use for comparing items. It is used only
159: * if sortMode is COMMAND.
160: *
161: * @exception TclException if an error occurs during sorting.
162: */
163: final void sort(Interp interp, TclObject a[], int mode, int index,
164: boolean increasing, String cmd) throws TclException {
165: sortInterp = interp;
166: sortMode = mode;
167: sortIndex = index;
168: sortIncreasing = increasing;
169: sortCommand = cmd;
170: quickSort(a, 0, a.length - 1);
171: }
172:
173: /**
174: * Compares the order of two items in the array.
175: *
176: * @param obj1 first item.
177: * @param obj2 second item.
178: * @return 0 if they are equal, 1 if obj1 > obj2, -1 otherwise.
179: *
180: * @exception TclException if an error occurs during sorting.
181: */
182: private final int compare(TclObject obj1, TclObject obj2)
183: throws TclException {
184:
185: int index;
186: int code = 0;
187:
188: if (sortIndex != -1) {
189: // The "-index" option was specified. Treat each object as a
190: // list, extract the requested element from each list, and
191: // compare the elements, not the lists. The special index "end"
192: // is signaled here with a negative index (other than -1).
193:
194: TclObject obj;
195: if (sortIndex < -1) {
196: index = TclList.getLength(sortInterp, obj1) - 1;
197: } else {
198: index = sortIndex;
199: }
200:
201: obj = TclList.index(sortInterp, obj1, index);
202: if (obj == null) {
203: throw new TclException(sortInterp, "element " + index
204: + " missing from sublist \"" + obj1 + "\"");
205: }
206: obj1 = obj;
207:
208: if (sortIndex < -1) {
209: index = TclList.getLength(sortInterp, obj2) - 1;
210: } else {
211: index = sortIndex;
212: }
213:
214: obj = TclList.index(sortInterp, obj2, index);
215: if (obj == null) {
216: throw new TclException(sortInterp, "element " + index
217: + " missing from sublist \"" + obj2 + "\"");
218: }
219: obj2 = obj;
220: }
221:
222: switch (sortMode) {
223: case ASCII:
224: code = obj1.toString().compareTo(obj2.toString());
225: break;
226: case DICTIONARY:
227: code = doDictionary(obj1.toString(), obj2.toString());
228: break;
229: case INTEGER:
230: try {
231: int int1 = TclInteger.get(sortInterp, obj1);
232: int int2 = TclInteger.get(sortInterp, obj2);
233:
234: if (int1 > int2) {
235: code = 1;
236: } else if (int2 > int1) {
237: code = -1;
238: }
239: } catch (TclException e1) {
240: sortInterp
241: .addErrorInfo("\n (converting list element from string to integer)");
242: throw e1;
243: }
244: break;
245: case REAL:
246: try {
247: double f1 = TclDouble.get(sortInterp, obj1);
248: double f2 = TclDouble.get(sortInterp, obj2);
249:
250: if (f1 > f2) {
251: code = 1;
252: } else if (f2 > f1) {
253: code = -1;
254: }
255: } catch (TclException e2) {
256: sortInterp
257: .addErrorInfo("\n (converting list element from string to real)");
258: throw e2;
259: }
260: break;
261: case COMMAND:
262: StringBuffer sbuf = new StringBuffer(sortCommand);
263: Util.appendElement(sortInterp, sbuf, obj1.toString());
264: Util.appendElement(sortInterp, sbuf, obj2.toString());
265: try {
266: sortInterp.eval(sbuf.toString(), 0);
267: } catch (TclException e3) {
268: sortInterp
269: .addErrorInfo("\n (user-defined comparison command)");
270: throw e3;
271: }
272:
273: try {
274: code = TclInteger.get(sortInterp, sortInterp
275: .getResult());
276: } catch (TclException e) {
277: sortInterp.resetResult();
278: TclException e4 = new TclException(sortInterp,
279: "comparison command returned non-numeric result");
280: throw e4;
281: }
282: break;
283:
284: default:
285: // Should never come to here.
286:
287: throw new TclRuntimeError("Unknown sortMode " + sortMode);
288: }
289:
290: if (sortIncreasing) {
291: return code;
292: } else {
293: return -code;
294: }
295: }
296:
297: /**
298: * DictionaryCompare -> doDictionary
299: *
300: * Compares the order of two strings in "dictionary" order.
301: *
302: * @param str1 first item.
303: * @param str2 second item.
304: * @return 0 if they are equal, 1 if obj1 > obj2, -1 otherwise.
305: */
306: private final int doDictionary(String str1, String str2) {
307: final int len1 = str1.length();
308: final int len2 = str2.length();
309: char c1, c2;
310: int i1 = 0, i2 = 0;
311:
312: int diff = 0, zeros;
313: int secondaryDiff = 0;
314:
315: while (true) {
316: if (Character.isDigit(charAt(str2, i2, len2))
317: && Character.isDigit(charAt(str1, i1, len1))) {
318:
319: // There are decimal numbers embedded in the two
320: // strings. Compare them as numbers, rather than
321: // strings. If one number has more leading zeros than
322: // the other, the number with more leading zeros sorts
323: // later, but only as a secondary choice.
324:
325: zeros = 0;
326: while (charAt(str2, i2, len2) == '0'
327: && Character
328: .isDigit(charAt(str2, i2 + 1, len2))) {
329: i2++;
330: zeros--;
331: }
332: while (charAt(str1, i1, len1) == '0'
333: && Character
334: .isDigit(charAt(str1, i1 + 1, len1))) {
335: i1++;
336: zeros++;
337: }
338: if (secondaryDiff == 0) {
339: secondaryDiff = zeros;
340: }
341:
342: // The code below compares the numbers in the two
343: // strings without ever converting them to integers. It
344: // does this by first comparing the lengths of the
345: // numbers and then comparing the digit values.
346:
347: diff = 0;
348: while (true) {
349: if (diff == 0) {
350: diff = charAt(str1, i1, len1)
351: - charAt(str2, i2, len2);
352: }
353: i2++;
354: i1++;
355: if (!Character.isDigit(charAt(str2, i2, len2))) {
356: if (Character.isDigit(charAt(str1, i1, len1))) {
357: return 1;
358: } else {
359: // The two numbers have the same length. See
360: // if their values are different.
361:
362: if (diff != 0) {
363: return diff;
364: }
365: break;
366: }
367: } else if (!Character
368: .isDigit(charAt(str1, i1, len1))) {
369: return -1;
370: }
371: }
372: continue;
373: }
374:
375: if (charAt(str1, i1, len1) != '\0'
376: && charAt(str2, i2, len2) != '\0') {
377: c1 = charAt(str1, i1, len1);
378: i1++;
379: c2 = charAt(str2, i2, len2);
380: i2++;
381:
382: // Convert both chars to lower for the comparison, because
383: // dictionary sorts are case insensitve. Covert to lower, not
384: // upper, so chars between Z and a will sort before A (where most
385: // other interesting punctuations occur)
386:
387: c1 = Character.toLowerCase(c1);
388: c2 = Character.toLowerCase(c2);
389: } else {
390: diff = (int) (charAt(str1, i1, len1) - charAt(str2, i2,
391: len2));
392: break;
393: }
394:
395: diff = (int) (c1 - c2);
396: if (diff != 0) {
397: return diff;
398: } else if (secondaryDiff == 0) {
399: if (Character.isUpperCase(c1)
400: && Character.isLowerCase(c2)) {
401: secondaryDiff = -1;
402: } else if (Character.isUpperCase(c2)
403: && Character.isLowerCase(c1)) {
404: secondaryDiff = 1;
405: }
406: }
407: }
408: if (diff == 0) {
409: diff = secondaryDiff;
410: }
411: return diff;
412: }
413:
414: // Like String.charAt() but returns '\0' if
415: // index is larger than len.
416:
417: private final char charAt(final String str, final int index,
418: final int len) {
419: return (index < len ? str.charAt(index) : '\0');
420: }
421: }
|