在编程中，我们经常需要处理各种范围集合，例如时间范围、数字范围等。传统的集合类库往往只能处理离散的元素集合，对于范围集合的处理则显得力不从心。为了解决这个问题，Google的Guava库提供了一种强大的数据结构——RangeSet，专门用于高效处理范围集合。
提升编程效率的利器: 解析Google Guava库之集合篇Immutable（一）
提升编程效率的利器: 解析Google Guava库之集合篇Multimap（二）
提升编程效率的利器: 解析Google Guava库之集合篇BitMap（三）
提升编程效率的利器: 解析Google Guava库之集合篇Table二维映射（四)
一、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来解决时间范围管理、数字范围限制等问题，提高代码的可读性和维护性。
