| |
java 1.0和1.1库都缺少的一样东西是算术运算，甚至没有最简单的排序运算方法。因此，我们最好创建一个vector，利用经典的quicksort（快速排序）方法对其自身进行排序。
编写通用的排序代码时，面临的一个问题是必须根据对象的实际类型来执行比较运算，从而实现正确的排序。当然，一个办法是为每种不同的类型都写一个不同的排序方法。然而，应认识到假若这样做，以后增加新类型时便不易实现代码的重复利用。
程序设计一个主要的目标就是“将发生变化的东西同保持不变的东西分隔开”。在这里，保持不变的代码是通用的排序算法，而每次使用时都要变化的是对象的实际比较方法。因此，我们不可将比较代码“硬编码”到多个不同的排序例程内，而是采用“回调”技术。利用回调，经常发生变化的那部分代码会封装到它自己的类内，而总是保持相同的代码则“回调”发生变化的代码。这样一来，不同的对象就可以表达不同的比较方式，同时向它们传递相同的排序代码。
下面这个“接口”（interface）展示了如何比较两个对象，它将那些“要发生变化的东西”封装在内：
//: compare.java
// interface for sorting callback:
package c08;
interface compare {
boolean lessthan(object lhs, object rhs);
boolean lessthanorequal(object lhs, object rhs);
} ///:~
对这两种方法来说，lhs代表本次比较中的“左手”对象，而rhs代表“右手”对象。
可创建vector的一个子类，通过compare实现“快速排序”。对于这种算法，包括它的速度以及原理等等，在此不具体说明。欲知详情，可参考binstock和rex编著的《practical algorithms for programmers》，由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);
}
} ///:~
现在，大家可以明白“回调”一词的来历，这是由于quicksort()方法“往回调用”了compare中的方法。从中亦可理解这种技术如何生成通用的、可重复利用（再生）的代码。
为使用sortvector，必须创建一个类，令其为我们准备排序的对象实现compare。此时内部类并不显得特别重要，但对于代码的组织却是有益的。下面是针对string对象的一个例子：
//: 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());
}
} ///:~
内部类是“静态”（static）的，因为它毋需连接一个外部类即可工作。
大家可以看到，一旦设置好框架，就可以非常方便地重复使用象这样的一个设计——只需简单地写一个类，将“需要发生变化”的东西封装进去，然后将一个对象传给sortvector即可。
比较时将字串强制为小写形式，所以大写a会排列于小写a的旁边，而不会移动一个完全不同的地方。然而，该例也显示了这种方法的一个不足，因为上述测试代码按照出现顺序排列同一个字母的大写和小写形式：a a b b c c d d。但这通常不是一个大问题，因为经常处理的都是更长的字串，所以上述效果不会显露出来（java 1.2的集合提供了排序功能，已解决了这个问题）。
继承（extends）在这儿用于创建一种新类型的vector——也就是说，sortvector属于一种vector，并带有一些附加的功能。继承在这里可发挥很大的作用，但了带来了问题。它使一些方法具有了final属性（已在第7章讲述），所以不能覆盖它们。如果想创建一个排好序的vector，令其只接收和生成string对象，就会遇到麻烦。因为addelement()和elementat()都具有final属性，而且它们都是我们必须覆盖的方法，否则便无法实现只能接收和产生string对象。
但在另一方面，请考虑采用“合成”方法：将一个对象置入一个新类的内部。此时，不是改写上述代码来达到这个目的，而是在新类里简单地使用一个sortvector。在这种情况下，用于实现compare接口的内部类就可以“匿名”地创建。如下所示：
//: 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());
}
} ///:~
这样便可快速再生来自sortvector的代码，从而获得希望的功能。然而，并不是来自sortvector和vector的所有public方法都能在strsortvector中出现。若按这种形式再生代码，可在新类里为包含类内的每一个方法都生成一个定义。当然，也可以在刚开始时只添加少数几个，以后根据需要再添加更多的。新类的设计最终会稳定下来。
这种方法的好处在于它仍然只接纳string对象，也只产生string对象。而且相应的检查是在编译期间进行的，而非在运行期。当然，只有addelement()和elementat()才具备这一特性；elements()仍然会产生一个enumeration（枚举），它在编译期的类型是未定的。当然，对enumeration以及在strsortvector中的类型检查会照旧进行；如果真的有什么错误，运行期间会简单地产生一个违例。事实上，我们在编译或运行期间能保
|
|
