Implementing Comparator interface

Suppose we have already decided natural ordering of the object, but for some reason we have to compare 2 objects based on some other fields in it.

Eg. Take the case of employee. We have already written compareTo() method for it. By this we have decided its natural ordering. Now, if we need to sort using other fields of the employee, we’ll have to change the Employee class’s compareTo() method to use those fields. But then we’ll loose this empId based sorting mechanism. This is not a good alternative if we need to sort using different fields at different occasions. But no need to worry; Comparator is there to save us.

By writing a class that implements the java.util.Comparator interface, you can sort Employees using any field as you wish even without touching the Employee class itself; Employee class does not need to implement java.lang.Comparable or java.util.Comparator interface.

Contract of compare method

java.util.Comparator: int compare(Object o1, Objecto2)
This method compares o1 and o2 objects. Returned int value has the following meanings.

1. positive – o1 is greater than o2
2. zero – o1 equals to o2
3. negative – o1 is less than o1

Example

Sorting by name field

Following EmpSortByName class is used to sort Employee instances according to the name field. In this class, inside the compare() method sorting mechanism is implemented. In compare() method we get two Employee instances and we have to return which object is greater.

public class EmpSortByName implements Comparator<Employee>{

    public int compare(Employee o1, Employee o2) {
        return o1.getName().compareTo(o2.getName());
    }
}

Watch out: Here, String class’s compareTo() method is used in comparing the name fields (which are Strings).
Now to test this sorting mechanism, you must use the Collections.sort(List, Comparator) method instead of Collections.sort(List) method. Now change the TestEmployeeSort class as follows. See how the EmpSortByName comparator is used inside sort method.

Using the above Comparator for sorting:

import java.util.*;

public class TestEmployeeSort {
    
    public static void main(String[] args) {
        
        List coll = Util.getEmployees();
        //Collections.sort(coll);
        //use Comparator implementation
        Collections.sort(coll, new EmpSortByName());
        printList(coll);
    }
    
    private static void printList(List<Employee> list) {
        System.out.println("EmpId\tName\tAge");
        for (Employee e: list) {
            System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
        }
    }
}

Sorting by empID field

Even the ordering by empId (previously done using Comparable) can be implemented using Comparator; following class does that.

public class EmpSortByEmpId implements Comparator<Employee>{

    public int compare(Employee o1, Employee o2) {
        return o1.getEmpId() - o2.getEmpId();
    }
}

Comparator vs Comparable interface

The primary use of comparators is to pass them to something that does sorting, either one of the explicit sort methods, or to a data structure than implicitly sorts (eg, TreeSet or TreeMap).

Comparators are not needed for arrays of primitive values, or arrays of collections of objects that have a natural ordering, eg, String, BigInteger, etc.

Implementing compareTo() : Sorting in natural ordering using compareTo()

Defining the criteria for sorting

Suppose we have list of Employees. We have to sort them. By default, you can't sort it, until you define some criteria. Say you define sorting as first name of employee, or you may say sort on the basis of employee id or their salary. So first thing is we have to define some criteria for sorting. This defines "natural ordering" on which sort can be done.

How to define "natural order" in java?

For this, we have to implement Comparable interface, which has compareTo method, which decides how we put natural ordering on the object.

Example:

Employee’s natural ordering would be done according to the employee id. For that, above Employee class must be altered to add the comparing ability as follows.

public class Employee implements Comparable<Employee> {
    private int empId;
    private String name;
    private int age;
    
    /**
     * Compare a given Employee with this object.
     * If employee id of this object is 
     * greater than the received object,
     * then this object is greater than the other.
     */
    public int compareTo(Employee o) {
        return this.empId - o.empId ;
    }
    ….
}

So this compareTo() method does the trick of implementing natural ordering. So if we have 2 Employees, emp1.id – emp2.id is negative, then emp1 falls before emp2 in this ordering. We can say it like this:

emp1.id < emp2.id – emp1 falls before emp2 in natural ordering

emp1.id == emp2.id – emp1 falls with emp2 in natural ordering

