java - 间隔集合的数据结构

Question

我正在寻找一种基于 Java 的数据结构，它管理基于集合时间/日期的间隔(最好是 Joda 时间)，以便对于添加到集合中的每个间隔，数据结构返回添加的子间隔间隔，它还没有在数据结构中并合并间隔。

现在，就集合论而言，这很容易，即返回值将是“待添加”\“现有”，结果结构将是“现有”联合“待添加”。现在我当然可以使用离散点集来模拟日期/时间间隔，但这似乎并不是很有效。

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

只是为了澄清，这里是我正在寻找的一个例子。

• 现有:时间间隔的集合
• to to be added:应该加入集合的区间
• 返回值:应该添加的区间的子区间，但还没有在数据结构中
• result: 区间的集合，包括刚刚添加的区间

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

Answer 1

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

在我们的应用程序中，我们有一个范围聚合器类，用于计算范围的分配总和。 IE。基本输入是一组(可能重叠的)日期范围，并附有数字。输出是一组相应的非重叠范围，其中输入的数字在输入范围重叠的地方求和。它少于 100 行代码并使用 TreeMap。