/*
 * Copyright (c) 2000 David Flanagan.  All rights reserved.
 * This code is from the book Java Examples in a Nutshell, 2nd Edition.
 * It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
 * You may study, use, and modify it for any non-commercial purpose.
 * You may distribute it non-commercially as long as you retain this notice.
 * For a commercial use license, or to purchase the book (recommended),
 * visit http://www.davidflanagan.com/javaexamples2.
 */
package com.davidflanagan.examples.classes;
// 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 a Comparer
     * object with a compare() method that orders those objects as desired
     **/
    public static interface Comparer {
        /**
	 * Compare objects, 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, 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 considered 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
            }
            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());
            }
        }
	
        /** A a test program that 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;
			ComplexNumber 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, then imaginary:");
            Sorter.sort(a, 0, a.length-1, false, new Sorter.Comparer() {
		    public int compare(Object a, Object b) {
			ComplexNumber i = (ComplexNumber) a;
			ComplexNumber 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 < 0) return -1;
            else return 0;
        }
    }
}