emp1.id > emp2.id – emp1 falls after emp2 in natural ordering

 

Sorting the employee list:

 

We’ll write a class to test this natural ordering mechanism. Following class use the Collections.sort(List) method to sort the given list in natural order.

import java.util.*;

public class TestEmployeeSort {
    
    public static void main(String[] args) {     
        List coll = Util.getEmployees();
        Collections.sort(coll); // sort method
        printList(coll);
    }
    
    private static void printList(List<Employee> list) {
        System.out.println("EmpId\tName\tAge");
        for (Employee e: list) {
            System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
        }
    }
}

Similarly to sort on the basis of name : write compareTo like this:

public int compareTo(Employee other) {
    return name.compareTo(o2.getName());
//here compareTo() method of String is called
}

Implementing compareTo() using commons-lang

Here CompareToBuilder is used to implement compareTo();

public int compareTo(Person person) {
    return new CompareToBuilder()
    append(this.firstName, person.firstName)
    append(this.lastName, person.firstName)
    toComparison();
}

Also, there is yet another reflection option:

public int compareTo(Object o) {
    return CompareToBuilder.reflectionCompare(this, o);
}

Difference between Comparable and Comparator Interface

Key Difference between Comparable and Comparator interface

The key difference between comparable and comparator interface is:

Comparable Interface	Comparator Interface
The comparable interface should be used when the current object is to be compared to objects of its type only.	The comparator should be used when some external class is taking your class as a parameter for some comparison operation and it doesn't know how to compare the objects and expects you to give it. In this case you can't give your class as the comparator. It has to be some other class which implements comparator interface and does the comparison.

The above is what we will learn from the following discussion about the two interfaces.

Comparable Interface

Lets start with the comparable interface:
The comparable interface is present in java.lang package. This means that you need not import this interface when you are implementing this interface.
This interface has only one method which has the signature as:

public int compareTo(Object o);

As the name suggests you want this object to be compared to someone else. In Java syntax, the code is:

CompareClass cmp1 = new CompareClass();
CompareClass cmp2 = new CompareClass();
cmp1.compareTo(cmp2);

The best definition of this interface will be the one given in Java API which is reproduced here:
This interface imposes a total ordering on the objects of each class that implements it

Its all upto the implementor to decide how and which kind of objects will he be comparing with the Object for which compareTo method has been invoked. Some facts related to comparable interface are as follows:
1) The compareTo() method should return -ve,zero or +ve integer depending upon whether this object is less than,equal to or greater than the specified object
2) The value returned by compareTo() should be consistent with the value returned by equals() method of the same class. if not so, the class should explicitly state that.
3) Any comparison with null should throw NullPointerException
4)If the object of the classes which implement this interface can be used as keys in the SortedMap or SortedSet.
5)Lists and Arrays that implemet this interface can be sorted using the Collections.sort(List/Array) method without specifying any external comparator.
Example: Lets take the example of String class. Here is a sample code which will clear the compareTo method for you:

public class Test
{
   public static void main(String[] args)
   {
      String str1 = "bar";
      String str2 = "barfoo";

      int compareResult = str1.compareTo(str2);
       if (compareResult < 0){
           System.out.println(str1 + "is less than" + str2); 
       }else if (result == 0){
          System.out.println(str1 +"is equal to" + str2); 
       }else{
          System.out.println(str1 +"is greater than" + str2); 
       }
   } 
}

In this example, we are comparing String objects with other String objects and the comparTo method resides within the String class itself.

Comparator Interface

Now lets see the comparator interface.
The Comparator interface is a part of util package and needs to explicitly imported.
The general contract that is true for comparable is also true for comparator interface which is restated here because of its importance.
The value returned by the compare method of the class implementing the comparator interface should also return the same value with equals() method. This is important because the SortedSet and SortedMap will behave strangely.
There are two methods specified in the comparator interface which have the signature as follows:

int compare(T o1, T o2);
boolean equals(Object obj);

The compare() method should return -ve,zero or +ve integer depending upon whether this object is less than,equal to or greater than the specified object

Example:

import java.util.*;
class Test{

