There have been many changes to the core Java libraries to add
support for sorting with the addition of the Collections
Framework to the Java 2 SDK, version 1.2. Classes like String
and Integer
now implement the Comparable
interface to provide a natural sorting order. For those classes
without a natural order, or when you desire a different order
than the natural order, you can implement the Comparator
interface to define your own.
To take advantage of the sorting capabilities, the Collections
Framework provides two interfaces that use it: SortedSet
and SortedMap
.
Comparable interface
The Comparable
interface, in the java.lang
package, is for when a class has a natural ordering. Given a
collection of objects of the same type, the interface allows you
to order the collection into that natural ordering.
The compareTo()
method compares the current instance
with an element passed in as an argument. If the current instance
comes before the argument in the ordering, a negative value is
returned. If the current instance comes after, then a positive
value is returned. Otherwise, zero is returned. It is not a
requirement that a zero return value signifies equality of
elements. A zero return value just signifies that two objects are
ordered at the same position.
There are fourteen classes in the Java 2 SDK, version 1.2
that implement the Comparable
interface. The following
table shows their natural ordering. While some classes share the
same natural ordering, you can sort only classes that are mutually
comparable.
Class | Ordering |
---|
BigDecimal,
BigInteger,
Byte,
Double,
Float,
Integer,
Long,
Short | Numerical |
Character | Numerical by Unicode value |
CollationKey | Locale-sensitive string ordering |
Date | Chronological |
File | Numerical by Unicode value of characters in
fully-qualified, system-specific pathname |
ObjectStreamField | Numerical by Unicode value of characters in name |
String | Numerical by Unicode value of characters in string |
The documentation for the compareTo()
method of String
defines the ordering lexicographically. This means the comparison is
of the numerical values of the characters in the text, which is not
necessarily alphabetically in all languages. For locale-specific ordering, use
Collator
with CollationKey
.
The following demonstrates the use of Collator
with CollationKey
to do a locale-specific sorting:
import java.text.*;
import java.util.*;
public class CollatorTest {
public static void main(String args[]) {
Collator collator = Collator.getInstance();
CollationKey key1 = collator.getCollationKey("Tom");
CollationKey key2 = collator.getCollationKey("tom");
CollationKey key3 = collator.getCollationKey("thom");
CollationKey key4 = collator.getCollationKey("Thom");
CollationKey key5 = collator.getCollationKey("Thomas");
Set set = new TreeSet();
set.add(key1);
set.add(key2);
set.add(key3);
set.add(key4);
set.add(key5);
printCollection(set);
}
static private void printCollection(
Collection collection) {
boolean first = true;
Iterator iterator = collection.iterator();
System.out.print("[");
while (iterator.hasNext()) {
if (first) {
first = false;
} else {
System.out.print(", ");
}
CollationKey key = (CollationKey)iterator.next();
System.out.print(key.getSourceString());
}
System.out.println("]");
}
}
Running the program produces the following output:
[thom, Thom, Thomas, tom, Tom]
If the names were stored directly, without using Collator
,
then the lowercase names would appear apart from the uppercase
names:
[Thom, Thomas, Tom, thom, tom]
Making your own class Comparable
is just a matter of
implementing the compareTo()
method. It usually involves
relying on the natural ordering of several data members. Your own
classes should also override equals()
and hashCode()
to ensure two equal objects return the same hash code.
Comparator interface
When a class wasn't designed to implement java.lang.Comparable
,
you can provide your own java.util.Comparator
. Providing
your own Comparator
also works if you don't like the
default Comparable
behavior.
The return values of the compare()
method of Comparator
are similar to the compareTo()
method of Comparable
.
In this case, if the first element comes before the second
element in the ordering, a negative value is returned. If the
first element comes after, then a positive value is returned.
Otherwise, zero is returned. Similar to Comparable
, a
zero return value does not signify equality of elements. A zero
return value just signifies that two objects are ordered at the
same position. It's up to the user of the Comparator
to
determine how to deal with it. If two unequal elements compare to
zero, you should first be sure that is what you want and second
document the behavior.
To demonstrate, you may find it easier to write a new Comparator
that ignores case, instead of using Collator
to do a
locale-specific, case-insensitive comparison. The following is
one such implementation:
class CaseInsensitiveComparator implements Comparator {
public int compare(Object element1, Object element2) {
String lowerE1 = ((String)element1).toLowerCase();
String lowerE2 = ((String)element2).toLowerCase();
return lowerE1.compareTo(lowerE2);
}
}
Because every class subclasses Object
at some point, it
is not a requirement that you implement the equals()
method. In fact, in most cases you won't. Do keep in mind the equals()
method checks for equality of Comparator
implementations, not the objects being compared.
The Collections
class has one predefined Comparator
available for reuse. Calling Collections.reverseOrder()
returns a Comparator
that sorts objects that implement
the Comparable
interface in reverse order.
Exercise
SortedSet interface
The Collections Framework provides a special Set
interface for maintaining elements in a sorted order: SortedSet
.
The interface provides access methods to the ends of the set
as well as to subsets of the set. When working with subsets of
the list, changes to the subset are reflected in the source set.
In addition, changes to the source set are reflected in the
subset. This works because subsets are identified by elements at
the end points, not indices. In addition, if the fromElement
is part of the source set, it is part of the subset. However, if
the toElement
is part of the source set, it is not part
of the subset. If you would like a particular to-element to be in
the subset, you must find the next element. In the case of a String
,
the next element is the same string with a null character
appended (string+"\0"
).;
The elements added to a SortedSet
must either
implement Comparable
or you must provide a Comparator
to the constructor of its implementation class: TreeSet
.
(You can implement the interface yourself. But the Collections
Framework only provides one such concrete implementation class.)
To demonstrate, the following example uses the reverse order Comparator
available from the Collections
class:
Comparator comparator = Collections.reverseOrder();
Set reverseSet = new TreeSet(comparator);
reverseSet.add("Bernadine");
reverseSet.add("Elizabeth");
reverseSet.add("Gene");
reverseSet.add("Elizabeth");
reverseSet.add("Clara");
System.out.println(reverseSet);
Running the program produces the following output:
[Gene, Elizabeth, Clara, Bernadine]
Because sets must hold unique items, if comparing two
elements when adding an element results in a zero return value
(from either the compareTo()
method of Comparable
or the compare()
method of Comparator
), then
the new element is not added. If the elements are equal, then
that is okay. However, if they are not, then you should modify
the comparison method such that the comparison is compatible with
equals()
.
Using the prior CaseInsensitiveComparator
to
demonstrate this problem, the following creates a set with three
elements: thom, Thomas, and Tom, not five elements as might be
expected.
Comparator comparator = new CaseInsensitiveComparator();
Set set = new TreeSet(comparator);
set.add("Tom");
set.add("tom");
set.add("thom");
set.add("Thom");
set.add("Thomas");
SortedMap interface
The Collections Framework provides a special Map
interface for maintaining keys in a sorted order: SortedMap
.
The interface provides access methods to the ends of the map
as well as to subsets of the map. Working with a SortedMap
is just like a SortedSet
, except the sort is done on the
map keys. The implementation class provided by the Collections
Framework is a TreeMap
.
Because maps can only have one value for every key, if
comparing two keys when adding a key-value pair results in a zero
return value (from either the compareTo()
method of Comparable
or the compare()
method of Comparator
), then
the value for the original key is replaced with the new value. If
the elements are equal, then that is okay. However, if they are
not, then you should modify the comparison method such that the
comparison is compatible with equals()
.