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!

Oneidaoneil

This might help you with some of it.. – Fatuitous

Answer 1

Here is a suggested algorithm, based on the answer you have already found. First, you need to sort all the end points of the intervals.

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

This map's keys - which are sorted since this is a TreeMap - will be the LocalDate objects at the start and end of your intervals. They are mapped to a number that represents the number of end points at this date subtracted from the number of start points at this date.

Now traverse your list of TimeIntervals. For each one, for the start point, check whether it is already in the map. If so, add one to the Integer. If not, add it to the map with the value of 1.

For the end point of the same interval, if it exists in the map, subtract 1 from the Integer. If not, create it with the value of -1.

Once you finished filling endPoints, create a new list for the "broken up" intervals you will create.

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

Now start iterating over endPoints. If you had at least one interval in the original list, you'll have at least two points in endPoints. You take the first, and keep the key (LocalDate) in a variable currStart, and its associated Integer in another variable (curr or something).

Loop starting from the second element until the end. At each iteration:

• If curr > 0, create a new TimeInterval starting at currStart and ending at the current key date. Add it to newList.
• Add the Integer value to curr.
• Assign the key as your next currStart.

And so on until the end.

What happens here is this: ordering the dates makes sure you have no overlaps. Each new interval is guaranteed not to overlap with any new one since they have exclusive and sorted end points. The trick here is to find the spaces in the timeline which are not covered by any intervals at all. Those empty spaces are characterized by the fact that your curr is zero, as it means that all the intervals that started before the current point in time have also ended. All the other "spaces" between the end points are covered by at least one interval so there should be a corresponding new interval in your newList.

Here is an implementation, but please notice that I did not use Joda Time (I don't have it installed at the moment, and there is no particular feature here that requires it). I created my own rudimentary TimeInterval class:

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 + "]";
    }
}

The important thing is to add the accessor methods for the start and end to be able to perform the algorithm as I wrote it. In reality, you should probably use Joda's Interval or implement their ReadableInterval if you want to use their extended features.

Now for the method itself. For this to work with yours you'll have to change all Date to 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;
}

(Note that it would probably be more efficient to use a mutable Integer-like object rather than Integer here, but I opted for clarity).

Beauvais

Thanks for your help! I will have a look at this today, but it seems that it is not quiet doing what I'm looking for, which is (just to remind you): I1: 2014-01-01 -- 2014-01-05, I2: 2014-01-03 -- 2014-01-10 >>> RESULTS: 2014-01-01 -- 2014-01-02 / 2014-01-03 -- 2014-01-04 / 2014-01-05 -- 2014-01-10 – Oneidaoneil

That would be because your intervals are inclusive, or at least that's how you define them. You can adjust the algorithm for that by adding a day to the end-dates when you add them into the map, and subtracting when you create the new intervals again. Note that Joda Intervals are semi-open and it's a lot easier to work with them like that, so you should consider keeping your intervals semi-open for manipulation and only translating them back to closed end for display. – Beauvais

What do you mean by "mutable Integer-like" object? – Inflect

Answer 2

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.

Swage

Answer 3

I'm not fully up to speed on Joda; I'll need to read up on that if you want an overlap-specific solution.

However, this is possible using only the dates. This is mostly pseudocode, but should bring the point across. I've also added notation so you can tell what the intervals look like. There's also some confusion for me as to whether I should be adding 1 or subtracting 1 for an overlap, so I erred on the side of caution by pointing outward from the overlap (-1 for start, +1 for end).

TimeInterval a, b; //a and b are our two starting intervals
TimeInterval c = null;; //in case we have a third interval

if(a.start > b.start) { //move the earliest interval to a, latest to b, if necessary
    c = a;
    a = b;
    b = c;
    c = null;
}

if(b.start > a.start && b.start < a.end) { //case where b starts in the a interval
    if(b.end > a.end) { //b ends after a |AA||AB||BB|
        c = new TimeInterval(a.end + 1, b.end);//we need time interval c
        b.end = a.end;
        a.end = b.start - 1;
    }
    else if (b.end < a.end) { //b ends before a |AA||AB||AA|
        c = new TimeInterval(b.end + 1, a.end);//we need time interval c
        a.end = b.start - 1;
    }
    else { //b and a end at the same time, we don't need c |AA||AB|
        c = null;
        a.end = b.start - 1;
    }
}
else if(a.start == b.start) { //case where b starts same time as a
    if(b.end > a.end) { //b ends after a |AB||B|
        b.start = a.end + 1;
        a.end = a.end;
    }
    else if(b.end < a.end) { //b ends before a |AB||A|
        b.start = b.end + 1;
        b.end = a.end;
        a.end = b.start;
    }
    else { //b and a are the same |AB|
        b = null;
    }
}
else {
    //no overlap
}

Monto