Trail: Collections
Lesson: Interfaces

SortedSet 接口

SortedSet 是 Set，它按升序维护其元素，根据元素的自然顺序排序或根据 SortedSet 创建时提供的 Comparator。除了正常的 Set 操作外，SortedSet 接口还提供以下操作：

Range view 允许对有序集进行任意范围操作
Endpoints 返回有序集合中的第一个或最后一个元素
Comparator access 返回用于对集合进行排序的 Comparator(如果有)

接下来是 SortedSet 接口的代码。

public interface SortedSet<E> extends Set<E> {
    // Range-view
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);

    // Endpoints
    E first();
    E last();

    // Comparator access
    Comparator<? super E> comparator();
}

Set 运算

SortedSet 继承自 Set 的操作在有序集和普通集上的行为完全相同，但有两个例外：

iterator 操作返回的 Iterator 按顺序遍历有序集。
toArray 返回的数组按顺序包含有序集的元素。

虽然接口不保证它，但 Java 平台的 SortedSet 实现的 toString 方法按顺序返回一个包含有序集的所有元素的字符串。

标准构造函数

按照规范，所有通用 Collection 实现都提供了一个标准转换构造函数，它采用 Collection; SortedSet 实现也不例外。在 TreeSet 中，此构造函数创建一个实例，根据其自然顺序对其元素进行排序。这可能是一个错误。最好动态检查以查看指定的集合是否为 SortedSet 实例，如果是，则根据相同的标准对新的 TreeSet 进行排序(比较器或自然排序)。因为 TreeSet 采用了它所采用的方法，它还提供了一个构造函数，它接受 SortedSet 并返回一个新的 TreeSet，其中包含相同的元素排序依据达到同样的标准。请注意，它是参数的编译时类型，而不是其运行时类型，它确定调用这两个构造函数中的哪一个(以及是否保留了排序条件)。

按照规范，SortedSet 实现还提供了一个构造函数，它接受 Comparator 并返回根据指定的 Comparator 排序的空集。如果将 null 传递给此构造函数，它将返回一个集合，该集合根据其自然顺序对其元素进行排序。

范围视图操作

range-view 操作有点类似于 List 接口提供的操作，但有一个很大的区别。即使直接修改了后备有序集，有序集的范围视图仍然有效。这是可行的，因为有序集的范围视图的端点是元素空间中的绝对点，而不是后备集合中的特定元素，如列表的情况。有序集的 range-view 实际上只是该集合的任何部分位于元素空间的指定部分中的窗口。对 range-view 的更改将写回到后备有序集，反之亦然。因此，与列表上的 range-view 不同，可以长时间在有序集上使用 range-view。

有序集提供三个 range-view 操作。第一个 subSet 采用两个端点，类似 subList。端点不是索引，而是对象，必须与有序集合中的元素相比较，使用 Set 的 Comparator 或其元素的自然顺序，以 Set 用于排序本身的为准。与 subList 类似，范围是半开放的，包括其低端点但不包括高端点。

因此，以下代码行告诉你 "doorbell" 和 "pickle" 之间有多少单词，包括 "doorbell" 但不包括 "pickle"，包含在名为 dictionary 的 SortedSet 字符串中：

int count = dictionary.subSet("doorbell", "pickle").size();

以类似的方式，以下单行移除以字母 f 开头的所有元素。

dictionary.subSet("f", "g").clear();

类似的技巧可以用来打印一个表格，告诉你每个字母开头有多少个单词。

for (char ch = 'a'; ch <= 'z'; ) {
    String from = String.valueOf(ch++);
    String to = String.valueOf(ch);
    System.out.println(from + ": " + dictionary.subSet(from, to).size());
}

假设你要查看 closed interval (闭区间)，其中包含两个端点，而不是开区间。如果元素类型允许计算元素空间中给定值的后继，则请求 subSet 从 lowEndpoint 到 successor(highEndpoint)。虽然不是很明显，但 String 中自然顺序的字符串 s 的后继是 s + "\0" 也就是说，s 附加了 null 字符。

因此，下面的单行代码告诉你在字典中 "doorbell" 和 "pickle" 之间有多少个单词，包括 doorbell 和 pickle。

count = dictionary.subSet("doorbell", "pickle\0").size();

可以使用类似的技术来查看 open interval (开区间)，其不包含任何端点。从 lowEndpoint 到 highEndpoint 的开区间视图是从 successor(lowEndpoint) 到 highEndpoint 的半开区间。使用以下内容计算 "doorbell" 和 "pickle" 之间的单词数，不包括两者。

count = dictionary.subSet("doorbell\0", "pickle").size();

SortedSet 接口还包含两个 range-view 操作 headSet 和 tailSet，两者都采用单个 Object 参数。前者返回后备 SortedSet 的初始部分的视图，直到但不包括指定的对象。后者返回后备 SortedSet 的最后部分的视图，从指定对象开始并继续到后备 SortedSet 的末尾。因此，以下代码允许你将字典视为两个不相交的 volumes(a-m 和 n-z)。

SortedSet<String> volume1 = dictionary.headSet("n");
SortedSet<String> volume2 = dictionary.tailSet("n");

端点操作

SortedSet 接口包含返回有序集合中第一个和最后一个元素的操作，不出意外地称为 first 和 last。除了明显的用途之外，last 允许解决 SortedSet 接口中的缺陷。你想用 SortedSet 做的一件事就是进入 Set 的内部并向前或向后迭代。从内部向前很容易：只需获得一个 tailSet 并迭代它。不幸的是，没有简单的方法可以后退。

以下习惯用法获得的元素空间中的第一个小于指定对象 o 的元素。

Object predecessor = ss.headSet(o).last();

这是从有序集内部的一个点向后移动一个元素的好方法。它可以重复应用以向后迭代，但这是非常低效的，需要查找返回的每个元素。

Comparator 访问器

SortedSet 接口包含一个名为 comparator 的访问器方法，它返回用于对集合进行排序的 Comparator，如果该集合根据其元素的 natural ordering (自然排序) 进行排序，则返回 null 。提供此方法以便可以将排序的集合复制到具有相同排序的新排序集合中。它由之前描述的 SortedSet 构造函数使用。