Comparators
Both TreeSet and TreeMap store elements in sorted order. However, it is the comparator that defines precisely what “sorted order” means. By default, these classes store their elements by using what Java refers to as “natural ordering,” which is usually the ordering that you would expect. (A before B, 1 before 2, and so forth.) If you want to order elements a different way, then specify a Comparator object when you construct the set or map. Doing so gives you the ability to govern precisely how elements are stored within sorted collections and maps.
The Comparator interface defines two methods: compare( ) and equals( ). The compare( ) method, shown here, compares two elements for order:
int compare(Object obj1, Object obj2)
obj1 and obj2 are the objects to be compared. This method returns zero if the objects are equal. It returns a positive value if obj1 is greater than obj2. Otherwise, a negative value is returned. The method can throw a ClassCastException if the types of the objects are not compatible for comparison. By overriding compare( ), you can alter the way that objects are ordered. For example, to sort in reverse order, you can create a comparator that reverses the outcome of a comparison.
The equals( ) method, shown here, tests whether an object equals the invoking comparator:
boolean equals(Object obj)
obj is the object to be tested for equality. The method returns true if obj and the invoking object are both Comparator objects and use the same ordering. Otherwise, it returns false. Overriding equals( ) is unnecessary, and most simple comparators will not do so.
Using a Comparator
The following is an example that demonstrates the power of a custom comparator. It implements the compare( ) method so that it operates in reverse of normal. Thus, it causes a tree set to be stored in reverse order.
// Use a custom comparator.
import java.util.*;
// A reverse comparator for strings.
class MyComp implements Comparator {
public int compare(Object a, Object b) {
String aStr, bStr;
aStr = (String) a;
bStr = (String) b;
// reverse the comparison
return bStr.compareTo(aStr);
}
// no need to override equals
}
class CompDemo {
public static void main(String args[]) {
// Create a tree set
TreeSet ts = new TreeSet(new MyComp());
// Add elements to the tree set
ts.add("C");
ts.add("A");
ts.add("B");
ts.add("E");
ts.add("F");
ts.add("D");
// Get an iterator
Iterator i = ts.iterator();
// Display elements
while(i.hasNext()) {
Object element = i.next();
System.out.print(element + " ");
}
System.out.println();
}
}
As the following output shows, the tree is now stored in reverse order:
F E D C B A
Look closely at the MyComp class, which implements Comparator and overrides compare( ). (As explained earlier, overriding equals( ) is neither necessary nor common.) Inside compare( ), the String method compareTo( ) compares the two strings. However, bStr—not aStr—invokes compareTo( ). This causes the outcome of the comparison to be reversed.
For a more practical example, the following program is an updated version of the TreeMap program shown earlier that stores account balances. In the previous version, the accounts were sorted by name, but the sorting began with the first name. The following program sorts the accounts by last name. To do so, it uses a comparator that compares the last name of each account. This results in the map being sorted by last name.
// Use a comparator to sort accounts by last name.
import java.util.*;
// Compare last whole words in two strings.
class TComp implements Comparator {
public int compare(Object a, Object b) {
int i, j, k;
String aStr, bStr;
aStr = (String) a;
bStr = (String) b;
// find index of beginning of last name
i = aStr.lastIndexOf(' ');
j = bStr.lastIndexOf(' ');
k = aStr.substring(i).compareTo(bStr.substring(j));
if(k==0) // last names match, check entire name
return aStr.compareTo(bStr);
else
return k;
}
// no need to override equals
}
class TreeMapDemo2 {
public static void main(String args[]) {
// Create a tree map
TreeMap tm = new TreeMap(new TComp());
// Put elements to the map
tm.put("John Doe", new Double(3434.34));
tm.put("Tom Smith", new Double(123.22));
tm.put("Jane Baker", new Double(1378.00));
tm.put("Todd Hall", new Double(99.22));
tm.put("Ralph Smith", new Double(-19.08));
// Get a set of the entries
Set set = tm.entrySet();
// Get an iterator
Iterator itr = set.iterator();
// Display elements
while(itr.hasNext()) {
Map.Entry me = (Map.Entry)itr.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
// Deposit 1000 into John Doe's account
double balance = ((Double)tm.get("John Doe")).doubleValue();
tm.put("John Doe", new Double(balance + 1000));
System.out.println("John Doe's new balance: " +
tm.get("John Doe"));
}
}
Here is the output; notice that the accounts are now sorted by last name:
Jane Baker: 1378.0
John Doe: 3434.34
Todd Hall: 99.22
Ralph Smith: -19.08
Tom Smith: 123.22
John Doe’s new balance: 4434.34
The comparator class TComp compares two strings that hold first and last names. It does so by first comparing last names. To do this, it finds the index of the last space in each string and then compares the substrings of each element that begin at that point. In cases where last names are equivalent, the first names are then compared. This yields a tree map that is sorted by last name, and within last name by first name. You can see this because Ralph Smith comes before Tom Smith in the output.
The Collection Algorithms
The collections framework defines several algorithms that can be applied to collections and maps. These algorithms are defined as static methods within the Collections class. They are summarized in Table 15-9. Several of the methods can throw a ClassCastException, which occurs when an attempt is made to compare incompatible types, or an UnsupportedOperationException, which occurs when an attempt is made to modify an unmodifiable collection.
Notice that several methods, such as synchronizedList( ) and synchronizedSet( ), are used to obtain synchronized (thread-safe) copies of the various collections. As explained, none of the standard collections implementations are synchronized. You must use the synchronization algorithms to provide synchronization. One other point: iterators to synchronized collections must be used within synchronized blocks.
The set of methods that begins with unmodifiable returns views of the various collections that cannot be modified. These will be useful when you want to grant some process read—but not write—capabilities on a collection.
The Algorithms Defined by Collections
static int binarySearch(List list, Object value, Comparator c): Searches for value in list ordered according to c. Returns the position of value in list, or −1 if value is not found.
static int binarySearch(List list, Object value): Searches for value in list. The list must be sorted. Returns the position of value in list, or −1 if value is not found.
static void copy(List list1, List list2): Copies the elements of list2 to list1.
static Enumeration enumeration(Collection c): Returns an enumeration over c. (See “The Enumeration Interface,” later in this chapter.)
static void fill(List list, Object obj): Assigns obj to each element of list.
static int indexOfSubList(List list, List subList): Searches list for the first occurrence of subList. Returns the index of the first match, or –1 if no match is found. (Added by Java 2, v1.4)
static int lastIndexOfSubList(List list, List subList): Searches list for the last occurrence of subList. Returns the index of the last match, or –1 if no match is found. (Added by Java 2, v1.4)
static ArrayList list(Enumeration enum): Returns an ArrayList that contains the elements of enum. (Added by Java 2, v1.4)
static Object max(Collection c, Comparator comp): Returns the maximum element in c as determined by comp.
static Object max(Collection c): Returns the maximum element in c as determined by natural ordering. The collection need not be sorted.
static Object min(Collection c, Comparator comp): Returns the minimum element in c as determined by comp. The collection need not be sorted.
static Object min(Collection c): Returns the minimum element in c as determined by natural ordering.
static List nCopies(int num, Object obj): Returns num copies of obj contained in an immutable list. num must be greater than or equal to zero.
static boolean replaceAll(List list, Object old, Object new): Replaces all occurrences of old with new in list. Returns true if at least one replacement occurred. Returns false, otherwise. (Added by Java 2, v1.4)
static void reverse(List list): Reverses the sequence in list.
static Comparator reverseOrder( ): Returns a reverse comparator (a comparator that reverses the outcome of a comparison between two elements).
static void rotate(List list, int n): Rotates list by n places to the right. To rotate left, use a negative value for n. (Added by Java 2, v1.4)
static void shuffle(List list, Random r): Shuffles (i.e., randomizes) the elements in list by using r as a source of random numbers.
static void shuffle(List list): Shuffles (i.e., randomizes) the elements in list.
static Set singleton(Object obj): Returns obj as an immutable set. This is an easy way to convert a single object into a set.
static List singletonList(Object obj): Returns obj as an immutable list. This is an easy way to convert a single object into a list. (Added by Java 2, v1.3)
static Map singletonMap(Object k, Object v): Returns the key/value pair k/v as an immutable map. This is an easy way to convert a single key/value pair into a map. (Added by Java 2, v1.3)
static void sort(List list, Comparator comp): Sorts the elements of list as determined by comp.
static void sort(List list): Sorts the elements of list as determined by their natural ordering.
static void swap(List list, int idx1, int idx2): Exchanges the elements in list at the indices specified by idx1 and idx2. (Added by Java 2, v1.4)
static Collection synchronizedCollection(Collection c): Returns a thread-safe collection backed by c.
static List synchronizedList(List list): Returns a thread-safe list backed by list.
static Map synchronizedMap(Map m): Returns a thread-safe map backed by m.
static Set synchronizedSet(Set s): Returns a thread-safe set backed by s.
static SortedMap synchronizedSortedMap(SortedMap sm): Returns a thread-safe sorted set backed by sm.
static SortedSet synchronizedSortedSet(SortedSet ss): Returns a thread-safe set backed by ss.
static Collection unmodifiableCollection(Collection c): Returns an unmodifiable collection backed by c.
static List unmodifiableList(List list): Returns an unmodifiable list backed by list.
static Map unmodifiableMap(Map m): Returns an unmodifiable map backed by m.
static Set unmodifiableSet(Set s): Returns an unmodifiable set backed by s.
static SortedMap unmodifiableSortedMap(SortedMap sm): Returns an unmodifiable sorted map backed by sm.
static SortedSet unmodifiableSortedSet(SortedSet ss): Returns an unmodifiable sorted set backed by ss.
Collections defines three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. All are immutable. EMPTY_MAP was added by Java 2, version 1.3.
The following program demonstrates some of the algorithms. It creates and initializes a linked list. The reverseOrder( ) method returns a Comparator that reverses the comparison of Integer objects. The list elements are sorted according to this comparator and then are displayed. Next, the list is randomized by calling shuffle( ), and then its minimum and maximum values are displayed.
// Demonstrate various algorithms.
import java.util.*;
class AlgorithmsDemo {
public static void main(String args[]) {
// Create and initialize linked list
LinkedList ll = new LinkedList();
ll.add(new Integer(-8));
ll.add(new Integer(20));
ll.add(new Integer(-20));
ll.add(new Integer(8));
// Create a reverse order comparator
Comparator r = Collections.reverseOrder();
// Sort list by using the comparator
Collections.sort(ll, r);
// Get iterator
Iterator li = ll.iterator();
System.out.print("List sorted in reverse: ");
while(li.hasNext())
System.out.print(li.next() + " ");
System.out.println();
Collections.shuffle(ll);
// display randomized list
li = ll.iterator();
System.out.print("List shuffled: ");
while(li.hasNext())
System.out.print(li.next() + " ");
System.out.println();
System.out.println("Minimum: " + Collections.min(ll));
System.out.println("Maximum: " + Collections.max(ll));
}
}
Output from this program is shown here:
List sorted in reverse: 20 8 -8 -20
List shuffled: 20 -20 8 -8
Minimum: -20
Maximum: 20
Notice that min( ) and max( ) operate on the list after it has been shuffled. Neither requires a sorted list for its operation.
