A collection implementation stores its elements in some order (arrangement). This order may be unsorted, or it may be sorted according to some criterion (such as alphabetical, numerical, or chronological).
A sorted collection implementation defaults to storing its elements according to their natural ordering. For example, the natural ordering of String objects is lexicographic or dictionary (also known as alphabetical) order.
A collection cannot rely on equals() to dictate natural ordering because this method can only determine if two elements are equivalent. Instead, element classes must implement the java.lang.Comparable<T> interface and its int compareTo(T o) method.
NOTE: According to Comparable's JDK documentation, this interface is considered to be part of the collections framework, even though it is a member of the java.lang package.
A sorted collection uses compareTo() to determine the natural ordering of this method's element argument o in a collection. compareTo() compares argument o with the current element (which is the element on which compareTo() was called) and does the following:
■ It returns a negative value when the current element should precede o.
■ It returns a zero value when the current element and o are the same.
■ It returns a positive value when the current element should succeed o.
When you need to implement Comparable's compareTo() method, there are some rules that you must follow. These rules, listed next, are similar to those shown in Chapter 3 for implementing the equals() method:
■ compareTo() must be reflexive: For any nonnull reference value x, x.compareTo(x) must return 0.
■ compareTo() must be symmetric: For any nonnull reference values x and y, x.compareTo(y) == -y.compareTo(x) must hold.
■ compareTo() must be transitive: For any nonnull reference values x, y, and z, if x.compareTo(y) > 0 is true, and ify.compareTo(z) > 0 is true, then x.compareTo(z) > 0 must also be true.
Also, compareTo() should throw NullPointerException when the null reference is passed to this method. However, you do not need to check for null because this method throws NullPointerException when it attempts to access a null reference's members.
NOTE: Prior to Java version 5 and its introduction of generics, compareTo()'s argument was of type Object and had to be cast to the appropriate type before the comparison could be made. The cast operator would throw a java.lang.ClassCastException instance when the argument's type was not compatible with the cast.
You might occasionally need to store in a collection objects that are sorted in some order that differs from their natural ordering. In this case, you would supply a comparator to provide that ordering.
A comparator is an object whose class implements the Comparator interface. This interface, whose generic type is Comparator<T>, provides the following pair of methods:
int compare(T o1, T o2) compares both arguments for order. This method returns 0 when o1 equals o2, a negative value when o1 is less than o2, and a positive value when o1 is greater than o2.
boolean equals(Object o) returns true when o "equals" this Comparator in that o is also a Comparator and imposes the same ordering. Otherwise, this method returns false.
NOTE: Comparator declares equals() because this interface places an extra condition on this method's contract. Additionally, this method can return true only if the specified object is also a comparator and it imposes the same ordering as this comparator. You do not have to override equals(), but doing so may improve performance by allowing programs to determine that two distinct comparators impose the same order.
Chapter 5 provided an example that illustrated implementing Comparable, and you will discover an additional example later in this chapter. Also, this chapter will present examples of implementing Comparator.
Was this article helpful?