Skip to main content
IBM 
ShopSupportDownloads
IBM HomeProductsConsultingIndustriesNewsAbout IBM
IBM : developerWorks : Java : Education - online courses
Java Collections Framework
Download tutorial zip fileView letter-sized PDF fileView A4-sized PDF fileE-mail this tutorial to a friend
Main menuSection menuGive feedback on this tutorialPrevious
Next Section
3. Collection interfaces and classes
  


Sorting page 8 of 8


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.

UML Diagram for Comparable Interface

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.

ClassOrdering
BigDecimal, BigInteger, Byte, Double, Float, Integer, Long, ShortNumerical
CharacterNumerical by Unicode value
CollationKeyLocale-sensitive string ordering
DateChronological
FileNumerical by Unicode value of characters in fully-qualified, system-specific pathname
ObjectStreamFieldNumerical by Unicode value of characters in name
StringNumerical 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.

UML Diagram for Comparator Interface

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.

UML Diagram for SortedSet Interface

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.

UML Diagram for SortedMap Interface

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().


Next Section
Main menuSection menuGive feedback on this tutorialPrevious
PrivacyLegalContact