一个用于存储区间集合的数据结构

Question

我正在寻找一个基于Java的数据结构，用于管理基于时间/日期的间隔集合(最好使用Joda Time)，以便于在向集合中添加每个间隔时，数据结构会返回该间隔的子间隔(s)，这些子间隔尚未在数据结构中汇总。根据集合理论，这很容易实现，即返回值为“待添加” \“已存在”，并且产生的结构为“已存在”的并集与“待添加”。当然，我也可以使用离散点集来模拟日期/时间间隔，但是这似乎不太有效。

因此，我正在寻找一个现有的数据结构，它已经提供了这些使用间隔的集合操作。

仅为澄清起见，这里是我正在寻找的内容说明：

- 已存在：时间间隔的集合 - 待添加：应添加到集合中的间隔 - 返回值：应添加的间隔的子间隔(s)尚未在数据结构中 - 结果：包括刚刚添加的间隔在内的间隔集合。

//       case 0
//       existing         *********************************************
//       to be added                      ********
//       return value                     --empty--  
//       result           *********************************************
//       
//       case 1
//       existing             *****************************************
//       to be added      ************
//       return value     ****
//       result           *********************************************
//       
//       case 2
//       existing               ***************************************
//       to be added      ****
//       return value     ****
//       result           ****  ***************************************
//       
//       case 3
//       existing         *****************************************
//       to be added                                       ************
//       return value                                              ****
//       result           *********************************************
//       
//       case 4
//       existing         ***************************************
//       to be added                                               ****
//       return value                                              ****
//       result           ***************************************  ****
//       
//       case 5
//       existing         *****************             ***************
//       to be added                           ****
//       return value                          ****
//       result           *****************    ****     ***************
//       
//       case 6
//       existing         *****************             ***************
//       to be added                    ********
//       return value                      *****
//       result           **********************        ***************
//       
//       case 7
//       existing         *****************             ***************
//       to be added                               ********
//       return value                              *****
//       result           *****************        ********************
//       
//       case 8
//       existing         *****************    ****     ***************
//       to be added                     *****************
//       return value                      ****    *****
//       result           *********************************************
//       
//       ......
//

- Ueli Hofstetter

---

第五个案例的结果是错误的，我是对的吗？ - Flown

你必须编写自己的ADT。我想不到任何有用的现有数据结构。 - Flown

Answer 1

至少在stdlib或commons中，并没有现成的结构可以实现这一点，但您可以使用NavigableMap (TreeMap)相对容易地实现一些东西。特别是像floorEntry()/ceilingEntry()和subMap()这样的方法对于此非常有用。

在我们的应用程序中，我们有一个范围聚合器类来计算范围内分配的总和。也就是说，基本输入是一组（可能重叠）的日期范围以及与它们相关联的数字。输出是相应的不重叠范围集，其中来自输入的数字在输入范围重叠时进行求和。它少于100行代码并使用TreeMap。

- user319799

---

你是使用间隔开始或结束日期作为TreeMap的键，还是使用某种组合键？此外，你是使用不可变的间隔表示还是修改它们？ - Ueli Hofstetter

我们只使用日期。在我们的情况下，映射是 { date -> sum_till_the_next_date }（最后一个条目映射到零）。当添加另一个范围时，我们重新计算其内容。这可能涉及插入新条目，如果我们尚未在映射中拥有这样的日期，以及将分配的值添加到 subMap() 中所有起始/结束日期的范围中。 - user319799

Answer 2

Guava范围可能在这里非常有用。它们已经描述了范围/间隔，并提供了一些实用方法来创建数据结构，以维护这些与问题描述相对应的区间。

实际上，它们比此处所需的区间更加强大，假设所有的区间都是包括端点的闭区间。但我想没有必要在这里重新发明轮子。

所需数据结构的操作如下：

- 计算区间并集。这已经由Range#span方法提供。 - 检测区间是否重叠，或者至少连接，或者互相包含。这也由Range#isConnected和Range#encloses方法提供。 - 计算区间差异。

最后一个不是由Ranges类提供的，其中一个简单的原因是：两个范围之间的差异可能不是一个区间，而是零、一个或两个区间。但是可以很容易地使用实用函数构建它，该工具函数返回包含0...2个元素的范围列表，具体取决于重叠配置。

以下是所需数据结构的一种可能实现：

import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

import com.google.common.collect.Range;

class Ranges
{
    // Computes the result of subtracting all the given ranges from
    // the given range.
    static <T extends Comparable<? super T>> List<Range<T>> subtractAll(
        Range<T> r, List<Range<T>> ranges)
    {
        List<Range<T>> currentList = Collections.singletonList(r);
        for (Range<T> other : ranges)
        {
            List<Range<T>> nextList = new ArrayList<Range<T>>();
            for (int i=0; i<currentList.size(); i++)
            {
                Range<T> current = currentList.get(i);
                List<Range<T>> differences = subtract(current, other);
                nextList.addAll(differences);
            }
            currentList = nextList;
        }
        return currentList;
    }

