Not everything that requires order requires an explicit sort operation. Just keep the data sorted at all times.
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, in Java 2, by using a
TreeSet
or a
TreeMap
. First, 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. For each person it also had the
city, phone number, and email address. Here is a portion of the code
that was the event handler for the New User push button:
/** The list of User objects. */ Vector usrList = new Vector( ); /** The scrolling list */ java.awt.List visList = new List( ); /** Add one (new) Candidate to the lists */ protected void add(Candidate c) { String n = c.lastname; int i; for (i=0; i<usrList.size( ); i++) if (n.compareTo(((Candidate)(usrList.elementAt(i))).lastname) <= 0) break; visList.add(c.getName( ), i); usrList.insertElementAt(c, i); visList.select(i); // ensure current }
This code uses the String
class
compareTo(String)
routine. This has the same name and
signature as the compareTo(Object)
in
Comparable
, but was added to the
String
class in JDK 1.1, before the
Comparable
interface was defined.
If I were writing this code today, on Java 2, I would probably
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 Candidate
objects). These 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 object of the same
class containing objects lexically before a given value. The
tailSet( )
and
tailMap( )
methods 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 Section 7.12. // 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
(and Java
2), 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);
3.145.107.100