   private int prop1;
   public void setProp1(int prop1){
     this.prop1=prop1;
   }

   public int getProp1(){
     return this.prop1;
   }
}


class TestComparator implements Comparator{

  public int compare(Object obj1, Object obj2){
   int test1 = ( (Test) obj1).getProp1();
   int test2 = ( (Test) obj2).getProp1();

   if( test1 > test2 )
       return 1;
   else if( test1 < test2 )
      return -1; else return 0; 
   } 
} 

So whats the distinguishing part between the comparable and comparator?
Well its the difference in terms of the method signature at code level.
But in terms of design level, there is a big difference and should not be overlooked.
The comparable interface should be used when the current object is to be compared to objects of its type only.
The comparator should be used when some external class is taking your class as a parameter for some comparison operation and it doesn't know how to compare the objects and expects you to give it. In this case you can't give your class as the comparator. It has to be some other class which implements comparator interface and does the comparison. A typical example of this is the Collections.sort(List l, Comparator c) method.

Implementing null-safe compareTo

// primarily by name, secondarily by value; null-safe; case-insensitive
public int compareTo(final Metadata other) {
    int result = nullSafeStringComparator(this.name, other.name);
    if (result != 0) {
        return result;
    }

    return nullSafeStringComparator(this.value, other.value);
}

public static int nullSafeStringComparator(final String one, final String two) {
    if (one == null ^ two == null) {
        return (one == null) ? -1 : 1;
    }

    if (one == null && two == null) {
        return 0;
    }

    return one.compareToIgnoreCase(two);
}

==, .equals(), compareTo(), and compare()

==,equals, compareTo, compare all help in comparing the object in one or other way.

== & != Operator
Compares references, not values. The use of == with object references is generally limited to the following:

• Comparing to see if a reference is null.
• Comparing two enum values. This works because there is only one object for each enum constant.
• You want to know if two references are to the same object

equals() method
Usage : a.equals(b) 
Compares values for equality. Because this method is defined in the Object class, from which all other classes are derived, it's automatically defined for every class. However, it doesn't perform an intelligent comparison for most classes unless the class overrides it. It has been defined in a meaningful way for most Java core classes. If it's not defined for a (user) class, it behaves the same as ==.
It turns out that defining equals() isn't trivial; in fact it's moderately hard to get it right, especially in the case of subclasses. The best treatment of the issues is in Horstmann's Core Java Vol 1. See equals() method here.

Also to see == vs equals() , refer here.

compareTo() method
a.compareTo(b) is present in Comparable interface. Compares values and returns an int which tells if the values compare less than, equal, or greater than. If your class objects have a natural order, implement the Comparable<T> interface and define this method. All Java classes that have a natural ordering implement this (String, Double, BigInteger, ...).
For more on Comparable interface, refer here.

compare(a,b) method
Usage  : compare(a, b) 
is implemented using Comparator interface. Compares values of two objects. This is implemented as part of the Comparator<T> interface, and the typical use is to define one or more small utility classes that implement this, to pass to methods such as sort() or for use by sorting data structures such as TreeMap and TreeSet. You might want to create a Comparator object for the following.

• Multiple comparisons. To provide several different ways to sort something. For example, you might want to sort a Person class by name, ID, age, height, ... You would define a Comparator for each of these to pass to the sort() method.
  
• System class. To provide comparison methods for classes that you have no control over. For example, you could define a Comparator for Strings that compared them by length.
  
• Strategy pattern. To implement a strategy pattern, which is a situation where you want to represent an algorithm as an object that you can pass as a parameter, save in a data structure, etc.

If your class objects have one natural sorting order, you may not need this.
For more on Comparator interface refer here.

Implementing compareTo (why we need it?)

The compareTo method is the sole member of the Comparable interface, and is not a member of Object. However, it is quite similar in nature to equals and hashCode. It provides a means of fully ordering objects.
Implementing Comparable allows

• calling Collections.sort and Collections.binarySearch
• calling Arrays.sort and Arrays.binarySearch
• using objects as keys in a TreeMap
• using objects as elements in a TreeSet

