item 14: 考虑实现 COMPARABLE

ITEM 14: CONSIDER IMPLEMENTING COMPARABLE
  Object 中 并没有定义 compareTo 方法，而是将它作为一个接口 Comparable。看起来，compareTo 似乎与 equal 方法拥有同样的用途，只是除了简单的相等比较之外，它还允许顺序比较，而且它是通用的。通过实现 Comparable，类表明其实例具有自然顺序。对实现 Comparable 的对象数组排序非常简单:
Arrays.sort(a);
  同样，搜索、计算极值和维护可比较对象的自动排序集合也很容易。例如，下面的程序，它依赖于 String 实现 Comparable 的事实，打印了一个按字母顺序排列的命令行参数列表，去掉了重复项:

public class WordList {
  public static void main(String[] args) {
    Set<String> s = new TreeSet<>();
    Collections.addAll(s, args); 
    System.out.println(s);
  } 
}

  通过实现Comparable，您将允许类与依赖于这个接口的所有通用算法和集合实现进行互操作。你只需付出一点点努力就能获得巨大的力量。实际上，Java平台库中的所有值类以及所有 enum 类型都实现了Comparable。如果您编写的值类具有明显的自然顺序，如字母顺序、数字顺序或时间顺序，您应该实现可比较的接口:

public interface Comparable<T> {
  int compareTo(T t);
}

  compareTo 方法的规范如下:
  将此对象与指定的对象进行比较。返回一个负整数、零或正整数，因为该对象小于、等于或大于指定的对象。
  如果指定对象的类型阻止将其与此对象进行比较，则引发ClassCastException。
  在下面的描述中，符号 sgn(expression) 指定了数学 sgn 函数，根据表达式的值是负、零还是正，sgn函数被定义为返回 -1, 0 或 1。

• 实现者必须确保 sgn(x.compareTo(y)) == -sgn(y.compareTo(x))。(这意味着当且仅当 y.compareTo(x) 抛出异常时，x.compareTo(y) 必须抛出异常。)
• 实现者还必须确保关系是可传递的：(x.compareTo(y) > 0 && y.compareTo(z) > 0)表示 x.compareTo(z) > 0。
• 最后，实现者必须确定如果 x.compareTo(y) == 0 ，那么 sgn(x.compareTo(z)) == sgn(y.compareTo(z)) for all z。
• 强烈建议(但不是必需的) (x.compareTo(y) == 0) == (x.equals(y))。一般来说，任何实现可比接口并违反此条件的类都应该清楚地指出这一事实。推荐的提示是：“注意:该类的自然顺序与equals不一致。”
    不要因为这个规范的数学性质而犹豫不决。与 equals 规范一样，这个规范并不像看上去那么复杂。与将全局等价关系强加于所有对象的 equals 方法不同，compareTo不必跨不同类型的对象工作：当遇到不同类型的对象时，compareTo允许抛出ClassCastException。通常，它就是这样做的。规范确实允许类型间比较，这通常是在由被比较的对象实现的接口中定义的。
    正如违反 hashCode 规范的类可以破坏依赖哈希的其他类一样，违反 compareTo 规范的类也可以破坏依赖比较的其他类。依赖于比较的类包括已排序的集合 TreeSet 和TreeMap，以及包含搜索和排序算法的实用程序类 collections 和 array。
    让我们再看一遍规范的条款。第一个规定说，如果您将两个对象引用之间的比较的方向颠倒过来，就会发生预期的事情：如果第一个对象小于第二个对象，那么第二个对象必须大于第一个对象；如果第一个对象等于第二个对象，那么第二个对象一定等于第一个对象；如果第一个对象大于第二个对象，那么第二个对象一定小于第一个对象。
    第二条规定说，如果一个对象大于第二个对象，第二个对象大于第三个对象，那么第一个对象一定大于第三个对象。
    最后一条规定是，与任何其他对象相比，所有进行相等比较的对象必须产生相同的结果。
    这三个规定的一个结果是，由比较法施加的相等检验必须遵守由相等反推法施加的同样的限制：反身性（reflexivity）、对称性（symmetry）和传递性（transitivity）。因此，同样的警告也适用：除非您愿意放弃面向对象抽象的好处，否则无法在保留compareTo 契约的同时，用新的值组件扩展可实例化类。同样的方法也适用。如果您想向实现 Comparable 的类添加值组件，不要扩展它；编写一个不相关的类，其中包含第一个类的实例。然后提供一个返回所包含实例的“视图”方法。这使您可以自由地在包含类上实现任何您喜欢的 compareTo 方法，同时允许其客户机在需要时将包含类的实例作为包含类的实例来查看。
    compareTo 规范的最后一段(这是一个强烈的建议，而不是一个真正的要求)简单地指出，compareTo 方法施加的等式测试通常应该返回与 equals 方法相同的结果。如果遵守了这一规定，则 compareTo 方法所施加的顺序被称为与 equal 一致。如果违反了这个规则，则表示顺序与等号不一致。compareTo 方法强制执行与 equals 不一致的顺序的类仍然可以工作，但是包含该类元素的已排序集合可能不遵守适当集合接口(Collection, Set, 或 Map)的一般约定。这是因为这些接口的一般规范是根据 equals 方法定义的，但是排序后的集合使用 compareTo 施加的相等测试来代替equals。如果发生这种情况，并不是一场灾难，但这是需要注意的。
    例如，考虑 BigDecimal 类，它的 compareTo 方法与 equals 不一致。如果您创建一个空的 HashSet 实例，然后添加新的 BigDecimal(“1.0”) 和新的 BigDecimal(“1.00”)，那么集合将包含两个元素，因为使用 equals 方法比较添加到集合中的两个 BigDecimal 实例是不相等的。但是，如果使用 TreeSet 而不是 HashSet执行相同的过程，则 set 将只包含一个元素，因为使用 compareTo 方法比较时，两个 BigDecimal 实例是相等的。(详细信息请参阅BigDecimal文档)。
    编写 compareTo 方法类似于编写 equals 方法，但是有几个关键区别。因为Comparable 接口是参数化的，compareTo 方法是静态类型的，所以您不需要键入check 或转换它的参数。如果参数类型错误，调用甚至不会编译。如果参数为 null，调用应该抛出一个 NullPointer-Exception，当方法尝试访问它的成员时，它就会抛出这个异常。
    在 compareTo x方法中，比较字段的顺序而不是相等性。要比较对象引用字段，请递归调用 compareTo 方法。如果字段没有实现 Comparable 或需要非标准排序，则使用 Comparator。您可以编写自己的比较器或使用现有的比较器，如 item 10中的CaseInsensitiveString 的 compareTo 方法:

