JAVA和Joda Time API:比较间隔,检测重叠并生成新的间隔

Question

我正在制作一个令我困惑的项目.

给定是List<TimeInterval> list包含类的元素,TimeInterval如下所示:

public class TimeInterval {
    private static final Instant CONSTANT = new Instant(0);
    private final LocalDate validFrom;
    private final LocalDate validTo;


    public TimeInterval(LocalDate validFrom, LocalDate validTo) {
        this.validFrom = validFrom;
        this.validTo = validTo;
    }


    public boolean isValid() {
        try {
            return toInterval() != null;
        }
        catch (IllegalArgumentException e) {
            return false;
        }
    }


    public boolean overlapsWith(TimeInterval timeInterval) {
        return this.toInterval().overlaps(timeInterval.toInterval());
    }


    private Interval toInterval() throws IllegalArgumentException {
        return new Interval(validFrom.toDateTime(CONSTANT), validTo.toDateTime(CONSTANT));
    }

使用以下内容生成间隔:

TimeInterval tI = new TimeInterval(ld_dateValidFrom, ld_dateValidTo);

列表中的间隔可能重叠:

|--------------------|
         |-------------------|

这应该导致:

|-------||-----------||------|

它应该不导致:

|--------|-----------|-------|

一般来说,数字:

I1: 2014-01-01 - 2014-01-30
I2: 2014-01-07 - 2014-01-15

这应该导致:

I1: 2014-01-01 - 2014-01-06
I2: 2014-01-07 - 2014-01-15
I3: 2014-01-16 - 2014-01-30

我正在使用JODA Time API,但由于我第一次使用,我实际上并不知道如何解决我的问题.我已经看过这个方法,overlap() / overlapWith()但我仍然没有得到它.

非常感谢您的帮助!

更新 我发现类似于我的问题>这里<但这对我现在没有帮助.

---

我一遍又一遍地尝试过,即使它在我测试的第一个时间间隔内工作,它实际上并没有按照我想要的方式工作.

这是我给出的间隔:

2014-10-20 ---> 2014-10-26
2014-10-27 ---> 2014-11-02
2014-11-03 ---> 2014-11-09
2014-11-10 ---> 2014-11-16
2014-11-17 ---> 9999-12-31

这是我用来生成新间隔的函数:

private List<Interval> cleanIntervalList(List<Interval> sourceList) {
    TreeMap<DateTime, Integer> endPoints = new TreeMap<DateTime, Integer>();

    // Fill the treeMap from the TimeInterval list. For each start point,
    // increment the value in the map, and for each end point, decrement it.
    for (Interval interval : sourceList) {
        DateTime start = interval.getStart();
        if (endPoints.containsKey(start)) {
            endPoints.put(start, endPoints.get(start)+1);
        }
        else {
            endPoints.put(start, 1);
        }
        DateTime end = interval.getEnd();
        if (endPoints.containsKey(end)) {
            endPoints.put(end, endPoints.get(start)-1);
        }
        else {
            endPoints.put(end, 1);
        }
    }
    System.out.println(endPoints);

    int curr = 0;
    DateTime currStart = null;

    // Iterate over the (sorted) map. Note that the first iteration is used
    // merely to initialize curr and currStart to meaningful values, as no
    // interval precedes the first point.

    List<Interval> targetList = new LinkedList<Interval>();

    for (Entry<DateTime, Integer> e : endPoints.entrySet()) {
        if (curr > 0) {
            if (e.getKey().equals(endPoints.lastEntry().getKey())){
                targetList.add(new Interval(currStart, e.getKey()));
            }
            else {
                targetList.add(new Interval(currStart, e.getKey().minusDays(1)));
            }
        }
        curr += e.getValue();
        currStart = e.getKey();
    }
    System.out.println(targetList);
    return targetList;
}

这就是输出实际上的样子:

2014-10-20 ---> 2014-10-25
2014-10-26 ---> 2014-10-26
2014-10-27 ---> 2014-11-01
2014-11-02 ---> 2014-11-02
2014-11-03 ---> 2014-11-08
2014-11-09 ---> 2014-11-09
2014-11-10 ---> 2014-11-15
2014-11-16 ---> 2014-11-16
2014-11-17 ---> 9999-12-31

这就是输出应该是什么样子:

2014-10-20 ---> 2014-10-26
2014-10-27 ---> 2014-11-02
2014-11-03 ---> 2014-11-09
2014-11-10 ---> 2014-11-16
2014-11-17 ---> 9999-12-31

由于在原始间隔中没有重叠,我不明白为什么它会产生类似的东西

2014-10-26 ---> 2014-10-26
2014-11-02 ---> 2014-11-02
2014-11-09 ---> 2014-11-09
etc

我一直在努力解决这个问题,我仍然没有到达那里:(更多的帮助非常感谢!

Answer 1

半开

我建议你重新考虑你的目标条款.Joda-Time明智地使用"半开"方法来定义时间跨度.开头是包容性的,而结尾是独家的.例如,一周开始于第一天的开始并且一直运行到下一周的第一时刻,但不包括下一周的第一时刻.半开放被证明是处理时间跨度的非常有用和自然的方式,正如其他答案中所讨论的那样.

使用这种半开放式方法作为示例,您确实需要此结果:

|--------|-----------|-------|

I1: 2014-01-01 - 2014-01-07
I2: 2014-01-07 - 2014-01-16
I3: 2014-01-16 - 2014-01-30

搜索StackOverflow"半开"以查找讨论和示例,例如我的这个答案.

Joda-Time Interval

Joda-Time有一个很好的Interval类来表示时间轴上由一对端点定义的时间跨度.Interval类提供overlap,overlaps(原文如此)abuts和gap方法.特别注意在overlap比较其他两个时产生新间隔的方法; 这可能是您解决方案的关键.

但不幸的是,该类仅适用于DateTime对象而不是LocalDate(仅限日期,没有时间或时区).也许缺乏对LocalDate的支持是您或您的团队发明TimeInterval该类的原因.但我建议使用该自定义类,考虑将DateTime对象与Joda-Time的类一起使用.我不是百分之百肯定比滚动你自己的仅限日期的间隔课更好(我很想做到这一点),但我的直觉告诉了我.

要关注日期而不是日期+时间,请在DateTime对象上调用withTimeAtStartOfDay方法将时间部分调整为当天的第一时刻.第一个时刻通常00:00:00.000但不一定是由于夏令时(DST)和可能的其他异常.要小心并与时区保持一致; 也许整个使用UTC.

以下是使用问题中建议的值在Joda-Time 2.5中的一些示例代码.在这些特定的行中,调用withTimeAtStartOfDay可能是不必要的,因为Joda-Time默认为没有提供日期的第一时刻.但我建议使用这些调用,withTimeAtStartOfDay因为它会使您的代码自我记录您的意图.它使您所有以日常为中心的DateTime代码使用保持一致.

Interval i1 = new Interval( new DateTime( "2014-01-01", DateTimeZone.UTC ).withTimeAtStartOfDay(), new DateTime( "2014-01-30", DateTimeZone.UTC ).withTimeAtStartOfDay() );
Interval i2 = new Interval( new DateTime( "2014-01-07", DateTimeZone.UTC ).withTimeAtStartOfDay(), new DateTime( "2014-01-15", DateTimeZone.UTC ).withTimeAtStartOfDay() );

从那里,应用其他答案中建议的逻辑.

Answer 2

这是基于您已经找到的答案的建议算法。首先，您需要对区间的所有端点进行排序。

TreeMap<LocalDate,Integer> endPoints = new TreeMap<LocalDate,Integer>();

该地图的键（由于这是一个 TreeMap，因此已排序）将是间隔开始和结束时的 LocalDate 对象。它们被映射到一个数字，该数字表示从该日期的起点数中减去该日期的终点数。

现在遍历您的 s 列表TimeInterval。对于每个起点，检查它是否已在地图中。如果是，则将整数加一。如果没有，则将其添加到值为 1 的地图中。

对于同一区间的终点，如果地图中存在，则Integer减1。如果没有，则使用值-1 创建它。

完成填充后endPoints，为您将创建的“分解”间隔创建一个新列表。

List<TimeInterval> newList = new ArrayList<TimeInterval>();

现在开始迭代endPoints. 如果原始列表中至少有一个区间，则 中至少有两个点endPoints。您采用第一个，并将键（LocalDate）保存在一个变量中currStart，并将其关联的整数保存在另一个变量（curr或其他变量）中。

从第二个元素开始循环，直到结束。在每次迭代时：

• 如果，则创建一个从当前关键日期开始并结束的curr > 0新日期。将其添加到.TimeIntervalcurrStartnewList
• 将整数值添加到curr。
• 将该键指定为您的下一个currStart.

依此类推，直至结束。

这里发生的情况是这样的：对日期进行排序可确保没有重叠。每个新间隔都保证不会与任何新间隔重叠，因为它们具有独占且已排序的端点。这里的技巧是找到时间轴中根本没有被任何间隔覆盖的空间。这些空白空间的特点是 yourcurr为零，因为这意味着在当前时间点之前开始的所有间隔也都结束了。端点之间的所有其他“空间”至少被一个间隔覆盖，因此您的newList.

这是一个实现，但请注意，我没有使用 Joda Time（我目前没有安装它，并且这里没有需要它的特定功能）。我创建了自己的基础TimeInterval课程：

public class TimeInterval {
    private final Date validFrom;
    private final Date validTo;

    public TimeInterval(Date validFrom, Date validTo) {
        this.validFrom = validFrom;
        this.validTo = validTo;
    }

    public Date getStart() {
        return validFrom;
    }

    public Date getEnd() {
        return validTo;
    }

    @Override
    public String toString() {
        return "[" + validFrom + " - " + validTo + "]";
    }
}

重要的是添加开始和结束的访问器方法，以便能够执行我编写的算法。实际上，如果您想使用它们的扩展功能，您可能应该使用 JodaInterval或实现它们。ReadableInterval

现在来说说方法本身。为了使它与你的一起工作，你必须将其全部更改Date为LocalDate：

public static List<TimeInterval> breakOverlappingIntervals( List<TimeInterval> sourceList ) {

    TreeMap<Date,Integer> endPoints = new TreeMap<>();

    // Fill the treeMap from the TimeInterval list. For each start point, increment
    // the value in the map, and for each end point, decrement it.

    for ( TimeInterval interval : sourceList ) {
        Date start = interval.getStart();
        if ( endPoints.containsKey(start)) {
            endPoints.put(start, endPoints.get(start) + 1);
        } else {
            endPoints.put(start, 1);
        }
        Date end = interval.getEnd();
        if ( endPoints.containsKey(end)) {
            endPoints.put(end, endPoints.get(start) - 1);
        } else {
            endPoints.put(end, -1);
        }
    }

    int curr = 0;
    Date currStart = null;

    // Iterate over the (sorted) map. Note that the first iteration is used
    // merely to initialize curr and currStart to meaningful values, as no 
    // interval precedes the first point.

    List<TimeInterval> targetList = new ArrayList<>();
    for ( Map.Entry<Date,Integer> e : endPoints.entrySet() ) {
        if ( curr > 0 ) {
            targetList.add(new TimeInterval(currStart, e.getKey()));
        }
        curr += e.getValue();
        currStart = e.getKey();
    }
    return targetList;
}

（请注意，这里使用可变的类 Integer 对象而不是 Integer 可能会更有效，但为了清楚起见，我选择了）。