Lesson 11 continued: Lists

So what’s all this talk about Comparators and “natural orders?”

To sort the elements of a List, there must be some way of comparing them. For this, the sort() method relies on the availability of a method that does that and returns the result. If you don’t provide a Comparator (and we’re getting to that), you need to promise that the class your elements belong to has such a method–specifically, a method called compareTo() which does the following things:

• Accepts as an argument an object of a class compatible with this object (i.e., it has access to all the fields involved in the comparison).
• Returns a negative number if this object is less than the argument, zero if it’s equal, and a positive number if this object is greater than the argument.

And what guarantees this promise? The Comparable interface. Adding implements Comparable to a class definition and coding the compareTo() method establishes the natural order of objects in that class. (The wrapper classes and String all implement Comparable, so it’s easy to sort them.)

For example:

    public enum Suit {
        CLUBS, DIAMONDS, HEARTS, SPADES
    }

    public enum Rank {
        DEUCE(2), TREY(3), FOUR(4), FIVE(5), SIX(6), SEVEN(7), 
           EIGHT(8), NINE(9), TEN(10), JACK(11), QUEEN(12),
           KING(13), ACE(14);

        private int value;

        private Rank(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }

    private static class Card implements Comparable<Card> {
        Suit suit;
        Rank rank;

        public Card(Suit suit, Rank rank) {
            super();
            this.suit = suit;
            this.rank = rank;
        }
        
        public Rank getRank() {
            return rank;
        }
        
        public Suit getSuit() {
            return suit;
        }

        @Override
        public int compareTo(Card other) {
            return this.getRank().getValue() 
                  - other.getRank().getValue();
        }
    }

Notice how the Comparable interface is generic. In our implementation, we return the difference between the Card’s rank value and that of the Card being passed to compareTo().

Sometimes, however, you want to sort the elements in other than natural order. That’s where a Comparator comes in. Here’s an example of a sort on Suit within Rank, only using a Comparator.

   deck.sort(new Comparator<Card>() {
      @Override
      public int compare(Card card1, Card card2) {
          int diff = card1.getRank().getValue()
                     - card2.getRank().getValue();
          if (diff != 0) {
              return diff;
          }
          return card1.getSuit().ordinal()
                  - card2.getSuit().ordinal();
      }
  });

There are a few interesting things about this code.

• Comparator is a functional interface; as such, you can instantiate it and it will insist on the presence of its one and only abstract method: compare().
• We’re also passing the instance of Comparator as an argument to sort().
• Since it’s created here, we don’t have to give it a name; in fact, you can pass an instance of any class created on the fly in exactly this way.
• The argument consists of the complete definition of the Comparator, including the compare() method with executable code.
• The compare() method needs two arguments, since a Comparator is independent of the class of objects it’s comparing. The compareTo() method of a Comparable belongs to an object, so the only argument it needs is what that object is being compared to.

This way of passing a class created for each call and destroyed afterward isn’t very efficient if it’s executed many times, of course. But you can also create the Comparator as a field in the containing class and pass that to sort().