JAVA & Joda Time API: compare intervals, detect overlapping and generate new intervals

Question

I am working on a project that confuses me really bad right now.

Given is a List<TimeInterval> list that contains elements of the class TimeInterval, which looks like this:

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));
    }

The intervals are generated using the following:

TimeInterval tI = new TimeInterval(ld_dateValidFrom, ld_dateValidTo);

The intervals within the list may overlap:

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

This should result in:

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

It should NOT result in:

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

Generally speaking in numbers:

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

That should result in:

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

I'm using JODA Time API but since I'm using for the first time, I actually don't really have a clue how to solve my problem. I already had a look at the method overlap() / overlapWith() but I still don't get it.

Your help is much appreciated!

UPDATE I found something similar to my problem >here< but that doesn't help me for now.

---

I tried it over and over again, and even though it worked for the first intervals I tested, it doesn't actually work the way I wanted it to.

Here are the intervals I have been given:

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

This is the function I am using to generate the new intervals:

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;
}

This is what the output actually looks like:

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

And this is what the output SHOULD look like:

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

Since there is no overlap in the original intervals, I don't get why it produces stuff like

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

I've been trying to fix this all day long and I'm still not getting there :( Any more help is much appreciated!

Answer 1

Half-Open

I suggest you reconsider the terms of your goal. Joda-Time wisely uses the "Half-Open" approach to defining a span of time. The beginning is inclusive while the ending is exclusive. For example, a week starts an the beginning of the first day and runs up to, but not including, the first moment of the next week. Half-open proves to be quite helpful and natural way to handle spans of time, as discussed in other answers.

Using this Half-Open approach for your example, you do indeed want this result:

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

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

Search StackOverflow for "half-open" to find discussion and examples, such as this answer of mine.

Joda-Time Interval

Joda-Time has an excellent Interval class to represent a span of time defined by a pair of endpoints on the timeline. That Interval class offers overlap, overlaps (sic), abuts, and gap methods. Note in particular the overlap method that generates a new Interval when comparing two others; that may be key to your solution.

But unfortunately, that class only works with DateTime objects and not LocalDate (date-only, no time-of-day or time zone). Perhaps that lack of support for LocalDate is why you or your team invented that TimeInterval class. But I suggest rather that using that custom class, consider using DateTime objects with Joda-Time's classes. I'm not 100% certain that is better than rolling your own date-only interval class (I've been tempted to do that), but my gut tells me so.

To focus on days rather than day+time, on your DateTime objects call the withTimeAtStartOfDay method to adjust the time portion to the first moment of the day. That first moment is usually 00:00:00.000 but not necessarily due to Daylight Saving Time (DST) and possibly other anomalies. Just be careful and consistent with the time zone; perhaps use UTC throughout.

Here is some example code in Joda-Time 2.5 using the values suggested in the Question. In these particular lines, the call to withTimeAtStartOfDay may be unnecessary as Joda-Time defaults to first moment of day when no day-of-time is provided. But I suggest using those calls to withTimeAtStartOfDay as it makes your code self-documenting as to your intent. And it makes all your day-focused use of DateTime code consistent.

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() );

From there, apply the logic suggested in the other answers.