// Single-field Comparable with object reference field
public final class CaseInsensitiveString implements Comparable<CaseInsensitiveString> {
  public int compareTo(CaseInsensitiveString cis) {
    return String.CASE_INSENSITIVE_ORDER.compare(s, cis.s);
  }
... 
// Remainder omitted 
}

  注意，CaseInsensitiveString 实现了 Comparable<CaseInsensitiveString>。这意味着一个 CaseInsensitiveString 引用只能与另一个 CaseInsensitiveString 引用进行比较。这是在声明要实现 Comparable 类时要遵循的常规模式。
本书以前的版本建议 compareTo 方法使用关系运算符 < 和 > 比较整数原语字段，使用静态方法 Double.compare 和 Float.compare 比较浮点原语字段。在Java 7中，静态比较方法被添加到所有Java的装箱原始类中。在compareTo方法中使用关系运算符 < 和 > 冗长且容易出错，不再推荐使用。
  如果一个类有多个重要字段，比较它们的顺序是至关重要的。从最重要的领域开始，然后慢慢向下。如果比较结果不是0(代表相等)，那么就完成了;只返回结果。如果最重要的字段是相等的，比较下一个最重要的字段，以此类推，直到找到一个不相等的字段或比较最不重要的字段。下面是 item 11 中 PhoneNumber 类的 compareTo 方法，演示了这种技术:

public int compareTo(PhoneNumber pn) {
  int result = Short.compare(areaCode, pn.areaCode); 
  if (result == 0) {
    result = Short.compare(prefix, pn.prefix); 
    if (result == 0)
      result = Short.compare(lineNum, pn.lineNum); 
  }
  return result; 
}

  在Java 8中，接口 Comparator 配备了一组比较器构造方法，这使得 Comparator 的构造更加流畅。然后，可以根据 Comparable 接口的要求，使用这些比较器实现compareTo 方法。许多程序员更喜欢这种方法的简明性，尽管它的性能不太好：在我的机器上，对 PhoneNumber 实例数组排序的速度要慢10%左右。当使用这种方法时，请考虑使用Java的静态导入工具，这样您就可以通过静态比较器的简单名称引用静态比较器构造方法，以保持清晰和简洁。下面是使用这种方法的PhoneNumber的compareTo方法：

