Sorting

One

of the things missing in the Java 1.0

A

problem with writing generic sorting code is that sorting must perform

comparisons based on the actual type of the object. Of course, one approach is

to write a different sorting method for every different type, but you should be

able to recognize that this does not produce code that is easily re-used for

new types.

A

primary goal of programming design is to “separate things that change

from things that stay the same,” and here, the code that stays the same

is the general sort algorithm, but the thing that changes from one use to the

next is the way objects are compared. So instead of hard-wiring the comparison

code into many different sort routines, the technique of the

The

following

describes how to compare two objects, and thus encapsulates “the things

that change” for this particular problem:

//: Compare.java
// Interface for sorting callback:
package c08;
 
interface Compare {
  boolean lessThan(Object lhs, Object rhs);
  boolean lessThanOrEqual(Object lhs, Object rhs);
} ///:~ 

For

both methods, the

represents the “left hand” object and the

represents the “right hand” object in the comparison.

A

subclass of

can be created that implements the Quicksort using

.

The algorithm, which is known for its speed, will not be explained here. For

details, see

,

by Binstock

&

Rex, Addison-Wesley 1995.

//: SortVector.java
// A generic sorting vector
package c08;
import java.util.*;
 
public class SortVector extends Vector {
  private Compare compare; // To hold the callback
  public SortVector(Compare comp) {
    compare = comp;
  }
  public void sort() {
    quickSort(0, size() - 1);
  }
  private void quickSort(int left, int right) {
    if(right > left) {
      Object o1 = elementAt(right);
      int i = left - 1;
      int j = right;
      while(true) {
        while(compare.lessThan(
              elementAt(++i), o1))
          ;
        while(j > 0)
          if(compare.lessThanOrEqual(
             elementAt(--j), o1))
            break; // out of while
        if(i >= j) break;
        swap(i, j);
      }
      swap(i , right);
      quickSort(left, i-1);
      quickSort(i+1, right);
    }
  }
  private void swap(int loc1, int loc2) {
    Object tmp = elementAt(loc1);
    setElementAt(elementAt(loc2), loc1);
    setElementAt(tmp, loc2);
  }
} ///:~ 

You

can now see the reason for the term “callback,” since the

method “calls back” to the methods in

.

You can also see how this technique has produced generic, reusable code.

To

use the

,

you must create a class that implements

for the kind of objects that you’re sorting. This is a place where an

inner class is not essential, but it can make sense for code organization.

Here’s an example for

objects:

//: StringSortTest.java
// Testing the generic sorting Vector
package c08;
import java.util.*;
 
public class StringSortTest {
  static class StringCompare implements Compare {
    public boolean lessThan(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) < 0;
    }
    public boolean
    lessThanOrEqual(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) <= 0;
    }
  }
  public static void main(String[] args) {
    SortVector sv =
      new SortVector(new StringCompare());
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    sv.sort();
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~ 

The

inner class is

because it does not need a link to an outer class in order for it to function.

You

can see how, once the framework is set up, it’s easy to reuse a design

like this – you simply write the class that encapsulates “the

things that change” and hand an object to the

.

The

comparison forces the strings to lower case, so that the capital

’s

end up next to the small

’s

and not in some entirely different place. This example shows, however, a slight

deficiency in this approach, since the test code above puts the uppercase and

lowercase single letters of the same letter in the order that they appear: A a

b B c C d D. This is not usually much of a problem, because you’re

usually working with longer strings and in that situation the effect

doesn’t show up. (The Java 1.2

Inheritance

(

)

is used here to create a new type of

– that is,

with some added functionality. The use of inheritance here is powerful but it

presents problems. It turns out that some methods are

(described

in Chapter 7), so you cannot override them. If you want to create a sorted

that accepts and produces only

objects

you run into a wall, since

and

are

,

and these are precisely the methods you’d need to override so they accept

and produce only

objects. No luck there.

On

the other hand, consider

//: StrSortVector.java
// Automatically sorted Vector that 
// accepts and produces only Strings
package c08;
import java.util.*;
 
public class StrSortVector {
  private SortVector v = new SortVector(
    // Anonymous inner class:
    new Compare() {
      public boolean
      lessThan(Object l, Object r) {
        return
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) < 0;
      }
      public boolean
      lessThanOrEqual(Object l, Object r) {
        return
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) <= 0;
      }
    }
  );
  private boolean sorted = false;
  public void addElement(String s) {
    v.addElement(s);
    sorted = false;
  }
  public String elementAt(int index) {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return (String)v.elementAt(index);
  }
  public Enumeration elements() {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return v.elements();
  }
  // Test it:
  public static void main(String[] args) {
    StrSortVector sv = new StrSortVector();
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~ 

This

quickly reuses the code from

to create the desired functionality. However, not all of the

methods from

and

appear in

.

When reusing code this way, you can make a definition in the new class for each

one in the contained class, or you can start with just a few and periodically

go back and add more when you need them. Eventually the new class design will

settle down.

The

advantage to this approach is that it will take only

objects and produce only

objects, and the checking happens at compile time instead of run time. Of

course, that’s only true for

and

;

still produces an

that is untyped at compile time. Type checking for the

You

can see there’s a flag called

in this class. You could sort the vector every time

is called, and constantly keep it in a sorted state. But usually people add a

lot of elements to a

before

beginning to read it. So sorting after every

would be less efficient than waiting until someone wants to read the vector and

then sorting it, which is what is done here. The technique of delaying a

process until it is absolutely necessary is called

|

|