Number of Periods in an Interval in Joda Time

Question

I'm trying to calculate the number of complete contiguous Periods in an Interval in Joda Time (where the Period is arbitrary but constant).

The simple solution I've come up with is a linear search using a while loop:

public static long periodsInAnInterval(Interval interval, Period period) {
    int periods = -1;
    DateTime marker = interval.getStart();
    while (marker.isBefore(interval.getEnd()) || marker.isEqual(interval.getEnd())) {
        marker = marker.plus(period);
        periods++;
    }
    return periods;
}

An O(n) solution is obviously pretty horrible, so can anyone think of a better way? I'm wondering whether some kind of binary search could be used...

Here's a test case: https://gist.github.com/Mahoney/9899832

Edit - remember a Period does not have a known number of seconds; Period.toStandardDuration() is just an approximation assuming years have 365 days, months have 30 days and days have 24 hours. (Actually a quick test reveals Period.toStandardDuration bombs out with an exception if you have years or months in the period.)

Edit 2 - I'm happy to assume that the first period begins at the start of the interval - otherwise I suspect the answer might vary depending on whether the remainder time were at the beginning, the end or both.

Answer 1

Here's my preferred solution: use average length of a period to form a best guess and then refine it. This seems the most efficient and elegant way to do it.

import com.google.common.base.Function;
import com.google.common.collect.ImmutableMap;
import org.joda.time.*;

import static com.google.common.collect.FluentIterable.from;
import static java.util.Arrays.asList;
import static org.joda.time.DurationFieldType.*;

public class PeriodArithmetic {

    public static long periodsInAnInterval(Interval interval, Period period) {
        int bestGuess = (int) (interval.toDurationMillis() / toAverageMillis(period));
        if (bestGuess < 0) return 0;
        if (startPlusScaledPeriodIsAfterEnd(interval, period, bestGuess + 1)) {
            return searchDownwards(interval, period, bestGuess);
        } else {
            return searchUpwards(interval, period, bestGuess);
        }
    }

    private static long searchDownwards(Interval interval, Period period, int currentGuess) {
        if (startPlusScaledPeriodIsAfterEnd(interval, period, currentGuess)) {
            return searchDownwards(interval, period, currentGuess - 1);
        } else {
            return currentGuess;
        }
    }

    private static long searchUpwards(Interval interval, Period period, int currentGuess) {
        if (!startPlusScaledPeriodIsAfterEnd(interval, period, currentGuess + 1)) {
            return searchUpwards(interval, period, currentGuess + 1);
        } else {
            return currentGuess;
        }
    }

    private static boolean startPlusScaledPeriodIsAfterEnd(Interval interval, Period period, int scalar) {
        return interval.getStart().plus(period.multipliedBy(scalar)).isAfter(interval.getEnd());
    }

    private static final long MILLIS_IN_DAY = Days.ONE.toStandardSeconds().getSeconds() * 1000L;
    private static final long MILLIS_IN_YEAR = Days.ONE.toStandardSeconds().getSeconds() * 365250L;

    private static final ImmutableMap<DurationFieldType, Long> averageLengthMillis
            = ImmutableMap.<DurationFieldType, Long>builder()
            .put(millis(),    1L)
            .put(seconds(),   1000L)
            .put(minutes(),   Minutes.ONE.toStandardSeconds().getSeconds() * 1000L)
            .put(hours(),     Hours.ONE.toStandardSeconds().getSeconds() * 1000L)
            .put(halfdays(),  MILLIS_IN_DAY / 2)
            .put(days(),      MILLIS_IN_DAY)
            .put(weeks(),     Weeks.ONE.toStandardSeconds().getSeconds() * 1000L)
            .put(months(),    MILLIS_IN_YEAR / 12)
            .put(years(),     MILLIS_IN_YEAR)
            .put(weekyears(), MILLIS_IN_YEAR)
            .put(centuries(), MILLIS_IN_YEAR * 100)
            .put(eras(),      Long.MAX_VALUE)
            .build();

    private static long toAverageMillis(Period period) {
        final Iterable<Long> milliValues = from(asList(period.getFieldTypes())).transform(toAverageMillisForFieldType(period));
        return total(milliValues);
    }

    private static Function<DurationFieldType, Long> toAverageMillisForFieldType(final Period period) {
        return new Function<DurationFieldType, Long>() {
            @Override
            public Long apply(DurationFieldType durationFieldType) {
                final Long averageDuration = averageLengthMillis.get(durationFieldType);
                return period.get(durationFieldType) * averageDuration;
            }
        };
    }

    private static long total(Iterable<Long> milliValues) {
        long acc = 0;
        for (Long milliValue : milliValues) {
            acc += milliValue;
        }
        return acc;
    }
}

Answer 2

I've put the beginnings of a binary search solution here: https://gist.github.com/Mahoney/9899936

It's much more complicated than the linear search; on the other hand it's roughly 100x faster at finding the number of months in 1,000 years, for instance.

It's also unfinished - more of an experiment than anything, so I'm sure there are untested edge cases (negative periods?).

Still keen to know if anyone has a more elegant solution (or just one I don't have to write, test & maintain!).