    // Computes the result of subtracting range r1 from
    // the given range r0. The result will be 
    // - an empty list if r1 encloses r0 
    // - an two-element list if r0 encloses r1
    // - a list containing r0 if the ranges are disjoint
    // - a single-element list otherwise 
    static <T extends Comparable<? super T>> List<Range<T>> subtract(
        Range<T> r0, Range<T> r1)
    {
        T min0 = r0.lowerEndpoint();
        T max0 = r0.upperEndpoint();
        T min1 = r1.lowerEndpoint();
        T max1 = r1.upperEndpoint();
        if (r0.encloses(r1))
        {
            List<Range<T>> result = 
                new ArrayList<Range<T>>();
            result.add(Range.closed(min0, min1));
            result.add(Range.closed(max1, max0));
            return result;
        }
        else if (r1.encloses(r0))
        {
            return Collections.emptyList();
        }
        else if (r0.isConnected(r1))
        {
            T min = null;
            T max = null;
            if (min0.compareTo(min1) < 0)
            {
                min = min0;
                max = min1;
            }
            else
            {
                min = max1;
                max = max0;
            }
            return Collections.singletonList(Range.closed(min, max));
        }
        return Collections.singletonList(r0);
    }

    // "Normalize" the given list of ranges: As long as two of
    // them are connected, they are replaced by their "span" (union)
    static <T extends Comparable<? super T>> List<Range<T>> normalize(
        List<Range<T>> ranges)
    {
        List<Range<T>> currentList = new ArrayList<Range<T>>(ranges);
        while (true)
        {
            List<Range<T>> toRemove = new ArrayList<Range<T>>();
            List<Range<T>> toAdd = new ArrayList<Range<T>>();
            for (int i=0; i<currentList.size(); i++)
            {
                for (int j=i+1; j<currentList.size(); j++)
                {
                    Range<T> r0 = currentList.get(i);
                    Range<T> r1 = currentList.get(j);
                    if (r0.isConnected(r1))
                    {
                        toRemove.add(r0);
                        toRemove.add(r1);
                        toAdd.add(r0.span(r1));
                    }
                }
            }
            if (toAdd.isEmpty())
            {
                break;
            }
            Set<Range<T>> set = new LinkedHashSet<Range<T>>();
            set.addAll(currentList);
            set.removeAll(toRemove);
            set.addAll(toAdd);
            currentList = new ArrayList<Range<T>>(set);
        }
        return currentList;
    }

}


class RangesContainer<T extends Comparable<? super T>>
{
    private List<Range<T>> ranges;

    RangesContainer()
    {
        ranges = new ArrayList<Range<T>>();
    }


    public List<Range<T>> add(Range<T> newRange)
    {
        if (ranges.stream().anyMatch(r -> r.encloses(newRange)))
        {
            return Collections.emptyList();
        }
        if (ranges.stream().noneMatch(r -> r.isConnected(newRange)))
        {
            ranges.add(newRange);
            ranges = Ranges.normalize(ranges);
            return Collections.singletonList(newRange);
        }
        List<Range<T>> differences = Ranges.subtractAll(newRange, ranges);
        ranges.add(newRange);
        ranges = Ranges.normalize(ranges);
        return differences;
    }


    List<Range<T>> getRanges()
    {
        return Collections.unmodifiableList(ranges);
    }

}

public class RangesTest
{
    static final LocalDateTime ZERO = 
        LocalDateTime.of(2015, 1, 1, 0, 0);

    public static void main(String[] args)
    {
        testCase0();
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
        testCase6();
        testCase7();
        testCase8();
    }


    private static void testCase0()
    {
        System.out.println("Test case 0");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(45));