The compareTo method needs to satisfy the following conditions. These conditions have the goal of allowing objects to be fully sorted, much like the sorting of a database result set on all fields.

• anticommutation :  x.compareTo(y) is the opposite sign of y.compareTo(x)
• exception symmetry : x.compareTo(y) throws exactly the same exceptions as y.compareTo(x)
• transitivity :  if x.compareTo(y)>0 and y.compareTo(z)>0, then x.compareTo(z)>0  (and same for less than)
•  if x.compareTo(y)==0, then x.compareTo(z) has the same sign as y.compareTo(z)
• consistency with equals is highly recommended, but not required : x.compareTo(y)==0, if and only if x.equals(y) ; consistency with equals is required for ensuring sorted collections (such as TreeSet) are well-behaved.

One can greatly increase the performance of compareTo by comparing first on items which are most likely to differ. When a class extends a concrete Comparable class and adds a significant field, a correct implementation of compareTo cannot be constructed. The only alternative is to use composition instead of inheritance. (A similar situation holds true for equals. See Effective Java for more information.)

Compare the various types of fields as follows :

• numeric primitive : use < and >. There is an exception to this rule: float and double primitives should be compared using Float.compare(float, float) and Double.compare(double, double). This avoids problems associated with special border values.
• boolean primitive :  use tests of the form (x && !y)
• Object : use compareTo. (Note that possibly-null fields present a problem : while x.equals(null) returns false, x.compareTo(null) will always throw a NullPointerException)
• type-safe enumeration : use compareTo, like any Object
• collection or array : Comparable does not seem to be intended for these kinds of fields. For example, List, Map and Set do not implement Comparable. As well, some collections have no definite order of iteration, so doing an element-by-element comparison cannot be meaningful in those cases.

If the task is to perform a sort of items which are stored in a relational database, then it is usually much preferred to let the database perform the sort using the ORDER BY clause, rather than in code. An alternative to implementing Comparable is passing Comparator objects as parameters. Be aware that if a Comparator compares only one of several significant fields, then the Comparator is very likely not synchronized with equals.
All primitive wrapper classes implement Comparable. Note that Boolean did not implement Comparable until version 1.5, however.

Example:

import java.util.*;
import java.io.*;

public final class Account implements Comparable<Account> {
  
//Constructor
  enum AccountType {CASH, MARGIN, RRSP};

public Account (
      String aFirstName,
      String aLastName,
      int aAccountNumber,
      int aBalance,
      boolean aIsNewAccount,
      AccountType aAccountType
  ) {
      //..parameter validations elided      fFirstName = aFirstName;
      fLastName = aLastName;
      fAccountNumber = aAccountNumber;
      fBalance = aBalance;
      fIsNewAccount = aIsNewAccount;
      fAccountType = aAccountType;
   }

  /**
  * @param aThat is a non-null Account.
  *
  * @throws NullPointerException if aThat is null.
  */
  public int compareTo( Account aThat ) {
    final int BEFORE = -1;
    final int EQUAL = 0;
    final int AFTER = 1;

    //this optimization is usually worthwhile, and can    
 

//always be added    
if ( this == aThat ) return EQUAL;

    //primitive numbers follow this form    
if (this.fAccountNumber < aThat.fAccountNumber) return BEFORE;
    if (this.fAccountNumber > aThat.fAccountNumber) return AFTER;

    //booleans follow this form    if (!this.fIsNewAccount && aThat.fIsNewAccount) return BEFORE;
    if (this.fIsNewAccount && !aThat.fIsNewAccount) return AFTER;

    //objects, including type-safe enums, follow this form    //note that null objects will throw an exception here    int comparison = this.fAccountType.compareTo(aThat.fAccountType);
    if ( comparison != EQUAL ) return comparison;

    comparison = this.fLastName.compareTo(aThat.fLastName);
    if ( comparison != EQUAL ) return comparison;

    comparison = this.fFirstName.compareTo(aThat.fFirstName);
    if ( comparison != EQUAL ) return comparison;

    if (this.fBalance < aThat.fBalance) return BEFORE;
    if (this.fBalance > aThat.fBalance) return AFTER;

    //all comparisons have yielded equality    //verify that compareTo is consistent with equals (optional)    assert this.equals(aThat) : "compareTo inconsistent with equals.";

    return EQUAL;
  }

