11.6 Sorted Sets and Sorted Maps

Sets and maps have special interfaces, called SortedSet and SortedMap , for implementations that sort their elements in a specific order (see Figures 11.2 and 11.3). Objects can specify their natural order by implementing the Comparable interface, or be dictated a total order by a comparator object that implements the Comparator interface.

We'll first look at the two interfaces Comparable and Comparator , before discussing sorted sets and maps.

The `Comparator` Interface

Precise control of ordering can be achieved by creating a customized comparator that imposes a specific total ordering on the elements. All comparators implement the Comparator interface, which has the following single method:

 int compare(Object o1, Object o2)

The compare() method returns a negative integer, zero, or a positive integer if the first object is less than, equal to, or greater than the second object, according to the total order. Since this method tests for equality, it is strongly recommended that its implementation does not contradict the semantics of the equals() method (see Section 11.7).

The `Comparable` Interface

A class can define the natural order of its instances by implementing the Comparable interface. Many of the standard classes in the Java API, such as the wrapper classes, String , Date , and File , implement this interface. The java.lang.Comparable interface specifies a single method:

 int compareTo(Object o)

This method returns a negative integer, zero, or a positive integer if the current object is less than, equal to, or greater than the specified object, based on the natural order. It throws a ClassCastException if the reference value passed in the argument cannot be cast to the type of the current object. Since this method tests for equality, it is recommended that its implementation does not contradict the semantics of the equals() method (see Section 11.7).

Objects implementing this interface can be used as

elements in a sorted set
keys in a sorted map
elements in lists that are sorted manually using the Collections.sort() method

Note that the natural order for String objects (and Character objects) is lexicographical order (see Section 10.5, p. 412). Strings will be lexicographically maintained as elements in a sorted set or as keys in a sorted map that uses natural ordering. A collection of strings sorted by natural order would be ordered in lexicographical order.

The natural order for objects of a numerical wrapper type is ascending order of the values of the corresponding numerical primitive type (see Section 10.3, p. 396). As elements in a sorted set, or as keys in a sorted map, the objects would be maintained in ascending order.

An alternative ordering to the default natural order can be specified by passing a Comparator to the constructor when the sorted set or map is created. The Collections and Arrays classes provide utility methods for sorting, which also take a Comparator (see Section 11.8, p. 482).

Example 11.5 demonstrates the use of different comparators for strings. The program creates an empty sorted set using the TreeSet class (discussed later in this section). Each program argument is added to the sorted set in the loop at (2). A textual representation of the sorted set is then printed at (3). The output shows the sorting order in which the elements are maintained in the set. The set is traversed according to the sorting order.

The String class implements the Comparable interface, providing an implementation of the compareTo() method. The compareTo() method defines the natural order for strings, which is lexicographical. The natural order is used to maintain the program arguments sorted lexicographically when the sorted set at (1a) is used. If we wish to maintain the strings in a different ordering, we need to provide a customized comparator.

The String class provides a static field ( CASE_INSENSITIVE_ORDER ) that denotes a comparator object with a compare() method that ignores the case when comparing strings lexicographically. This particular total order is used to maintain the program arguments sorted when the sorted set at (1b) is used. The comparator is passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total order, which is a case-insensitive order.

We can create a string comparator that enforces rhyming order on the strings. In rhyming order, two strings are compared by examining their corresponding characters at each position in the two strings, starting with the characters in the last position. First the characters in the last position are compared, then those in the last but one position, and so on. For example, given the two strings "report" and " court " , the last two characters in both the strings are the same. Continuing backward in the two strings, the character 'o' in the first string is less than the character 'u' in the second string. According to the rhyming order, the string "report" is less than the string "court" .

Comparing two strings according to the rhyming order is equivalent to reversing the strings and comparing the reversed strings lexicographically. If we reverse the two strings, "report" and "court" , the reversed string "troper" is lexicographically less than the reversed string "truoc" .

