间隔集合的数据结构

Question

间隔集合的数据结构

我正在寻找一个基于Java的数据结构,它管理基于收集时间/日期的间隔(最好是Joda时间),这样对于添加到集合的每个间隔,数据结构返回添加间隔的子间隔,还没有在数据结构中并巩固间隔.

现在就集合理论而言,这将是容易的,即返回值将是"待添加"\"现有的",并且所得到的结构将是"待加"的"现有"联合.当然,我可以使用一组离散点来模拟日期/时间间隔,但这似乎并不真正有效.

所以我正在寻找一个现有的数据结构,它已经使用间隔提供了开箱即用的这些设置操作.

只是为了澄清,这里是我正在寻找的例证.

现有:时间间隔的集合
要添加:应该添加到集合的间隔
返回值:应添加的区间的子区间(尚未包含在数据结构中)
结果:间隔的集合,包括刚刚添加的间隔

//       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           *********************************************
//       
//       ......
//

Run Code Online (Sandbox Code Playgroud)

Answer 1

Mar*_*o13 2

番石榴山脉在这里可能会派上用场。他们已经描述了范围/间隔，并使用一些实用方法来帮助创建数据结构来维护问题中描述的这些间隔。

_{事实上，它们比此处所需的区间强大得多，假设所有区间都是包含端点的闭区间。但我想没有理由在这里重新发明轮子。}

所需数据结构所需的操作是

计算间隔的并集。Range#span该方法已经提供了这一点
检测区间是否重叠或至少相连，或相互包围。这也是由Range#isConnected和Range#encloses方法提供的。
计算间隔之间的差异

最后一个不是由该类提供的Ranges- 原因很简单：两个范围之间的差异可能不是单个范围，而是零、一个或两个范围。但它可以轻松地使用实用函数构建，该函数返回一系列List范围，包含 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());
    }

}

Run Code Online (Sandbox Code Playgroud)

输出如下：

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:*********************************************

Run Code Online (Sandbox Code Playgroud)

我用 aLocalDateTime作为间隔边界，但任何Comparable对象都可以。ZERO LocalDateTime那里打印的星星数量只是自任意测试以来的分钟数。

笔记：

尽管此处介绍了您所描述的测试用例，并提供了所需的结果，但可以/应该引入其他测试。例如，添加空间隔，或添加恰好位于其他两个间隔边界的间隔......（这就是为什么这些被称为边界情况;-））

我还应该提到的是，这种实现不一定是最有效或最优雅的。我在那里介绍的方法normalize可能可以通过认真记录范围边界来避免，可能使用另一个答案中建议的NavigableSet或。NavigableMap如果性能至关重要，那么复杂的数据结构（例如区间树）也可能值得一看。但我认为给出的实现是合理的并且比较容易理解。

归档时间：	10 年，4 月前
查看次数：	325 次
最近记录：	10 年，4 月前