   /**
   * Define equality of state.
   */
   @Override public boolean equals( Object aThat ) {
     if ( this == aThat ) return true;
     if ( !(aThat instanceof Account) ) return false;

     Account that = (Account)aThat;
     return
       ( this.fAccountNumber == that.fAccountNumber ) &&
       ( this.fAccountType == that.fAccountType ) &&
       ( this.fBalance == that.fBalance ) &&
       ( this.fIsNewAccount == that.fIsNewAccount ) &&
       ( this.fFirstName.equals(that.fFirstName) ) &&
       ( this.fLastName.equals(that.fLastName) );
   }

   /**
   * A class that overrides equals must also override hashCode.
   */
   @Override public int hashCode() {
     int result = HashCodeUtil.SEED;
     result = HashCodeUtil.hash( result, fAccountNumber );
     result = HashCodeUtil.hash( result, fAccountType );
     result = HashCodeUtil.hash( result, fBalance );
     result = HashCodeUtil.hash( result, fIsNewAccount );
     result = HashCodeUtil.hash( result, fFirstName );
     result = HashCodeUtil.hash( result, fLastName );
     return result;
   }

   ////  PRIVATE  ///////
   private String fFirstName; //non-null   private String fLastName;  //non-null   private int fAccountNumber;
   private int fBalance;
   private boolean fIsNewAccount;

   /**
   * Type of the account, expressed as a type-safe enumeration (non-null).
   */
   private AccountType fAccountType;

   /**
   * Exercise compareTo.
   */
   public static void main (String[] aArguments) {
     //Note the difference in behaviour in equals and compareTo, for nulls:     String text = "blah";
     Integer number = new Integer(10);
     //x.equals(null) always returns false:     System.out.println("false: " + text.equals(null));
     System.out.println("false: " + number.equals(null) );
     //x.compareTo(null) always throws NullPointerException:     //System.out.println( text.compareTo(null) );     //System.out.println( number.compareTo(null) );
     Account flaubert = new Account(
      "Gustave", "Flaubert", 1003, 0,true, AccountType.MARGIN
     );

     //all of these other versions of "flaubert" differ from the     //original in only one field     Account flaubert2 = new Account(
       "Guy", "Flaubert", 1003, 0, true, AccountType.MARGIN
     );
     Account flaubert3 = new Account(
       "Gustave", "de Maupassant", 1003, 0, true, AccountType.MARGIN
     );
     Account flaubert4 = new Account(
       "Gustave", "Flaubert", 2004, 0, true, AccountType.MARGIN
     );
     Account flaubert5 = new Account(
       "Gustave", "Flaubert", 1003, 1, true, AccountType.MARGIN
     );
     Account flaubert6 = new Account(
       "Gustave", "Flaubert", 1003, 0, false, AccountType.MARGIN
     );
     Account flaubert7 = new Account(
       "Gustave", "Flaubert", 1003, 0, true, AccountType.CASH
     );

     System.out.println( "0: " +  flaubert.compareTo(flaubert) );
     System.out.println( "first name +: " +  flaubert2.compareTo(flaubert) );
     //Note capital letters precede small letters     System.out.println( "last name +: " +  flaubert3.compareTo(flaubert) );
     System.out.println( "acct number +: " +  flaubert4.compareTo(flaubert) );
     System.out.println( "balance +: " +  flaubert5.compareTo(flaubert) );
     System.out.println( "is new -: " +  flaubert6.compareTo(flaubert) );
     System.out.println( "account type -: " +  flaubert7.compareTo(flaubert) );
   }
} 

A sample run of this class gives:
>java -cp . Account
false: false
false: false
0: 0
first name +: 6
last name +: 30
acct number +: 1
balance +: 1
is new -: -1
account type -: -1

String comparisons using ==, equals () or compartTo()

