Find holes in Yoda-Time intervals

Question

I have a list of Joda-Time intervals

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

and another Joda-Time interval (search time interval), as in the image below.

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

Answer 1

Building the answer fge - the next version actually handles both cases (when the large interval is greater than the extreme values ​​of the intervals for which the search is performed + + the case when the large interval is actually less ... or less on the one hand)

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

Answer 2

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 3

Fge's answer seems correct, although I did not run this unverified code.

The term "space" seems to be the more common term for what you call "holes."

See this answer by Katya Christiansen , who makes good use of gap in the Interval class.

 Interval gapInterval = interval_X.gap( interval_Y ); // … Test for null to see whether or a gap exists. 

If there is a nonzero duration between them, you get a new Interval object to return. If intervals overlap or intersect, null is returned. Note that the Interval class also offers overlap and abuts methods if you are interested in these special conditions.

Of course, your collection of Interval objects must be sorted for this.