// This example is from _Java Examples in a Nutshell_. (http://www.oreilly.com)
// Copyright (c) 1997 by David Flanagan
// This example is provided WITHOUT ANY WARRANTY either expressed or implied.
// You may study, use, modify, and distribute it for non-commercial purposes.
// For any commercial use, see http://www.davidflanagan.com/javaexamples
// These are some classes we need for internationalized string sorting
import java.text.Collator;
import java.text.CollationKey;
import java.util.Locale;
/**
* This class defines a bunch of static methods for efficiently sorting
* arrays of Strings or other objects. It also defines two interfaces that
* provide two different ways of comparing objects to be sorted.
**/
public class Sorter {
/**
* This interface defines the compare() method used to compare two objects.
* To sort objects of a given type, you must provide an appropriate Comparer
* object with a compare() method that orders those objects as desired
**/
public static interface Comparer {
/**
* Compare objects and return a value that indicates their relative order:
* if (a > b) return > 0;
* if (a == b) return 0;
* if (a < b) return < 0.
**/
public int compare(Object a, Object b);
}
/**
* This is an alternative interface that can be used to order objects. If a
* class implements this Comparable interface, then any two instances of that
* class can be directly compared by invoking the compareTo() method.
**/
public static interface Comparable {
/**
* Compare objects and return a value that indicates their relative order:
* if (this > other) return > 0
* if (this == other) return 0
* if (this < other) return < 0
**/
public int compareTo(Object other);
}
/**
* This is an internal Comparer object (created with an anonymous class)
* that compares two ASCII strings.
* It is used in the sortAscii methods below.
**/
private static Comparer ascii_comparer = new Comparer() {
public int compare(Object a, Object b) {
return ((String)a).compareTo((String)b);
}
};
/**
* This is another internal Comparer object. It is used to compare two
* Comparable objects. It is used by the sort() methods below that take
* Comparable objects as arguments instead of arbitrary objects
*/
private static Comparer comparable_comparer = new Comparer() {
public int compare(Object a, Object b) {
return ((Comparable)a).compareTo(b);
}
};
/** Sort an array of ASCII strings into ascending order */
public static void sortAscii(String[] a) {
// Note use of the ascii_comparer object
sort(a, null, 0, a.length-1, true, ascii_comparer);
}
/**
* Sort a portion of an array of ASCII strings into ascending or descending
* order, depending on the argument up
**/
public static void sortAscii(String[] a, int from, int to, boolean up) {
// Note use of the ascii_comparer object
sort(a, null, from, to, up, ascii_comparer);
}
/** Sort an array of ASCII strings into ascending order, ignoring case */
public static void sortAsciiIgnoreCase(String[] a) {
sortAsciiIgnoreCase(a, 0, a.length-1, true);
}
/**
* Sort an portion of an array of ASCII strings, ignoring case. Sort into
* ascending order if up is true, otherwise sort into descending order.
**/
public static void sortAsciiIgnoreCase(String[] a, int from, int to,
boolean up) {
if ((a == null) || (a.length < 2)) return;
// Create a secondary array of strings that contains lowercase versions
// of all the specified strings.
String b[] = new String[a.length];
for(int i = 0; i < a.length; i++) b[i] = a[i].toLowerCase();
// Sort that secondary array, and rearrange the original array
// in exactly the same way, resulting in a case-insensitive sort.
// Note the use of the ascii_comparer object
sort(b, a, from, to, up, ascii_comparer);
}
/**
* Sort an array of strings into ascending order, using the correct
* collation order for the default locale
**/
public static void sort(String[] a) {
sort(a, 0, a.length-1, true, false, null);
}
/**
* Sort a portion of an array of strings, using the collation order of
* the default locale. If up is true, sort ascending, otherwise, sort
* descending. If ignorecase is true, ignore the capitalization of letters
**/
public static void sort(String[] a, int from, int to,
boolean up, boolean ignorecase) {
sort(a, from, to, up, ignorecase, null);
}
/**
* Sort a portion of an array of strings, using the collation order of
* the specified locale. If up is true, sort ascending, otherwise, sort
* descending. If ignorecase is true, ignore the capitalization of letters
**/
public static void sort(String[] a, int from, int to,
boolean up, boolean ignorecase,
Locale locale) {
// Don't sort if we don't have to
if ((a == null) || (a.length < 2)) return;
// The java.text.Collator object does internationalized string compares
// Create one for the specified, or the default locale.
Collator c;
if (locale == null) c = Collator.getInstance();
else c = Collator.getInstance(locale);
// Specify whether or not case should be taken into account in the sort.
// Note: this option does not seem to work correctly in JDK 1.1.1
// using the default American English locale.
if (ignorecase) c.setStrength(Collator.SECONDARY);
// Use the Collator object to create an array of CollationKey objects that
// correspond to each of the strings.
// Comparing CollationKeys is much quicker than comparing Strings
CollationKey[] b = new CollationKey[a.length];
for(int i = 0; i < a.length; i++) b[i] = c.getCollationKey(a[i]);
// Now define a Comparer object to compare collation keys, using an
// anonymous class.
Comparer comp = new Comparer() {
public int compare(Object a, Object b) {
return ((CollationKey)a).compareTo((CollationKey)b);
}
};
// Finally, sort the array of CollationKey objects, rearranging the
// original array of strings in exactly the same way.
sort(b, a, from, to, up, comp);
}
/** Sort an array of Comparable objects into ascending order */
public static void sort(Comparable[] a) {
sort(a, null, 0, a.length-1, true);
}
/**
* Sort a portion of an array of Comparable objects. If up is true,
* sort into ascending order, otherwise sort into descending order.
**/
public static void sort(Comparable[] a, int from, int to, boolean up) {
sort(a, null, from, to, up, comparable_comparer);
}
/**
* Sort a portion of array a of Comparable objects. If up is true,
* sort into ascending order, otherwise sort into descending order.
* Re-arrange the array b in exactly the same way as a.
**/
public static void sort(Comparable[] a, Object[] b,
int from, int to, boolean up) {
sort(a, b, from, to, up, comparable_comparer);
}
/**
* Sort an array of arbitrary objects into ascending order, using the
* comparison defined by the Comparer object c
**/
public static void sort(Object[] a, Comparer c) {
sort(a, null, 0, a.length-1, true, c);
}
/**
* Sort a portion of an array of objects, using the comparison defined by
* the Comparer object c. If up is true, sort into ascending order,
* otherwise sort into descending order.
**/
public static void sort(Object[] a, int from,int to, boolean up, Comparer c){
sort(a, null, from, to, up, c);
}
/**
* This is the main sort() routine. It performs a quicksort on the elements
* of array a between the element from and the element to. The up argument
* specifies whether the elements should be sorted into ascending (true) or
* descending (false) order. The Comparer argument c is used to perform
* comparisons between elements of the array. The elements of the array b
* are reordered in exactly the same way as the elements of array a are.
**/
public static void sort(Object[] a, Object[] b,
int from, int to,
boolean up, Comparer c)
{
// If there is nothing to sort, return
if ((a == null) || (a.length < 2)) return;
// This is the basic quicksort algorithm, stripped of frills that can make
// it faster but even more confusing than it already is. You should
// understand what the code does, but don't have to understand just
// why it is guaranteed to sort the array...
// Note the use of the compare() method of the Comparer object.
int i = from, j = to;
Object center = a[(from + to) / 2];
do {
if (up) { // an ascending sort
while((i < to) && (c.compare(center, a[i]) > 0)) i++;
while((j > from) && (c.compare(center, a[j]) < 0)) j--;
} else { // a descending sort
while((i < to) && (c.compare(center, a[i]) < 0)) i++;
while((j > from) && (c.compare(center, a[j]) > 0)) j--;
}
if (i < j) {
Object tmp = a[i]; a[i] = a[j]; a[j] = tmp; // swap elements
if (b != null) { tmp = b[i]; b[i] = b[j]; b[j] = tmp; }// swap b, too
}
if (i <= j) { i++; j--; }
} while(i <= j);
if (from < j) sort(a, b, from, j, up, c); // recursively sort the rest
if (i < to) sort(a, b, i, to, up, c);
}
/**
* This nested class defines a test program that demonstrates several
* ways to use the Sorter class to sort ComplexNumber objects
**/
public static class Test {
/**
* This subclass of ComplexNumber implements the Comparable interface
* and defines a compareTo() method for comparing complex numbers.
* It compares numbers based on their magnitude. I.e. on their distance
* from the origin.
**/
static class SortableComplexNumber extends ComplexNumber
implements Sorter.Comparable {
public SortableComplexNumber(double x, double y) { super(x, y); }
public int compareTo(Object other) {
return sign(this.magnitude()-((ComplexNumber)other).magnitude());
}
}
/** This is the test program. It sorts complex numbers in various ways. */
public static void main(String[] args) {
// Define an array of SortableComplexNumber objects. Initialize it
// to contain random complex numbers.
SortableComplexNumber[] a = new SortableComplexNumber[5];
for(int i = 0; i < a.length; i++)
a[i] = new SortableComplexNumber(Math.random()*10, Math.random()*10);
// Now sort it using the SortableComplexNumber compareTo() method, which
// sorts by magnitude, and print the results out.
System.out.println("Sorted by magnitude:");
Sorter.sort(a);
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
// Sort the complex numbers again, using a Comparer object that
// compares them based on the sum of their real and imaginary parts
System.out.println("Sorted by sum of real and imaginary parts:");
Sorter.sort(a, new Sorter.Comparer() {
public int compare(Object a, Object b) {
ComplexNumber i = (ComplexNumber)a, j = (ComplexNumber)b;
return sign((i.real() + i.imaginary()) -
(j.real() + j.imaginary()));
}
});
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
// Sort them again using a Comparer object that compares their real
// parts, and then their imaginary parts
System.out.println("Sorted descending by real part, then imaginary:");
Sorter.sort(a, 0, a.length-1, false, new Sorter.Comparer() {
public int compare(Object a, Object b) {
ComplexNumber i = (ComplexNumber) a, j = (ComplexNumber) b;
double result = i.real() - j.real();
if (result == 0) result = i.imaginary() - j.imaginary();
return sign(result);
}
});
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
}
/** This is a convenience routine used by comparison routines */
public static int sign(double x) {
if (x > 0) return 1;
else if (x |