Using ==
To compare Strings for equality, don't use ==. The == operator checks to see if two objects are exactly the same object. Two strings may be different objects, but have the same value (have exactly the same characters in them).
Using equals()
Use the .equals() method to compare strings for equality. Similarly, use the .compareTo() method to test for unequal comparisons. For example,
String s1 = "True";
String s2 = "True";
s1 == s2 == true //compiler uses one instance for string literals , so works fine as 2 strings are
same taken from string pool.
String s3 = new String("False");
String s4 = new String("False");
s3 == s4 == false //two forced instances
String s5 = "True";
String s6 = "Tr" + "ue";
s5 == s6 == true //compiler evaluates and uses same instance
String s7 = "False";
String sx = "F";
String s8 = sx + "alse";
s7 == s8 == false //compiler won't evaluate where a second reference is involved
These values are all "equal". But == will return true or false based on _how_ the values were set.
Stick to .equals(), and enjoy the remaining features of autoboxing.
compareTo() and comparison operators

if (s > t)    // ILLEGAL
    if (s.compareTo(t) > 0) // CORRECT>

I guess I don't find it inconsistent, or at least not as inconsistent as the alternative would be. In each case the result is true or false based on whether the reference is pointing to the same object instance or not. When dealing with objects, == does not compare values. Doing so _would_ be inconsistent.

Object Ordering : Comparable Interface

A List l may be sorted as follows:

Collections.sort(l);

If the list consists of String elements, it will be sorted into lexicographic (alphabetical) order. If it consists of Date elements, it will be sorted into chronological order. How does Java know how to do this? It's magic! Well, no. Actually String and Date both implement the Comparable interface. The Comparable interfaces provides a natural ordering for a class, which allows objects of that class to be sorted automatically. The following table summarizes the JDK classes that implement Comparable:

Class	Natural Ordering
Byte	signed numerical
Character	unsigned numerical
Long	signed numerical
Integer	signed numerical
Short	signed numerical
Double	signed numerical
Float	signed numerical
BigInteger	signed numerical
BigDecimal	signed numerical
File	system-dependent lexicographic on pathname.
String	lexicographic
Date	chronological
CollationKey	locale-specific lexicographic

If you try to sort a list whose elements do not implement Comparable, Collections.sort(list) will throw a ClassCastException . Similarly, if you try to sort a list whose elements cannot be compared to one another, Collections.sort will throw a ClassCastException. Elements that can be compared to one another are called mutually comparable. While it is possible to have elements of different types be mutually comparable, none of the JDK types listed above permit inter-class comparison.
This is all you really need to know about the the Comparable interface if you just want to sort lists of comparable elements, or create sorted collections of them. The next section will be of interest to you if you want to implement your own Comparable type.

Writing Your Own Comparable Types

The Comparable interface consists of a single method:

public interface Comparable {
    public int compareTo(Object o);
}

The compareTo method compares the receiving object with the specified object, and returns a negative integer, zero, or a positive integer as the receiving object is less than, equal to, or greater than the specified Object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException. Here's a class representing a person's name that implements Comparable:

import java.util.*;

public class Name implements Comparable {
    private String  firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName==null || lastName==null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String firstName()    {return firstName;}
    public String lastName()     {return lastName;}

    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name)o;
        return n.firstName.equals(firstName) &&
               n.lastName.equals(lastName);
    }

    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }

    public String toString() {return firstName + " " + lastName;}

    public int compareTo(Object o) {
        Name n = (Name)o;
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp!=0 ? lastCmp :
                firstName.compareTo(n.firstName));
    }
}

To keep the example short, the class is somewhat limited: It doesn't support middle names, it demands both a first and a last name, and it is not internationalized in any way. Nonetheless, it illustrates several important points:

