Java- last part, comparators

Java has two basic tools for doing comparison- the compareTo() method of Comparable objects, and the compare() method of the Comparator class. I will try to explain this with a quick example. Suppose I wanted to sort a collection of strings in alphabetical (ignoring case for the moment) order. I might use a TreeSet to do this:

SortedSet sorter = new TreeSet();
sorter.add("hello");
sorter.add("world");
sorter.add("cat");
sorter.add("dog");

Iterator i = sorter.iterator();
while(i.hasNext())
  System.out.print(i.next()+" ");//prints "cat dog hello world"

In the above example the string constants are automatically cast to String, which implements the compareTo() method (just like c/c++ strcmp). The sorted map assumes its elements are Comparable and uses compareTo() to sort them. Note that this is a unique case where i.next() can be used without a cast, since in java ALL objects implement the toString() method which is automatically called here. Back on topic, what if I wanted to sort the words backwards? One way is to wrap the strings in another class that implements compareTo() backwards like:

class MyString
  {
  String s;
  MyString(String s){this.s=s;}
  public int compareTo(Object other){return -1*(s.compareTo(other));}
  }

This would work, but it is a bit of a mess. We can't extend String directly, since Sun has made it a final class. In any case it will be non obvious what it is you are doing. However, there is a better way that you can use with all of Java's sorted classes (and which you will implement in your own sorted maps later this semester). You can use a comparator:

class ReverseCompare implements Comparator
  {
  public int compare(Object a, Object b)
    {
    return(-1*((Comparable)a).compareTo(b));
    }
  }

SortedSet sorter = new TreeSet(new ReverseCompare());
sorter.add("hello");
sorter.add("world");
sorter.add("cat");
sorter.add("dog");

Iterator i = sorter.iterator();
while(i.hasNext())
  System.out.print(i.next()+" ");//prints "world hello god cat "

Because the TreeSet was given a Comparator in its constructor it will no longer assume its elements are Comparable, and will use the Comparator for sorting instead. Comparators allow you to easily have sets with different types of objects which aren't natively comparable with each other, or to impose your own sorting rules on other people's classes (like String) with ease. Cool stuff. You'll hopefully find this useful for doing your coordinate checking in project 1, as well as implementing a priority queue for your adjacency lists.