Java’s SortedSet interface and the classes that implement it (like TreeSet) will store a collection of objects that are sortable. In order to make a class sortable so that we can store it in a sorted collection, we have two choices:

1. the sorted class can implement the Comparable interface
2. we can pass a Comparator to the collection’s constructor.

1. Comparable Interface

This is probably the easiest way to make sure we can store objects in a sorting collection. The Comparable interface has a single method that we recognize from classes like String:

int compareTo(Object o)

This method must return an integer: 0 if this.equals(o), a negative int if this is less than o, and a positive int if this is greater than o. Using the Comparable interface defines what we call the “natural ordering” for a class. Here’s an example I wrote for a PTerm, which is a term in a polynomial:

public int compareTo( PTerm other )
{
    return other.power - power;
}

2. Comparator Interface

An interesting alternative is the Comparator interface. By using the Comparator interface we can define different comparators for a class if we need to order objects of a type in different ways. The Comparator interface contains two methods:

1. equals()
2. int compare(T o1, T o2).

Here’s the trick: the class we are comparing does NOT implement Comparator–we create a brand new class that implements it, and pass the implementing class to the collection’s constructor. Here’s an example:

public class TermComparator implements Comparator<PTerm>
{
    public int compare( PTerm term1, PTerm term2 )
    {
        return term2.getPower() - term1.getPower();
    }
}

In this case, we’re sorting the terms in the polynomial by the magnitude of the exponent, but we could have also decided to sort them by the magnitude of the coefficient.

We create the TreeSet like this:

    SortedSet<PTerm> polynomial = new TreeSet<PTerm>( new TermComparator() );

So now, whenever we add a term to the polynomial, the TreeSet will use the TermComparator to decide where it goes.

Don’t forget to override equals() in the PTerm class either:

public boolean equals( Object obj )
{
    if( obj == null )
        return false;
    if( getClass() != obj.getClass() )
        return false;
    PTerm other = (PTerm) obj;
    return power == other.power;
}