Find holes in Joda-Time intervals

Question

I have list of Joda-Time intervals

List<Interval> intervals = new ArrayList<Interval>();

and another Joda-Time interval (search time interval), like on the picture below.

I need to write Java function that finds the holes in time and returns List<Interval> with the red intervals.

Answer 1

A quick look at the Interval API gives this (UNTESTED):

// SUPPOSED: the big interval is "bigInterval"; the list is "intervals"

// Intervals returned
List<Interval> ret = new ArrayList<>();


Interval gap, current, next;

// First, compute the gaps between the elements in the list

current = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
    next = intervals.get(i);
    gap = current.gap(next);
    if (gap != null)
        ret.add(gap);
    current = next;
}

// Now, compute the time difference between the starting time of the first interval
// and the starting time of the "big" interval; add it at the beginning

ReadableInstant start, end;

start = bigInterval.getStart();
end = intervals.get(0).getStart();

if (start.isBefore(end))
    ret.add(0, new Interval(start, end));

//
// finally, append the time difference between the ending time of the last interval
// and the ending time of the "big" interval

// next still contains the last interval
start = next.getEnd();
end = bigInterval.getEnd();
if (start.isBefore(end))
    ret.add(new Interval(start, end));

return ret;

Answer 2

Building up on fge's response - the following version actually handles both cases (when the big interval is larger than the extremes of the intervals being searched over + the case when the big interval is in fact smaller ... or smaller on one side)

you can see the full code along with the tests at https://github.com/erfangc/JodaTimeGapFinder.git

public class DateTimeGapFinder {

    /**
     * Finds gaps on the time line between a list of existing {@link Interval}
     * and a search {@link Interval}
     * 
     * @param existingIntervals
     * @param searchInterval
     * @return The list of gaps
     */
    public List<Interval> findGaps(List<Interval> existingIntervals, Interval searchInterval) {
        List<Interval> gaps = new ArrayList<Interval>();

        DateTime searchStart = searchInterval.getStart();
        DateTime searchEnd = searchInterval.getEnd();

        if (hasNoOverlap(existingIntervals, searchInterval, searchStart, searchEnd)) {
            gaps.add(searchInterval);
            return gaps;
        }

        // create a sub-list that excludes interval which does not overlap with
        // searchInterval
        List<Interval> subExistingList = removeNoneOverlappingIntervals(existingIntervals, searchInterval);
        DateTime subEarliestStart = subExistingList.get(0).getStart();
        DateTime subLatestStop = subExistingList.get(subExistingList.size() - 1).getEnd();

        // in case the searchInterval is wider than the union of the existing
        // include searchInterval.start => earliestExisting.start
        if (searchStart.isBefore(subEarliestStart)) {
            gaps.add(new Interval(searchStart, subEarliestStart));
        }

        // get all the gaps in the existing list
        gaps.addAll(getExistingIntervalGaps(subExistingList));

        // include latestExisting.stop => searchInterval.stop
        if (searchEnd.isAfter(subLatestStop)) {
            gaps.add(new Interval(subLatestStop, searchEnd));
        }
        return gaps;
    }

    private List<Interval> getExistingIntervalGaps(List<Interval> existingList) {
        List<Interval> gaps = new ArrayList<Interval>();
        Interval current = existingList.get(0);
        for (int i = 1; i < existingList.size(); i++) {
            Interval next = existingList.get(i);
            Interval gap = current.gap(next);
            if (gap != null)
                gaps.add(gap);
            current = next;
        }
        return gaps;
    }

    private List<Interval> removeNoneOverlappingIntervals(List<Interval> existingIntervals, Interval searchInterval) {
        List<Interval> subExistingList = new ArrayList<Interval>();
        for (Interval interval : existingIntervals) {
            if (interval.overlaps(searchInterval)) {
                subExistingList.add(interval);
            }
        }
        return subExistingList;
    }

    private boolean hasNoOverlap(List<Interval> existingIntervals, Interval searchInterval, DateTime searchStart, DateTime searchEnd) {
        DateTime earliestStart = existingIntervals.get(0).getStart();
        DateTime latestStop = existingIntervals.get(existingIntervals.size() - 1).getEnd();
        // return the entire search interval if it does not overlap with
        // existing at all
        if (searchEnd.isBefore(earliestStart) || searchStart.isAfter(latestStop)) {
            return true;
        }
        return false;
    }
}