【数据结构和算法】--RangeSet时间范围管理示例

一、问题

最近项目要求对一批时间范围进行管理，要求不能交叉。RangeSet是专门用于高效处理范围集合。

二、RangeSet实现原理

RangeSet表示一组不重叠的、非空的范围集合。RangeSet中的每个范围都是一个Range对象，Range对象表示一个具有起始和结束边界的范围。实现RangeSet接口，主要有两个实现类：ImmutableRangeSet和TreeRangeSet。ImmutableRangeSet是一个不可修改的RangeSet，而TreeRangeSet则是利用树的形式来实现，提供了高效的查询和插入操作。

2.1、RangeSet常用方法

complement()：返回RangeSet的补集视图。complement也是RangeSet类型,包含了不相连的、非空的区间。
subRangeSet(Range<C>)：返回RangeSet与给定Range的交集视图。这扩展了传统排序集合中的headSet、subSet和tailSet操作。
asRanges()：用Set<Range<C>>表现RangeSet，这样可以遍历其中的Range。
asSet(DiscreteDomain<C>)（仅ImmutableRangeSet支持）：用ImmutableSortedSet<C>表现RangeSet，以区间中所有元素的形式而不是区间本身的形式查看。（这个操作不支持DiscreteDomain 和RangeSet都没有上边界，或都没有下边界的情况）
contains(C)：RangeSet最基本的操作，判断RangeSet中是否有任何区间包含给定元素。
rangeContaining(C)：返回包含给定元素的区间；若没有这样的区间，则返回null。
encloses(Range<C>)：简单明了，判断RangeSet中是否有任何区间包括给定区间。
span()：返回包括RangeSet中所有区间的最小区间。
1
2
3
4
5
6
7
8

2.2、核心原理

RangeSet的实现原理主要基于一种称为“范围树”的数据结构。范围树是一种平衡树，其中每个节点都表示一个范围。树中的节点按照范围的起始位置进行排序，以便快速查找和定位特定的范围。
当向RangeSet中添加一个新的范围时，它会遍历范围树，找到与新范围相交或相邻的现有范围，并进行合并。合并后的范围会被插入到树中的适当位置，以保持树的平衡性。
对于查询操作，RangeSet可以利用范围树的结构进行快速查找。【例如，当查询一个元素是否包含在RangeSet中时，可以从树的根节点开始，沿着适当的分支向下遍历，直到找到一个包含该元素的范围或确定该元素不在RangeSet中。】

2.3、核心特性

自动合并范围：
当向RangeSet中添加一个新的范围时，它会自动与现有的范围进行合并。如果新的范围与某个现有范围相交或相邻，它们会被合并成一个更大的范围。这种自动合并的特性使得RangeSet能够保持范围的不重叠性，从而简化了范围集合的管理。
高效的查询操作：
RangeSet提供了丰富的查询操作，可以快速地判断一个元素是否在某个范围内、获取包含某个元素的范围等。这些查询操作都是基于对范围树的高效遍历实现的，能够在对数时间内给出结果。
灵活的范围操作：
除了基本的查询操作外，RangeSet还支持各种范围操作，如并集、交集、差集等。这些操作可以方便地对范围集合进行组合和变换，满足各种复杂的需求。

2.4、基本使用

  public void way1(){
        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..+∞))

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

三、具体应用

yyyy-MM-dd类型的时间，要求构建范围，新加入的时间范围不可重叠。

 /**
     新加入的时间，如果有重叠，返回false
     * @param start  2024-04-03
     * @param end
     */
    public Boolean addTimeToRange(String start,String end){
        Date startDate = TimeUtil.stringToDate(start,TimeUtil.D_FORMAT);
        Date endDate = TimeUtil.stringToDate(end,TimeUtil.D_FORMAT);
        long lStart = TimeUtil.dateToLong(startDate);
        long lEnd = TimeUtil.dateToLong(endDate);
        if(timeRangeValue.contains(lStart) || timeRangeValue.contains(lEnd)){
            return false;
        }


        timeRangeValue.add(Range.closed(lStart,lEnd));
        return true;
    }

    public Map<String,String> getTimeFromRange(){
        Map<String,String> reMap = new HashMap<>();
        Set<Range<Long>> ranges= timeRangeValue.asRanges();
        Iterator<Range<Long>> iterator = ranges.iterator();
        while (iterator.hasNext()){
            Range<Long> tempRange = iterator.next();
            Date dStart = TimeUtil.longToDate(tempRange.lowerEndpoint(),TimeUtil.D_FORMAT);
            Date dEnd = TimeUtil.longToDate(tempRange.upperEndpoint(),TimeUtil.D_FORMAT);
            reMap.put(TimeUtil.dateToString(dStart,TimeUtil.D_FORMAT),
                    TimeUtil.dateToString(dEnd,TimeUtil.D_FORMAT));
        }
        return reMap;
    }

    public static void main(String[] args) {
        RangeCreateService rangeCreateService = new RangeCreateService();
         rangeCreateService.addTimeToRange("2024-01-02","2024-01-24");
        rangeCreateService.addTimeToRange("2024-02-05","2024-02-24");
        rangeCreateService.addTimeToRange("2024-01-24","2024-02-02");
        Map<String,String> reMap = rangeCreateService.getTimeFromRange();
        System.out.println("timeRangeValue:"+ JSON.toJSONString(reMap));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41