// Comparable with comparator construction methods
private static final Comparator<PhoneNumber> COMPARATOR = 
  comparingInt((PhoneNumber pn) -> pn.areaCode)
     .thenComparingInt(pn -> pn.prefix)
     .thenComparingInt(pn -> pn.lineNum);

public int compareTo(PhoneNumber pn) { 
    return COMPARATOR.compare(this, pn);
}

  这个实现使用两个比较器构造方法在类初始化时构建一个比较器。第一个是比较int。它是一个静态方法，接受一个键提取器函数，该函数将对象引用映射到int类型的键，并返回一个比较器，该比较器根据该键对实例排序。在前面的示例中，comparingInt使用lambda() 从 PhoneNumber 中提取区号，并返回一个 Comparator，该比较器根据电话区号排序电话号码。注意，lambda 显式地指定其输入参数的类型(PhoneNumber pn)。事实证明，在这种情况下，Java的类型推断并没有强大到足以自己找出类型，因此我们不得不帮助它来编译程序。
  如果两个电话号码有相同的区号，我们需要进一步细化比较，这正是第二个比较器构造方法，thenComparingInt 所做的。它是 Comparator 上的一个实例方法，它接受一个 int 键提取器函数，并返回一个比较器，该比较器首先应用原始比较器，然后使用提取的键断开连接。您可以根据自己的喜好对 thenComparingInt 进行尽可能多的调用，从而实现字典顺序。在上面的例子中，我们将两个对 thenComparingInt 的调用叠加在一起，得到一个顺序，其中次级键是前缀，第三个键是行号。注意，我们不必指定传递给对 thenComparingInt 的两个调用中的任何一个的键提取器函数的参数类型：Java的类型推断足够聪明，可以自己解决这个问题。
  Comparator 类有完整的构造方法。对于 long 和 double 原始类型 。int版本还可以用于更窄的整数类型，例如short，如我们的PhoneNumber示例。double 版本也可以用于 float。这提供了对所有Java数字基本类型的覆盖。
  对象引用类型也有比较器构造方法。名为 compare 的静态方法有两个重载。一个使用 key 并使用 key 的自然顺序。第二种方法同时使用 key 和比较器对提取的 key 进行比较。实例方法有三种重载，称为thenComparison。一个重载只需要一个比较器并使用它来提供二级顺序。第二次重载只使用密钥提取器，并使用密钥的自然顺序作为次要顺序。最后的重载需要一个密钥提取器和一个比较器来对提取的密钥进行使用。
  有时候，您可能会看到compareTo或compare方法，它们依赖于这样一个事实：如果第一个值小于第二个值，那么两个值之间的差为负：如果两个值相等，那么差为零;如果第一个值更大，那么差为正。举个例子：

// BROKEN difference-based comparator - violates transitivity!
static Comparator<Object> hashCodeOrder = new Comparator<>() {
  public int compare(Object o1, Object o2) { 
    return o1.hashCode() - o2.hashCode();
  } };

  不要使用这种技术。它充满了整数溢出和 IEEE 754 浮点运算伪码的危险。此外，生成的方法不太可能比使用本项目中描述的技术编写的方法快。使用静态比较方法：

// Comparator based on static compare method
static Comparator<Object> hashCodeOrder = new Comparator<>() {
  public int compare(Object o1, Object o2) {
    return Integer.compare(o1.hashCode(), o2.hashCode());
  } };

  或比较器构造方法:

// Comparator based on Comparator construction method
static Comparator<Object> hashCodeOrder = Comparator.comparingInt(o -> o.hashCode());

  总之，无论何时实现具有合理排序的值类，都应该让该类实现 Comparable 接口，以便能够轻松地对其实例进行排序、搜索，并在基于比较的集合中使用。在比较compareTo 方法实现中的字段值时，要避免使用 < 和 > 操作符。相反，使用装箱的基本类中的静态比较方法或比较器接口中的比较器构造方法。