• Name objects are immutable. All other things being equal, immutable types are the way to go, especially for objects that will be used as elements in Sets, or keys in Maps. These collections will break if you modify their elements or keys while they're in the collection.
• The constructor checks its arguments for null. This ensures that all Name objects are well-formed, so that none of the other methods will ever throw a NullPointerException.
• The hashCode method is redefined. This is essential for any class that redefines the equals method. It is required by the general contract for Object.equals. (Equal objects must have equal hash codes.)
• The equals method returns false if the specified object is null, or of an inappropriate type. The compareTo method throws a runtime exception under these circumstances. Both of these behaviors are required by the general contracts of the respective methods.
• The toString method has been redefined to print the Name in human-readable form. This is always a good idea, especially for objects that are going to get put into collections. The various collection types' toString methods depend on the toString methods of their elements, keys and values.

Since this section is about element ordering, let's talk a bit more about Name's compareTo method. It implements the standard name-ordering algorithm, where last names take precedence over first names. This is exactly what you want in a natural ordering. It would be very confusing if the natural ordering were unnatural! Take a look at how compareTo is implemented, because it's quite typical. First, you cast the Object argument to the appropriate type. This throws the appropriate exception (ClassCastException) if the arguments type is inappropriate. Then you compare the most significant part of the object (in this case, the last name). Often, you can just use the natural ordering of the part's type. In this case, the part is a String, and the natural (lexicographic) ordering is exactly what's called for. If the comparison results in anything other than zero (which represents equality), you're done: you just return the result. If the most significant parts are equal, you go on to compare the next-most-significant parts. In this case, there are only two parts (first name and last name). If there were more parts, you'd proceed in the obvious fashion, comparing parts until you found two that weren't equal (or you were comparing the least-significant parts), at which point you'd return the result of the comparison.
Just to show that it all works, here's a little program that builds a list of Name objects and sorts them:

import java.util.*;

class NameSort {
    public static void main(String args[]) {
        Name n[] = {
            new Name("John", "Lennon"),
            new Name("Karl", "Marx"),
            new Name("Groucho", "Marx"),
            new Name("Oscar", "Grouch")
        };
        List l = Arrays.asList(n);
        Collections.sort(l);
        System.out.println(l);
    }
}

If you run this program, here's what it prints:

[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]

There are four restrictions on the behavior of the compareTo method, which we won't go over now because they're fairly technical and boring and are better left in the API documentation. It's really important that all classes that implement Comparable obey these restrictions, so read the documentation for Comparable if you're writing a class that implements it. Attempting to sort a list of objects that violate these restrictions has undefined behavior. Technically speaking, these restrictions ensure that the natural ordering is a partial order on the objects of a class that implements it; this is necessary to ensure that sorting is well-defined.

Comparators

OK, so now you know about natural ordering. But what if you want to sort some objects in some order other than their natural order? Or what if you want to sort some objects that don't implement Comparable? To do either of these things, you'll need to provide a Comparator . A Comparator is simply an object that encapsulates an ordering. Like the Comparable interface, the Comparator interface consists of a single method:

public interface Comparator {
    int compare(Object o1, Object o2);
}

The compare method compares its two arguments, returning a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator, the compare method throws a ClassCastException. Much of what was said about Comparable in the previous section applies to Comparator as well. Writing a compare method is nearly identical to writing a compareTo method, except that the former gets both objects passed in as arguments. The compare method has to obey the same four "technical restrictions" as Comparable's compareTo method, for the same reason: a Comparator must induce a partial order on the objects it compares.
Suppose you have a class called EmployeeRecord:

public class EmployeeRecord implements Comparable {
    public Name name();
    public int employeeNumber();
    public Date hireDate();
             ...
}

Let's assume that the natural ordering of EmployeeRecord objects is Name-ordering (as defined in the previous example) on employee name. Unfortunately the boss has asked us for a list of employees in order of seniority. This means we actually have to do some work, but not much. Here's a program that will produce the required list:

import java.util.*;

class EmpSort {
    static final Comparator SENIORITY_ORDER = new Comparator() {
        public int compare(Object o1, Object o2) {
            EmployeeRecord r1 = (EmployeeRecord) o1;
            EmployeeRecord r2 = (EmployeeRecord) o2;
            return r2.hireDate().compareTo(r1.hireDate());
        }
    };

