Recipe 7.9 Avoiding the Urge to Sort

Problem

Your data needs to be sorted, but you don't want to stop and sort it periodically.

Solution

Not everything that requires order requires an explicit sort operation. Just keep the data sorted at all times.

Discussion

You can avoid the overhead and elapsed time of an explicit sorting operation by ensuring that the data is in the correct order at all times. You can do this manually or, as of JDK 1.2, by using a TreeSet or a TreeMap . First, here is some code from a call tracking program that I first wrote on JDK 1.0 to keep track of people I had extended contact with. Far less functional than a Rolodex, my CallTrak program maintained a list of people sorted by last name and first name. It also had the city, phone number, and email address of each person. Here is a very small portion of the code surrounding the event handling for the New User push button:

/** The list of Person objects. */ protected List usrList = new ArrayList( ); /** The scrolling list */ protected java.awt.List visList = new java.awt.List( ); /** Add one (new) Person to the list, keeping the list sorted. */ protected void add(Person p) {     String lastName = p.getLastName( );     int i;     for (i=0; i<usrList.size( ); i++)         if (lastName.compareTo(((Person)(usrList.get(i))).getLastName( )) <= 0)             break;     usrList.add(i, p);     visList.add(p.getName( ), i);     visList.select(i);      // ensure current }

This code uses the String class compareTo(String) routine.

If I were writing this code today, I might well use a TreeSet (which keeps objects in order) or a TreeMap (which keeps the keys in order and maps from keys to values; the keys would be the name and the values would be the Person objects). Both insert the objects into a tree in the correct order, so an Iterator that traverses the tree always returns the objects in sorted order. In addition, they have methods such as headSet( ) and headMap( ), which give a new Set or Map of objects of the same class, containing the objects lexically before a given value. The tailSet( ) and tailMap( ) methods, similarly, return objects greater than a given value, and subSet( ) and subMap( ) return a range. The first( ) and last( ) methods retrieve the obvious components from the collection. The following program uses a TreeSet to sort some names:

// TreeSetDemo.java /* A TreeSet keeps objects in sorted order. We use a  * Comparator published by String for case-insensitive  * sorting order.  */ TreeSet tm = new TreeSet(String.CASE_INSENSITIVE_ORDER); tm.add("Gosling"); tm.add("da Vinci"); tm.add("van Gogh"); tm.add("Java To Go"); tm.add("Vanguard"); tm.add("Darwin"); tm.add("Darwin");    // TreeSet is Set, ignores duplicate. See Recipe 7.10. // Since it is sorted we can ask for various subsets System.out.println("Lowest (alphabetically) is " + tm.first( )); // Print how many elements are greater than "k" System.out.println(tm.tailSet("k").toArray( ).length +      " elements higher than \"k\""); // Print the whole list in sorted order System.out.println("Sorted list:"); java.util.Iterator t = tm.iterator( ); while (t.hasNext( ))     System.out.println(t.next( ));

One last point to note is that if you have a Hashtable or HashMap, you can convert it to a TreeMap , and therefore get it sorted, just by passing it to the TreeMap constructor:

TreeMap sorted = new TreeMap(unsortedHashMap);