Implementing Comparable amounts to defining a compareTo() method that implements a natural ordering for the type.
There are many applications where we want to use different orders for the objects that we are sorting, depending on the situation. The Java Comparator interface allows us to build multiple orders within a single class.
Insertion sorting with a Comparator
public static void sort(Object[] a, Comparator c)
{
int N = a.length;
for (int i = 1; i <; N; i++) for (int j = i; j >; 0 && less(c, a[j], a[j-1]); j--)
exch(a, j, j-1);
}
private static boolean less(Comparator c, Object v, Object w)
{ return c.compare(v, w) <; 0; }
private static void exch(Object[] a, int i, int j)
{ Object t = a[i]; a[i] = a[j]; a[j] = t; }
In typical applications, items have multiple instance variables that might need to serve as sort keys.
The sort does each compare through a callback to the compare() method in Transaction that is specified by the client code. To avoid the cost of making a new Comparator object for each sort, we could use public final instance variables to define the comparators (as Java does for CASE_INSENSITIVE_ORDER).
import java.util.Comparator;
public class Transaction
{
...
private final String who;
private final Date when;
private final double amount;
...
public static class WhoOrder implements Comparator
{
public int compare(Transaction v, Transaction w)
{ return v.who.compareTo(w.when); }
}
public static class WhenOrder implements Comparator
{
public int compare(Transaction v, Transaction w)
{ return v.when.compareTo(w.when); }
}
public static class HowMuchOrder implements Comparator
{
public int compare(Transaction v, Transaction w)
{
if (v.amount < w.amount) return -1; if (v.amount > w.amount) return +1;
return 0;
} }
}
Priority queues with comparators. The same flexibility to use comparators is also useful for priority queues. Extending our standard implementation in Algorithm 2.6 to support comparators involves the following steps:
. Import java.util.Comparator.
. Add to MaxPQ an instance variable comparator and a constructor that takes a
comparator as argument and initializes comparator to that value.
. Add code to less() that checks whether comparator is null (and uses it if it is
not null).
For example, with these changes, you could build different priority queues with Transaction keys, using the time, place, or account number for the ordering. If you remove the Key extends Comparable phrase from MinPQ, you even can support keys with no natural order.
ALGORITHM 2.6 Heap priority queue
public class MaxPQ >
{
private Key[] pq; // heap-ordered complete binary tree
private int N = 0; // in pq[1..N] with pq[0] unused
public MaxPQ(int maxN)
{ pq = (Key[]) new Comparable[maxN+1]; }
public boolean isEmpty()
{ return N == 0; }
public int size()
{ return N; }
public void insert(Key v)
{
pq[++N] = v;
swim(N); }
public Key delMax()
{
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max; }
// Retrieve max key from top.
// Exchange with last item.
// Avoid loitering.
// Restore heap property.
// Missing the implementations of these helper methods.
private boolean less(int i, int j)
private void exch(int i, int j)
private void swim(int k)
private void sink(int k)
}
MaxPQ
Assignments:
1. Write a telephone lookup program, YI_Telephone.java. Read a data set of 1,000 names and telephone numbers from a file that contains the numbers in random order. Handle lookups by name and also reverse lookups by phone number. Use Comparator and a binary search for both lookups.
2. Write a program, YI_StringLength.java to sort an array list of strings by increasing length. Supply a Comparator.
NOTE:
Callbacks are most easily described in terms of the telephone system. A function call is analogous to calling someone on a telephone, asking her a question, getting an answer, and hanging up; adding a callback changes the analogy so that after asking her a question, you also give her your name and number so she can call you back with the answer.
http://stackoverflow.com/questions/8736378/what-is-a-callback-in-java
