001: /*
002: * Copyright 2005 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: /* The contents of this file are subject to the Sun Public License
027: * Version 1.0 (the "License"); you may not use this file except in
028: * compliance with the License. A copy of the License is available at
029: * http://www.sun.com/, and in the file LICENSE.html in the
030: * doc directory.
031: *
032: * The Original Code is HAT. The Initial Developer of the
033: * Original Code is Bill Foote, with contributions from others
034: * at JavaSoft/Sun. Portions created by Bill Foote and others
035: * at Javasoft/Sun are Copyright (C) 1997-2004. All Rights Reserved.
036: *
037: * In addition to the formal license, I ask that you don't
038: * change the history or donations files without permission.
039: */
040:
041: package com.sun.tools.hat.internal.util;
042:
043: import java.util.*;
044:
045: /**
046: * A singleton utility class that sorts an array of objects.
047: * <p>
048: * Use:
049: * <pre>
050: *
051: * Stuff[] arr = ...;
052: * ArraySorter.sort(arr, new Comparer() {
053: * public int compare(Object lhs, Object rhs) {
054: * return ((String) lhs).compareTo((String) rhs);
055: * }
056: * });
057: * </pre>
058: *
059: * @version 1.5, 03/06/98 [jhat @(#)ArraySorter.java 1.8 07/05/05]
060: * @author Bill Foote
061: */
062:
063: public class ArraySorter {
064:
065: /**
066: * Sort the given array, using c for comparison
067: **/
068: static public void sort(Object[] arr, Comparer c) {
069: quickSort(arr, c, 0, arr.length - 1);
070: }
071:
072: /**
073: * Sort an array of strings, using String.compareTo()
074: **/
075: static public void sortArrayOfStrings(Object[] arr) {
076: sort(arr, new Comparer() {
077: public int compare(Object lhs, Object rhs) {
078: return ((String) lhs).compareTo((String) rhs);
079: }
080: });
081: }
082:
083: static private void swap(Object[] arr, int a, int b) {
084: Object tmp = arr[a];
085: arr[a] = arr[b];
086: arr[b] = tmp;
087: }
088:
089: //
090: // Sorts arr between from and to, inclusive. This is a quick, off-the-top-
091: // of-my-head quicksort: I haven't put any thought into optimizing it.
092: // I _did_ put thought into making sure it's safe (it will always
093: // terminate). Worst-case it's O(n^2), but it will usually run in
094: // in O(n log n). It's well-behaved if the list is already sorted,
095: // or nearly so.
096: //
097: static private void quickSort(Object[] arr, Comparer c, int from,
098: int to) {
099: if (to <= from)
100: return;
101: int mid = (from + to) / 2;
102: if (mid != from)
103: swap(arr, mid, from);
104: Object pivot = arr[from]; // Simple-minded, but reasonable
105: int highestBelowPivot = from - 1;
106: int low = from + 1;
107: int high = to;
108: // We now move low and high toward each other, maintaining the
109: // invariants:
110: // arr[i] <= pivot for all i < low
111: // arr[i] > pivot for all i > high
112: // As long as these invariants hold, and every iteration makes
113: // progress, we are safe.
114: while (low <= high) {
115: int cmp = c.compare(arr[low], pivot);
116: if (cmp <= 0) { // arr[low] <= pivot
117: if (cmp < 0) {
118: highestBelowPivot = low;
119: }
120: low++;
121: } else {
122: int c2;
123: for (;;) {
124: // arr[high] > pivot:
125: c2 = c.compare(arr[high], pivot);
126: if (c2 > 0) {
127: high--;
128: if (low > high) {
129: break;
130: }
131: } else {
132: break;
133: }
134: }
135: // At this point, low is never == high, BTW
136: if (low <= high) {
137: swap(arr, low, high);
138: if (c2 < 0) {
139: highestBelowPivot = low;
140: }
141: low++;
142: high--;
143: }
144: }
145: }
146: // At this point, low == high+1
147: // Now we just need to sort from from..highestBelowPivot
148: // and from high+1..to
149: if (highestBelowPivot > from) {
150: // pivot == pivot, so ensure algorithm terminates
151: swap(arr, from, highestBelowPivot);
152: quickSort(arr, c, from, highestBelowPivot - 1);
153: }
154: quickSort(arr, c, high + 1, to);
155: }
156: }
|