A rhyming order comparator is implemented by the RhymingStringComparator class in Example 11.5. The compare() method at (4) first creates reversed versions of the strings passed as arguments. A reversed version of a string is created using a string buffer, which is first reversed and then converted back to a string, as shown at (5). The compare() method then calls the compareTo() method at (6) to compare the reversed strings, as the lexicographical order for the reversed strings is equivalent to the rhyming order for the original strings. This particular total order is used to maintain the program arguments sorted when the sorted set at (1c) is used. The comparator is again passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total order, which is rhyming order.

Example 11.5 Natural Order and Total Order

 import java.util.*; public class ComparatorUsage {     public static void main(String[] args) {         // Choice of comparator.     //  Set strSet = new TreeSet();                              // (1a)     //  Set strSet = new TreeSet(String.CASE_INSENSITIVE_ORDER); // (1b)         Set strSet = new TreeSet(new RhymingStringComparator()); // (1c)         // Add each command line argument to the set.         for (int i=0; i < args.length; i++) {                    // (2)             strSet.add(args[i]);         }         System.out.println(strSet);                              // (3)     } } class RhymingStringComparator implements Comparator {     public int compare(Object obj1, Object obj2) {               // (4)         // (5) Create reversed versions of the strings.         String reverseStr1 = new StringBuffer((String) obj1).reverse().toString();         String reverseStr2 = new StringBuffer((String) obj2).reverse().toString();         // Compare the reversed strings lexicographically.         return reverseStr1.compareTo(reverseStr2);               // (6)     } }

The program is run with the following program arguments on the command line:

 >java ComparatorUsage court Stuart report Resort assort support transport distort

Output from the program using the natural order (1a):

 [Resort, Stuart, assort, court, distort, report, support, transport]

Output from the program using the case insensitive order (1b):

 [assort, court, distort, report, Resort, Stuart, support, transport]

Output from the program using the rhyming order (1c):

 [Stuart, report, support, transport, Resort, assort, distort, court]

The `SortedSet` Interface

The SortedSet interface extends the Set interface to provide the functionality for handling sorted sets.

 // Range-view operations SortedSet headSet(Object toElement) SortedSet tailSet(Object fromElement) SortedSet subSet(Object fromElement, Object toElement)

The headSet() method returns a view of a portion of this sorted set, whose elements are strictly less than the specified element. Similarly, the tailSet() method returns a view of the portion of this sorted set, whose elements are greater than or equal to the specified element. The subSet() method returns a view of the portion of this sorted set, whose elements range from fromElement , inclusive, to toElement , exclusive. Note that the views present the elements sorted in the same order as the underlying sorted map.

 // First-last elements Object first() Object last()

The first() method returns the first element currently in this sorted set, and the last() method returns the last element currently in this sorted set. Both throw a NoSuchElementException if the sorted set is empty.

 // Comparator access Comparator comparator()

This method returns the comparator associated with this sorted set, or null if it uses the natural ordering of its elements. This comparator, if defined, is used by default when a sorted set is constructed , and also used when copying elements into new sorted sets.

The `SortedMap` Interface

The SortedMap interface extends the Map interface to provide the functionality for implementing maps with sorted keys . Its operations are analogous to those of the SortedSet interface, applied to maps and keys rather than to sets and elements.

 // Range-view operations SortedMap headMap(Object toKey) SortedMap tailMap(Object fromKey) SortedMap subMap(Object fromKey, Object toKey) // First-last keys Object firstKey() Object lastKey() // Comparator access Comparator comparator()

`TreeSet` and `TreeMap`

The TreeSet and TreeMap classes implement the SortedSet and SortedMap interfaces, respectively. By default, operations on sorted sets or maps rely on the natural ordering of the elements or keys, respectively. However, a total ordering can be specified by passing a customized comparator to the constructor.

These implementations use balanced trees, which deliver excellent performance for all operations. Searching in a HashSet or HashMap can be faster than in a TreeSet or TreeMap , as hashing algorithms usually offer better performance than the search algorithms for balanced trees.

Each class provides four constructors:

 TreeSet() TreeMap()

A standard constructor to create a new empty sorted set or map, according to the natural order of the elements or the keys, respectively.

 TreeSet(Comparator c) TreeMap(Comparator c)

A constructor that takes an explicit comparator for ordering the elements or the keys.

 TreeSet(Collection c) TreeMap(Map m)

A constructor that can create a sorted set or a sorted map based on a collection or a map, according to the natural order of the elements or the keys, respectively.

 TreeSet(SortedSet s) TreeMap(SortedMap m)

A constructor that creates a new set or map containing the same elements or entries as the specified sorted set or sorted map, with the same ordering.

Example 11.6 Using SortedMaps

 import java.util.*; public class WeightGroups2 {     public static void main(String[] args) {         // Create a map to store the frequency for each group.         Map groupFreqData = new HashMap();         int numArgs = args.length;         for (int i=0; i<numArgs; i++) {             // Get the value from argument and group into intervals of 5    (1)             double weight = Double.parseDouble(args[i]);             Integer weightGroup = new Integer((int) Math.round(weight/5)*5);             // Increment count, set to 1 if it's the first value of group.  (2)             Integer oldCount = (Integer) groupFreqData.get(weightGroup);             Integer newCount = (oldCount==null) ?                 new Integer(1) :                 new Integer(oldCount.intValue()+1);             groupFreqData.put(weightGroup, newCount);                    // (3)         }         /* Only the histogram for the weight groups between 50 and 150            is of interest. Print frequency for these groups in a sorted order. */         // Transfer the data to a sorted map.         SortedMap sortedGroupFreqData = new TreeMap(groupFreqData);      // (4)         // Select the relevant sub-map.         SortedMap selectedGroupFreqData =                                // (5)                 sortedGroupFreqData.subMap(new Integer(50), new Integer(150));         /** Print by traversing the sorted entries of weight groups (key)             and count (value). */         Iterator entryIterator =                 selectedGroupFreqData.entrySet().iterator();             // (6)         while (entryIterator.hasNext()) {             Map.Entry entry = (Map.Entry) entryIterator.next();          // (7)             // Extract groups (key) and count (value) from entry.           (8)             Integer group = (Integer) entry.getKey();             Integer count = (Integer) entry.getValue();             int intCount = count.intValue();             /* Use the fill() method from the Arrays class to create a                string consisting of intCount number of '*'. */             char[] bar = new char[intCount];             Arrays.fill(bar, '*');                                       // (9)             System.out.println(group + ":\t" + new String(bar));         } // end while     } // end main() } // end of class

Running the program with the following argument:

 java WeightGroups2 74 75 93 75 93 82 61 92 10 185

gives the following output:

 60:     * 75:     *** 80:     * 90:     * 95:     **

Example 11.6 illustrates sorted maps. It also prints a textual histogram like the one in Example 11.4, but now the histogram is limited to a range of weight groups. The program defines the following steps:

Read the program arguments, converting each weight to its corresponding weight group and updating the frequency of the weight group. This is the same step as in Example 11.4.

Transfer the data to a sorted map, as shown at (4).

 SortedMap sortedGroupFreqData = new TreeMap(groupFreqData);      // (4)

Create a sorted submap view of the required range of weight groups, as shown at (5).

 SortedMap selectedGroupFreqData =                                // (5)         sortedGroupFreqData.subMap(new Integer(50), new Integer(150));

Set up an iterator on a set view of entries in the submap, as shown at (6). First, a set view of the entries is created using the entrySet() method. The elements (i.e., the entries) in this set view will be sorted, since the underlying submap is sorted. An iterator is then created on this set.
```
 Iterator entryIterator =         selectedGroupFreqData.entrySet().iterator();             // (6) 
```
Use the iterator to traverse the underlying set. Each element in this set is an entry in the underlying sorted submap. Each entry conforms to the Map.Entry interface, which allows the key and the value to be extracted, as shown at (8).
```
 // Extract groups (key) and count (value) from entry.               (8) Integer group = (Integer) entry.getKey(); Integer count = (Integer) entry.getValue(); int intCount = count.intValue(); 
```

The Comparator Interface

The Comparable Interface