    static final Collection employees = ... ;  // Employee Database

    public static void main(String args[]) {
        List emp = new ArrayList(employees);
        Collections.sort(emp, SENIORITY_ORDER);
        System.out.println(emp);
    }
}

The Comparator in the above program is reasonably straightforward. It casts its arguments to EmployeeRecord, and relies on the natural ordering of Date applied to the hireDate() accessor method. Note that the Comparator passes the hire-date of its second argument to its first, rather than vice-versa. This is because the employee who was hired most recently is least senior: sorting in order of hire-date would put the list in reverse seniority-order. Another way to achieve the same effect would be to maintain the argument order but negate the result of the comparison:

return -r1.hireDate().compareTo(r2.hireDate());

The two techniques are equally preferable. Use whichever looks best to you. The Comparator in the above program works fine for sorting a List, but it does have one deficiency: it cannot be used to order a sorted collection (such as TreeSet) because it generates a strictly partial ordering. What this means is that this comparator equates unequal objects. In particular, any two employees who were hired on the same date will compare as equal. When you're sorting a List, this doesn't matter, but when you're using the Comparator to order a sorted collection, it's fatal. If you insert multiple employees who were hired on the same date into a TreeSet with this Comparator, only the first one will be added to the set. The second will be seen as a duplicate element, and ignored.
To fix this problem, all you have to do is tweak the Comparator so that it produces a total ordering. In other words, tweak it so that the only elements that are seen as equal when using compare are those that are also seen as equal when compared using equals. The way to do this is to do a two-part comparison (like we did for Name) where the first part is the one that we're actually interested in (in this case, the hire-date), and the second part is attribute that uniquely identifies the object. In this case, the employee number is the obvious attribute to use as the second part. Here's the Comparator that results:

static final Comparator SENIORITY_ORDER = new Comparator() {
    public int compare(Object o1, Object o2) {
        EmployeeRecord r1 = (EmployeeRecord) o1;
        EmployeeRecord r2 = (EmployeeRecord) o2;
        int dateCmp = r2.hireDate().compareTo(r1.hireDate());
        if (dateCmp != 0)
            return dateCmp;
        return (r1.employeeNumber() < r2.employeeNumber() ? -1 :
                (r1.employeeNumber() == r2.employeeNumber() ? 0 : 1));
    }
};

One last note. You might be tempted to replace the final return statement in the Comparator with the simpler:

return r1.employeeNumber() - r2.employeeNumber();

Don't do it unless you're absolutely sure that no one will ever have a negative employee number! This trick does not work in general, as the signed integer type is not big enough to represent the difference of two arbitrary signed integers. If i is a large positive integer and j is a large negative integer, i-j will overflow and return a negative integer. The resulting Comparator violates one of the four technical restrictions that we keep talking about (transitivity), and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.

Comparators

The key-value (Map.Entry) pairs in a HashMap are not sorted, but users would certainly like to see them sorted, either alphabetically by word, or by frequency.
Because sorts are usually based on comparison of two values at a time, all that is needed is a way to compare two values. That's what a Comparator does -- it defines a compare() method that tells how two values compare.

import java.util.*;

/////////////////////////////////////////////////////// class ComparatorAlphabetic
/** Order words alphabetically. */
class ComparatorAlphabetic implements Comparator> {
    public int compare(Map.Entry entry1
                     , Map.Entry entry2) {
        return entry1.getKey().compareTo(entry2.getKey());
    }
} 

import java.util.*;

////////////////////////////////////////////////////// class ComparatorFrequency
/** Order words from least to most frequent, put ties in alphabetical order. */
class ComparatorFrequency implements Comparator> {
    public int compare(Map.Entry obj1
                     , Map.Entry obj2) {
        int result;
        int count1 = obj1.getValue().value;
        int count2 = obj2.getValue().value;
        if (count1 < count2) {
            result = -1;
            
        } else if (count1 > count2) {
            result = 1;
            
        } else { 
            //... If counts are equal, compare keys alphabetically.
            result = obj1.getKey().compareTo(obj2.getKey());
        }
        return result;
    }
}