提升编程效率的利器: 解析Google Guava库之集合篇RangeSet范围集合（五）
提升编程效率的利器: 解析Google Guava库之集合篇RangeSet范围集合（五）
在编程中，我们经常需要处理各种范围集合，例如时间范围、数字范围等。传统的集合类库往往只能处理离散的元素集合，对于范围集合的处理则显得力不从心。为了解决这个问题，Google的Guava库提供了一种强大的数据结构——RangeSet，专门用于高效处理范围集合。
一、RangeSet简介
RangeSet是Guava库中的一个接口，它表示一组不重叠的、非空的范围集合。RangeSet中的每个范围都是一个Range对象，Range对象表示一个具有起始和结束边界的范围。RangeSet提供了一种方便的方式来管理和操作这些范围。
RangeSet还提供了丰富的查询和操作功能。例如，可以使用contains©方法查询给定的元素是否在RangeSet里，rangeContaining©方法返回包含给定元素的Range（如果不存在则返回null），以及encloses(Range)方法用来判断给定的Range是否包含在RangeSet里面。此外，span()方法返回一个包含在这个RangeSet的所有Range的并集。
要实现RangeSet接口，可以选择使用它的两个主要实现类：ImmutableRangeSet和TreeRangeSet。其中，ImmutableRangeSet是一个不可修改的RangeSet，而TreeRangeSet则是利用树的形式来实现，提供了高效的查询和插入操作。
二、RangeSet的核心特性
- 自动合并范围： 当向RangeSet中添加一个新的范围时，它会自动与现有的范围进行合并。如果新的范围与某个现有范围相交或相邻，它们会被合并成一个更大的范围。这种自动合并的特性使得RangeSet能够保持范围的不重叠性，从而简化了范围集合的管理。
- 高效的查询操作： RangeSet提供了丰富的查询操作，可以快速地判断一个元素是否在某个范围内、获取包含某个元素的范围等。这些查询操作都是基于对范围树的高效遍历实现的，能够在对数时间内给出结果。
- 灵活的范围操作： 除了基本的查询操作外，RangeSet还支持各种范围操作，如并集、交集、差集等。这些操作可以方便地对范围集合进行组合和变换，满足各种复杂的需求。
三、RangeSet的实现原理
RangeSet的实现原理主要基于一种称为“范围树”的数据结构。范围树是一种平衡树，其中每个节点都表示一个范围。树中的节点按照范围的起始位置进行排序，以便快速查找和定位特定的范围。
当向RangeSet中添加一个新的范围时，它会遍历范围树，找到与新范围相交或相邻的现有范围，并进行合并。合并后的范围会被插入到树中的适当位置，以保持树的平衡性。这种合并和插入操作的时间复杂度都是对数级别的，因此RangeSet能够高效地处理大量的范围添加操作。
对于查询操作，RangeSet可以利用范围树的结构进行快速查找。例如，当查询一个元素是否包含在RangeSet中时，可以从树的根节点开始，沿着适当的分支向下遍历，直到找到一个包含该元素的范围或确定该元素不在RangeSet中。这种查询操作的时间复杂度也是对数级别的，因此RangeSet能够高效地处理大量的查询请求。
四、RangeSet的使用示例
使用 RangeSet 之前，我们得先了解一下 Guava 的Range 类，其实顾名思义就是表达区间范围，我们看一下它的 type 就明白了：
下面是一个使用RangeSet的简单示例，演示了如何创建一个RangeSet、向其中添加范围、并进行查询操作：
import com.google.common.collect.Range;
import com.google.common.collect.RangeSet;
import com.google.common.collect.TreeRangeSet;
public class TreeRangeSetDemo {
public static void main(String[] args) {
// 创建一个空的TreeRangeSet
RangeSet<Integer> rangeSet = TreeRangeSet.create();
// 向RangeSet中添加几个不连续的范围
rangeSet.add(Range.closed(1, 3)); // [1, 3]
rangeSet.add(Range.open(5, 8)); // (5, 8)
rangeSet.add(Range.closedOpen(10, 12));// [10, 12)
rangeSet.add(Range.greaterThan(15)); // (15, +∞)
// 打印当前RangeSet的内容
System.out.println(rangeSet); // [1..3](5..8)[10..12)(15..+∞)
// 查询某个范围是否包含在RangeSet中
System.out.println(rangeSet.contains(Range.closed(2, 3))); // true
System.out.println(rangeSet.contains(Range.open(6, 7))); // true
System.out.println(rangeSet.contains(Range.closed(11, 11))); // true
System.out.println(rangeSet.contains(Range.closed(4, 5))); // false
// 删除一个范围
rangeSet.remove(Range.open(5, 8));
System.out.println(rangeSet); // [1..3][10..12)(15..+∞)
// 获取与指定范围重叠的范围
RangeSet<Integer> overlappingRanges = rangeSet.subRangeSet(Range.atLeast(9));
System.out.println(overlappingRanges); // [10..12)(15..+∞)
// 获取指定范围的补集（这里仅展示与[0, 20]范围内的补集）
RangeSet<Integer> complement = rangeSet.complement().subRangeSet(Range.closed(0, 20));
System.out.println(complement); // (0..1)(3..5)(8..10)[12..15][15..20]
// 注意：由于complement()返回的是整个数域中不属于rangeSet的部分，
// 我们再次使用subRangeSet来限制补集的范围，以便更好地展示结果。
// 查询单个元素是否在RangeSet中
System.out.println(rangeSet.contains(2)); // true
System.out.println(rangeSet.contains(9)); // false
// 获取包含指定元素的范围
Range<Integer> rangeContaining11 = rangeSet.rangeContaining(11);
System.out.println(rangeContaining11); // [10..12)
Range<Integer> rangeContaining4 = rangeSet.rangeContaining(4);
System.out.println(rangeContaining4); // null，因为4不在rangeSet中
// 获取RangeSet的最小和最大元素（注意这不是一个Range，而是两个元素）
Integer minValue = rangeSet.asRanges().stream().map(Range::lowerEndpoint).min(Integer::compareTo).orElse(null);
Integer maxValue = rangeSet.asRanges().stream().map(Range::upperEndpoint).max(Integer::compareTo).orElse(null);
System.out.println("Min value: " + minValue); // Min value: 1
System.out.println("Max value: " + maxValue); // Max value: 2147483647 (Integer.MAX_VALUE，因为rangeSet包含(15..+∞))
}
}在这个例子中，我添加了一些不连续的整数范围，并进行了基本的操作，包括添加、删除范围、查询范围是否存在、获取范围的补集以及与指定范围重叠的范围等。我也演示了如何获取RangeSet中的最小和最大元素，尽管对于无限范围(15…+∞)，最大值实际上是Integer.MAX_VALUE，因为TreeRangeSet内部使用Integer来表示范围，并且它会将这个无限范围视为上界为Integer.MAX_VALUE的范围。
请注意，在实际应用中，处理无限范围时应该特别小心，因为整数是有界的，而TreeRangeSet的某些操作可能会受到这个限制的影响。
再来看下 循环遍历 和 使用encloses方法检查范围包含关系 的示例：
// 创建一个TreeRangeSet并添加一些不连续的范围
TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
rangeSet.add(Range.closed(1, 3));
rangeSet.add(Range.open(5, 8));
rangeSet.add(Range.closedOpen(10, 12));
rangeSet.add(Range.greaterThan(15));
// 使用encloses方法检查范围包含关系
boolean enclosesClosedRange = rangeSet.encloses(Range.closed(2, 3)); // true，因为[2,3]被[1,3]完全包含
boolean enclosesOpenRange = rangeSet.encloses(Range.open(6, 7)); // true，(6,7)被(5,8)完全包含
boolean enclosesSingletonRange = rangeSet.encloses(Range.singleton(11)); // true，11被[10,12)完全包含
boolean notEnclosesRange = rangeSet.encloses(Range.closed(4, 5)); // false，[4,5]不被任何范围完全包含
System.out.println("rangeSet.encloses(Range.closed(2, 3)): " + enclosesClosedRange);
System.out.println("rangeSet.encloses(Range.open(6, 7)): " + enclosesOpenRange);
System.out.println("rangeSet.encloses(Range.singleton(11)): " + enclosesSingletonRange);
System.out.println("rangeSet.encloses(Range.closed(4, 5)): " + notEnclosesRange);
// 遍历TreeRangeSet中的所有范围
System.out.println("Iterating over the ranges in the TreeRangeSet:");
Iterator<Range<Integer>> iterator = rangeSet.asRanges().iterator();
while (iterator.hasNext()) {
Range<Integer> range = iterator.next();
System.out.println(range);
}
// 使用增强的for循环遍历（更简洁）
System.out.println("Iterating over the ranges using enhanced for loop:");
for (Range<Integer> range : rangeSet.asRanges()) {
System.out.println(range);
}
} 五、总结
Guava的RangeSet提供了一种高效、灵活的方式来处理范围集合。它基于范围树的数据结构，实现了范围的自动合并和高效的查询操作。通过RangeSet，我们可以方便地管理和操作各种范围集合，满足各种复杂的需求。在实际应用中，我们可以利用RangeSet来解决时间范围管理、数字范围限制等问题，提高代码的可读性和维护性。
术因分享而日新，每获新知，喜溢心扉。 诚邀关注公众号 『
码到三十五』 ，获取更多技术资料。