        rc.add(existing0);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(16),
            ZERO.plusMinutes(24));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }

    private static void testCase1()
    {
        System.out.println("Test case 1");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(4),
            ZERO.plusMinutes(45));

        rc.add(existing0);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(12));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }

    private static void testCase2()
    {
        System.out.println("Test case 2");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(6),
            ZERO.plusMinutes(45));

        rc.add(existing0);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(4));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }

    private static void testCase3()
    {
        System.out.println("Test case 3");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(41));

        rc.add(existing0);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(33),
            ZERO.plusMinutes(45));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }


    private static void testCase4()
    {
        System.out.println("Test case 4");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(39));

        rc.add(existing0);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(41),
            ZERO.plusMinutes(45));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }

    private static void testCase5()
    {
        System.out.println("Test case 5");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(17));
        Range<LocalDateTime> existing1 = Range.closed(
            ZERO.plusMinutes(30),
            ZERO.plusMinutes(45));

        rc.add(existing0);
        rc.add(existing1);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(21),
            ZERO.plusMinutes(25));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }


    private static void testCase6()
    {
        System.out.println("Test case 6");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(17));
        Range<LocalDateTime> existing1 = Range.closed(
            ZERO.plusMinutes(30),
            ZERO.plusMinutes(45));

        rc.add(existing0);
        rc.add(existing1);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(14),
            ZERO.plusMinutes(22));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }


    private static void testCase7()
    {
        System.out.println("Test case 7");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(17));
        Range<LocalDateTime> existing1 = Range.closed(
            ZERO.plusMinutes(30),
            ZERO.plusMinutes(45));

        rc.add(existing0);
        rc.add(existing1);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(25),
            ZERO.plusMinutes(33));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }

    private static void testCase8()
    {
        System.out.println("Test case 8");

        RangesContainer<LocalDateTime> rc = 
            new RangesContainer<LocalDateTime>();

        Range<LocalDateTime> existing0 = Range.closed(
            ZERO.plusMinutes(0),
            ZERO.plusMinutes(17));
        Range<LocalDateTime> existing1 = Range.closed(
            ZERO.plusMinutes(21),
            ZERO.plusMinutes(25));
        Range<LocalDateTime> existing2 = Range.closed(
            ZERO.plusMinutes(30),
            ZERO.plusMinutes(45));

        rc.add(existing0);
        rc.add(existing1);
        rc.add(existing2);

        Range<LocalDateTime> added = Range.closed(
            ZERO.plusMinutes(15),
            ZERO.plusMinutes(31));

        System.out.println("Existing:");
        print(rc.getRanges());

        System.out.println("Adding:");
        print("", added);

        List<Range<LocalDateTime>> returnValue = rc.add(added);

        System.out.println("Returned:");
        print(returnValue);

        System.out.println("Result");
        print(rc.getRanges());

        System.out.println("\n");
    }


    static void print(List<Range<LocalDateTime>> list)
    {
        for (int i=0; i<list.size(); i++)
        {
            Range<LocalDateTime> range = list.get(i);
            String message = String.format("%3d", i);
            print(message, range);
        }
    }

    static void print(String message, LocalDateTime t0, LocalDateTime t1)
    {
        long minutes0 = ZERO.until(t0, ChronoUnit.MINUTES);
        long minutes1 = ZERO.until(t1, ChronoUnit.MINUTES);
        System.out.printf("%10s:", message);
        for (long i=0; i<minutes0; i++)
        {
            System.out.print(" ");
        }
        for (long i=minutes0; i<minutes1; i++)
        {
            System.out.print("*");
        }
        System.out.println();
    }

    static void print(String message, Range<LocalDateTime> r)
    {
        print(message, r.lowerEndpoint(), r.upperEndpoint());
    }

}

输出结果如下：

Test case 0
Existing:
     0:*********************************************
Adding:
      :                ********
Returned:
Result
     0:*********************************************


Test case 1
Existing:
     0:    *****************************************
Adding:
      :************
Returned:
     0:****
Result
     0:*********************************************


Test case 2
Existing:
     0:      ***************************************
Adding:
      :****
Returned:
     0:****
Result
     0:      ***************************************
     1:****


Test case 3
Existing:
     0:*****************************************
Adding:
      :                                 ************
Returned:
     0:                                         ****
Result
     0:*********************************************


Test case 4
Existing:
     0:***************************************
Adding:
      :                                         ****
Returned:
     0:                                         ****
Result
     0:***************************************
     1:                                         ****


Test case 5
Existing:
     0:*****************
     1:                              ***************
Adding:
      :                     ****
Returned:
     0:                     ****
Result
     0:*****************
     1:                              ***************
     2:                     ****


Test case 6
Existing:
     0:*****************
     1:                              ***************
Adding:
      :              ********
Returned:
     0:                 *****
Result
     0:                              ***************
     1:**********************


Test case 7
Existing:
     0:*****************
     1:                              ***************
Adding:
      :                         ********
Returned:
     0:                         *****
Result
     0:*****************
     1:                         ********************


Test case 8
Existing:
     0:*****************
     1:                     ****
     2:                              ***************
Adding:
      :               ****************
Returned:
     0:                 ****
     1:                         *****
Result
     0:*********************************************

我采用了一个LocalDateTime对象来表示时间间隔的边界，但是任何一个实现了Comparable接口的对象都可以。那里打印的星号数量仅仅是从任意一个ZEROLocalDateTime到现在的分钟数，用于测试。

注释：

虽然您描述的测试用例已经覆盖在此处，并且提供了期望的结果，但是可以/应该引入其他测试。例如，添加空间隔，或者添加恰好位于两个其他间隔边界的间隔……（这就是为什么它们被称为边界案例;-)）

我还应该提到，这个实现不一定是最高效或优雅的实现。我引入的normalize方法可能可以通过精心保管范围边界来避免使用，可能使用另一个答案中建议的NavigableSet或NavigableMap。如果性能至关重要，那么诸如区间树之类的复杂数据结构也值得一看。但我认为给出的实现是合理的，相对容易理解的。

- Marco13