java - Joda-Time 間隔で穴を見つける

Question

Joda-Time 間隔のリストがあります

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

下の図のように、別の Joda-Time 間隔 (検索時間間隔)。

List<Interval>時間内に穴を見つけて赤い間隔で返す Java 関数を作成する必要があります。

Answer 1

fge の応答に基づいて構築する - 次のバージョンは実際に両方のケースを処理します (大きな間隔が検索される間隔の極値よりも大きい場合 + 大きな間隔が実際に小さい場合 ... または片側で小さい場合)

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

Interval API をざっと見てみると、次のようになります (未テスト)。

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