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

Question

I am working on a project that is embarrassing me right now.

Provided List<TimeInterval> list, containing the elements of a class TimeIntervalthat 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));
    }

Intervals are created using the following:

TimeInterval tI = new TimeInterval(ld_dateValidFrom, ld_dateValidTo);

The intervals in 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

This 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 am using the JODA Time API , but since I am using it for the first time, I really do not know how to solve my problem. I already looked at the method overlap() / overlapWith(), but I still do not understand it.

Your help is much appreciated!

UPDATE - > <, .

---

, , , , .

, :

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

, , . -, .

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

, , TreeMap, LocalDate . , , .

TimeInterval s. , , , . , Integer. , 1.

, , 1 Integer. , -1.

endPoints, "", .

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

iterating over endPoints. , endPoints. (LocalDate) currStart Integer (curr - ).

. :

• curr > 0, TimeInterval currStart . newList.
• Integer curr.
• currStart.

.

: , . , . , , . , curr , , , , . "" , 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 + "]";
    }
}

, , . , , Joda Interval 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, ).

Answer 2

Half-Open

. Joda-Time "Half-Open" . , . , , , . , .

Half-Open , :

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

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

StackOverflow "", , .

Joda

Joda-Time Interval , . Interval overlap, overlaps (sic), abuts gap. , , overlap, ; .

, , DateTime, LocalDate ( , ). , LocalDate - , TimeInterval. , DateTime Joda-Time. 100%, , ( ), .

, + , 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 3

; , , .

However, this is possible using only dates. This is basically pseudo code, but you need to translate the point. I also added a notation so that you can find out what the intervals look like. There is also some confusion as to whether I should add 1 or subtract 1 for the overlap, so I made a mistake on the side of caution, pointing outward from the overlap (-1 for the start, +1 for the 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
}