Java Comparator Interface

0-comparators.md

##Java Comparator Interface

####Concept

• Comparables are the basic interface java offers to compare two objects
  • classes that implement Comparable must provide a compareTo method
  • the compareTo method determines what is known as the natural order in which objects of that class are sorted
• comparators enable us to define a compare statement outside of a class
• this allows us to redefine sorting order to be different than the natural order

####Implementation 2 main changes must be made to use the Comparator interface: sorting methods and the comparators themselves.

1. the Comparators themselves
must be coded

• these are classes that implement Comparator

• the classes must contain a public int compare() method

  public static class ByName implements Comparator { public int compare(ClassWeAreTryingToSort a, ClassWeAreTryingToSort b) { /code that determines sorting behaviour/ } }

• the int generally returns

  • -ve number if a < b
  • 0 if a == b
  • +ve number if a > b

2. Sorting methods
must be changed/added to allow comparators to be used

• to work with Comparators, java.util.Comparator should be imported
  • items to be sorted must be changed from Comparable to Object
  • an extra parameter must be added to functions that handled Comparables to take a Comparator

#####Example of such a change in the less method Before

public static boolean less(Comparable a, Comparable b)
{
    return a.compareTo(b) < 0;
}

After

public static boolean less(Object a, Object b, Comparator c)
{
    return c.compare(a, b) < 0;
}

CompObject.java

/*
 * Author: Emerick Bosch
 *
 * This class is used to create and test the comparator interface in conjuction
 * with MergeCompare.java (basic mergesort adapted to take comparators).
 * 
 * Takes a command line integer argument to determine number of elements to
 * generate and sort.
 */

import java.util.Comparator;

public class CompObject {
	// comparator accessor variables
	public static final Comparator<CompObject> BY_NAME = new ByName();
	public static final Comparator<CompObject> BY_NUMBER =  new ByNumber();

	private final String name;
	private final int number;

	public CompObject(String str, int num)
	{
		name = str;
		number = num;
	}

	public void printDetails()
	{
		System.out.println("Name: " + name + "\tNumber: " + number);
	}

	// comparators
	private static class ByName implements Comparator<CompObject>
	{
		public int compare(CompObject a, CompObject b)
		{ return a.name.compareTo(b.name); }
	}

	private static class ByNumber implements Comparator<CompObject>
	{
		public int compare(CompObject a, CompObject b)
		{ return a.number - b.number; }
	}

	// test client
	public static void main(String[] args)
	{
		int N = Integer.parseInt(args[0]);
		CompObject[] array = new CompObject[N];

		/* 
		 * generate N objects each with:
		 *  - random name between 3 and 10 chars long
		 *  - random number between 0 and 30
		 */

		for (int i = 0; i < N; i++) {
			int len = (int)(Math.random() * 7 + 3);
			char[] rname = new char[len];

			// name generation
			for (int j = 0; j < len; j++){
				int ch = (int)(Math.random() * 26 + 97);
				rname[j] = (char) ch;
			}

			String name = new String(rname);
			int num = (int)(Math.random() * 31);

			array[i] = new CompObject(name, num);
		}

		// sort and display
		System.out.println("Sort by name: ");
		MergeCompare.sort(array, CompObject.BY_NAME);
		for (int i = 0; i < array.length; i++) 
			array[i].printDetails(); 
		System.out.println();
			
		System.out.println("Sort by number: ");
		MergeCompare.sort(array, CompObject.BY_NUMBER);
		for (int i = 0; i < array.length; i++) 
			array[i].printDetails(); 
	}
}

MergeCompare.java

/*
 * Author: Emerick Bosch
 *
 * Basic mergesort adapted to take comparators.
 */

import java.util.Comparator;

public class MergeCompare {
	private static Comparable[] aux;
	private static Object[] auxil;
	
	public static void sort(Comparable[] a)
	{
		/* 
		 * aux must be created here. not in the recursion.
		 * we will have many different auxes and use up a lot of memory and time
		 * in array creation.
		 */
		aux = new Comparable[a.length];
		sort(a, aux, 0, a.length - 1);
	}

	public static void sort(Object[] a, Comparator comparator)
	{
		auxil = new Object[a.length];
		sort(a, auxil, 0, a.length - 1, comparator);
	}

	public static void sort(Comparable[] a, Comparable aux[], int lo, int hi)
	{
		if (hi <= lo) return;
		int mid = (lo + hi)/2;
		sort (a, aux, lo, mid);
		sort (a, aux, mid + 1, hi);
		merge (a, aux, lo, mid, hi);
	}

	public static void sort(Object[] a, Object aux[], int lo, int hi, Comparator comparator)
	{
		if (hi <= lo) return;
		int mid = (lo + hi)/2;
		sort (a, aux, lo, mid, comparator);
		sort (a, aux, mid + 1, hi, comparator);
		merge (a, aux, lo, mid, hi, comparator);
	}

	public static void merge(Comparable[] a, Comparable aux[], int lo, int mid, int hi)
	{
		assert isSorted(a, lo, mid);
		assert isSorted(a, mid + 1, hi);

		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo;
		int j = mid + 1;

		for (int k = lo; k <= hi; k++){
			if 	(i > mid)		a[k] = aux[j++];
			else if (j > hi)		a[k] = aux[i++];
			else if (less(aux[j], aux[i]))	a[k] = aux[j++];
			else 				a[k] = aux[i++];
		}

		assert isSorted(a, lo, hi);
	}
		
	public static void merge(Object[] a, Object aux[], int lo, int mid, int hi, 
			Comparator comparator)
	{
		assert isSorted(a, lo, mid, comparator);
		assert isSorted(a, mid + 1, hi, comparator);

		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo;
		int j = mid + 1;

		for (int k = lo; k <= hi; k++) {
			if 	(i > mid)				a[k] = aux[j++];
			else if (j > hi)				a[k] = aux[i++];
			else if (less(comparator, aux[j], aux[i]))	a[k] = aux[j++];
			else 						a[k] = aux[i++];
		}

		assert isSorted(a, lo, hi, comparator);
	}

	// private
	public static void main(String[] args)
	{
		Integer[] array = {0,2,3,5,1,4,6,7};

		for (Integer i : array)
			System.out.print(i + " ");
		System.out.println();

		MergeCompare.sort(array);

		for (Integer i : array)
			System.out.print(i + " ");
	}

	private static boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; }
	
	private static boolean less(Comparator c, Object a, Object b) { 
		return c.compare(a, b) < 0; }

	private static boolean isSorted(Comparable[] a, int lo, int hi)
	{
		for (int i = lo + 1; i < hi; i++)
			if (less(a[i], a[i-1])) return false;
		return true;
	}

	private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator)
	{
		for (int i = lo + 1; i < hi; i++)
			if (less(comparator, a[i], a[i-1])) return false;
		return true;
	}
}