| /* //device/content/providers/pim/RecurrenceProcessor.java |
| ** |
| ** Copyright 2006, The Android Open Source Project |
| ** |
| ** Licensed under the Apache License, Version 2.0 (the "License"); |
| ** you may not use this file except in compliance with the License. |
| ** You may obtain a copy of the License at |
| ** |
| ** http://www.apache.org/licenses/LICENSE-2.0 |
| ** |
| ** Unless required by applicable law or agreed to in writing, software |
| ** distributed under the License is distributed on an "AS IS" BASIS, |
| ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| ** See the License for the specific language governing permissions and |
| ** limitations under the License. |
| */ |
| |
| package com.android.calendarcommon2; |
| |
| import android.text.format.Time; |
| import android.util.Log; |
| |
| import java.util.TreeSet; |
| |
| public class RecurrenceProcessor |
| { |
| // these are created once and reused. |
| private Time mIterator = new Time(Time.TIMEZONE_UTC); |
| private Time mUntil = new Time(Time.TIMEZONE_UTC); |
| private StringBuilder mStringBuilder = new StringBuilder(); |
| private Time mGenerated = new Time(Time.TIMEZONE_UTC); |
| private DaySet mDays = new DaySet(false); |
| // Give up after this many loops. This is roughly 1 second of expansion. |
| private static final int MAX_ALLOWED_ITERATIONS = 2000; |
| |
| public RecurrenceProcessor() |
| { |
| } |
| |
| private static final String TAG = "RecurrenceProcessor"; |
| |
| private static final boolean SPEW = false; |
| |
| /** |
| * Returns the time (millis since epoch) of the last occurrence, |
| * or -1 if the event repeats forever. If there are no occurrences |
| * (because the exrule or exdates cancel all the occurrences) and the |
| * event does not repeat forever, then 0 is returned. |
| * |
| * This computes a conservative estimate of the last occurrence. That is, |
| * the time of the actual last occurrence might be earlier than the time |
| * returned by this method. |
| * |
| * @param dtstart the time of the first occurrence |
| * @param recur the recurrence |
| * @return an estimate of the time (in UTC milliseconds) of the last |
| * occurrence, which may be greater than the actual last occurrence |
| * @throws DateException |
| */ |
| public long getLastOccurence(Time dtstart, |
| RecurrenceSet recur) throws DateException { |
| return getLastOccurence(dtstart, null /* no limit */, recur); |
| } |
| |
| /** |
| * Returns the time (millis since epoch) of the last occurrence, |
| * or -1 if the event repeats forever. If there are no occurrences |
| * (because the exrule or exdates cancel all the occurrences) and the |
| * event does not repeat forever, then 0 is returned. |
| * |
| * This computes a conservative estimate of the last occurrence. That is, |
| * the time of the actual last occurrence might be earlier than the time |
| * returned by this method. |
| * |
| * @param dtstart the time of the first occurrence |
| * @param maxtime the max possible time of the last occurrence. null means no limit |
| * @param recur the recurrence |
| * @return an estimate of the time (in UTC milliseconds) of the last |
| * occurrence, which may be greater than the actual last occurrence |
| * @throws DateException |
| */ |
| public long getLastOccurence(Time dtstart, Time maxtime, |
| RecurrenceSet recur) throws DateException { |
| long lastTime = -1; |
| boolean hasCount = false; |
| |
| // first see if there are any "until"s specified. if so, use the latest |
| // until / rdate. |
| if (recur.rrules != null) { |
| for (EventRecurrence rrule : recur.rrules) { |
| if (rrule.count != 0) { |
| hasCount = true; |
| } else if (rrule.until != null) { |
| // according to RFC 2445, until must be in UTC. |
| mIterator.parse(rrule.until); |
| long untilTime = mIterator.toMillis(false /* use isDst */); |
| if (untilTime > lastTime) { |
| lastTime = untilTime; |
| } |
| } |
| } |
| if (lastTime != -1 && recur.rdates != null) { |
| for (long dt : recur.rdates) { |
| if (dt > lastTime) { |
| lastTime = dt; |
| } |
| } |
| } |
| |
| // If there were only "until"s and no "count"s, then return the |
| // last "until" date or "rdate". |
| if (lastTime != -1 && !hasCount) { |
| return lastTime; |
| } |
| } else if (recur.rdates != null && |
| recur.exrules == null && recur.exdates == null) { |
| // if there are only rdates, we can just pick the last one. |
| for (long dt : recur.rdates) { |
| if (dt > lastTime) { |
| lastTime = dt; |
| } |
| } |
| return lastTime; |
| } |
| |
| // Expand the complete recurrence if there were any counts specified, |
| // or if there were rdates specified. |
| if (hasCount || recur.rdates != null || maxtime != null) { |
| // The expansion might not contain any dates if the exrule or |
| // exdates cancel all the generated dates. |
| long[] dates = expand(dtstart, recur, |
| dtstart.toMillis(false /* use isDst */) /* range start */, |
| (maxtime != null) ? |
| maxtime.toMillis(false /* use isDst */) : -1 /* range end */); |
| |
| // The expansion might not contain any dates if exrule or exdates |
| // cancel all the generated dates. |
| if (dates.length == 0) { |
| return 0; |
| } |
| return dates[dates.length - 1]; |
| } |
| return -1; |
| } |
| |
| /** |
| * a -- list of values |
| * N -- number of values to use in a |
| * v -- value to check for |
| */ |
| private static boolean listContains(int[] a, int N, int v) |
| { |
| for (int i=0; i<N; i++) { |
| if (a[i] == v) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * a -- list of values |
| * N -- number of values to use in a |
| * v -- value to check for |
| * max -- if a value in a is negative, add that negative value |
| * to max and compare that instead; this is how we deal with |
| * negative numbers being offsets from the end value |
| */ |
| private static boolean listContains(int[] a, int N, int v, int max) |
| { |
| for (int i=0; i<N; i++) { |
| int w = a[i]; |
| if (w > 0) { |
| if (w == v) { |
| return true; |
| } |
| } else { |
| max += w; // w is negative |
| if (max == v) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Filter out the ones for events whose BYxxx rule is for |
| * a period greater than or equal to the period of the FREQ. |
| * |
| * Returns 0 if the event should not be filtered out |
| * Returns something else (a rule number which is useful for debugging) |
| * if the event should not be returned |
| */ |
| private static int filter(EventRecurrence r, Time iterator) |
| { |
| boolean found; |
| int freq = r.freq; |
| |
| if (EventRecurrence.MONTHLY >= freq) { |
| // BYMONTH |
| if (r.bymonthCount > 0) { |
| found = listContains(r.bymonth, r.bymonthCount, |
| iterator.month + 1); |
| if (!found) { |
| return 1; |
| } |
| } |
| } |
| if (EventRecurrence.WEEKLY >= freq) { |
| // BYWEEK -- this is just a guess. I wonder how many events |
| // acutally use BYWEEKNO. |
| if (r.byweeknoCount > 0) { |
| found = listContains(r.byweekno, r.byweeknoCount, |
| iterator.getWeekNumber(), |
| iterator.getActualMaximum(Time.WEEK_NUM)); |
| if (!found) { |
| return 2; |
| } |
| } |
| } |
| if (EventRecurrence.DAILY >= freq) { |
| // BYYEARDAY |
| if (r.byyeardayCount > 0) { |
| found = listContains(r.byyearday, r.byyeardayCount, |
| iterator.yearDay, iterator.getActualMaximum(Time.YEAR_DAY)); |
| if (!found) { |
| return 3; |
| } |
| } |
| // BYMONTHDAY |
| if (r.bymonthdayCount > 0 ) { |
| found = listContains(r.bymonthday, r.bymonthdayCount, |
| iterator.monthDay, |
| iterator.getActualMaximum(Time.MONTH_DAY)); |
| if (!found) { |
| return 4; |
| } |
| } |
| // BYDAY -- when filtering, we ignore the number field, because it |
| // only is meaningful when creating more events. |
| byday: |
| if (r.bydayCount > 0) { |
| int a[] = r.byday; |
| int N = r.bydayCount; |
| int v = EventRecurrence.timeDay2Day(iterator.weekDay); |
| for (int i=0; i<N; i++) { |
| if (a[i] == v) { |
| break byday; |
| } |
| } |
| return 5; |
| } |
| } |
| if (EventRecurrence.HOURLY >= freq) { |
| // BYHOUR |
| found = listContains(r.byhour, r.byhourCount, |
| iterator.hour, |
| iterator.getActualMaximum(Time.HOUR)); |
| if (!found) { |
| return 6; |
| } |
| } |
| if (EventRecurrence.MINUTELY >= freq) { |
| // BYMINUTE |
| found = listContains(r.byminute, r.byminuteCount, |
| iterator.minute, |
| iterator.getActualMaximum(Time.MINUTE)); |
| if (!found) { |
| return 7; |
| } |
| } |
| if (EventRecurrence.SECONDLY >= freq) { |
| // BYSECOND |
| found = listContains(r.bysecond, r.bysecondCount, |
| iterator.second, |
| iterator.getActualMaximum(Time.SECOND)); |
| if (!found) { |
| return 8; |
| } |
| } |
| |
| if (r.bysetposCount > 0) { |
| bysetpos: |
| // BYSETPOS - we only handle rules like FREQ=MONTHLY;BYDAY=MO,TU,WE,TH,FR;BYSETPOS=-1 |
| if (freq == EventRecurrence.MONTHLY && r.bydayCount > 0) { |
| // Check for stuff like BYDAY=1TU |
| for (int i = r.bydayCount - 1; i >= 0; i--) { |
| if (r.bydayNum[i] != 0) { |
| if (Log.isLoggable(TAG, Log.VERBOSE)) { |
| Log.v(TAG, "BYSETPOS not supported with these rules: " + r); |
| } |
| break bysetpos; |
| } |
| } |
| if (!filterMonthlySetPos(r, iterator)) { |
| // Not allowed, filter it out. |
| return 9; |
| } |
| } else { |
| if (Log.isLoggable(TAG, Log.VERBOSE)) { |
| Log.v(TAG, "BYSETPOS not supported with these rules: " + r); |
| } |
| } |
| // BYSETPOS was defined but we don't know how to handle it. Do no filtering based |
| // on it. |
| } |
| |
| // if we got to here, we didn't filter it out |
| return 0; |
| } |
| |
| /** |
| * Filters out instances that don't match the BYSETPOS clause of a monthly recurrence rule. |
| * This is an awkward and inefficient way to go about it. |
| * |
| * @returns true if this instance should be kept |
| */ |
| private static boolean filterMonthlySetPos(EventRecurrence r, Time instance) { |
| /* |
| * Compute the day of the week for the first day of the month. "instance" has a |
| * day number and a DotW, so we compute the DotW of the 1st from that. Note DotW |
| * is 0-6, where 0=SUNDAY. |
| * |
| * The basic calculation is to take the instance's "day of the week" number, subtract |
| * (day of the month - 1) mod 7, and then make sure it's positive. We can simplify |
| * that with some algebra. |
| */ |
| int dotw = (instance.weekDay - instance.monthDay + 36) % 7; |
| |
| /* |
| * The byday[] values are specified as bits, so we can just OR them all |
| * together. |
| */ |
| int bydayMask = 0; |
| for (int i = 0; i < r.bydayCount; i++) { |
| bydayMask |= r.byday[i]; |
| } |
| |
| /* |
| * Generate a set according to the BYDAY rules. For each day of the month, determine |
| * if its day of the week is included. If so, append it to the day set. |
| */ |
| int maxDay = instance.getActualMaximum(Time.MONTH_DAY); |
| int daySet[] = new int[maxDay]; |
| int daySetLength = 0; |
| |
| for (int md = 1; md <= maxDay; md++) { |
| // For each month day, see if it's part of the set. (This makes some assumptions |
| // about the exact form of the DotW constants.) |
| int dayBit = EventRecurrence.SU << dotw; |
| if ((bydayMask & dayBit) != 0) { |
| daySet[daySetLength++] = md; |
| } |
| |
| dotw++; |
| if (dotw == 7) |
| dotw = 0; |
| } |
| |
| /* |
| * Now walk through the BYSETPOS list and see if the instance is equal to any of the |
| * specified daySet entries. |
| */ |
| for (int i = r.bysetposCount - 1; i >= 0; i--) { |
| int index = r.bysetpos[i]; |
| if (index > 0) { |
| if (index > daySetLength) { |
| continue; // out of range |
| } |
| if (daySet[index-1] == instance.monthDay) { |
| return true; |
| } |
| } else if (index < 0) { |
| if (daySetLength + index < 0) { |
| continue; // out of range |
| } |
| if (daySet[daySetLength + index] == instance.monthDay) { |
| return true; |
| } |
| } else { |
| // should have been caught by parser |
| throw new RuntimeException("invalid bysetpos value"); |
| } |
| } |
| |
| return false; |
| } |
| |
| |
| private static final int USE_ITERATOR = 0; |
| private static final int USE_BYLIST = 1; |
| |
| /** |
| * Return whether we should make this list from the BYxxx list or |
| * from the component of the iterator. |
| */ |
| int generateByList(int count, int freq, int byFreq) |
| { |
| if (byFreq >= freq) { |
| return USE_ITERATOR; |
| } else { |
| if (count == 0) { |
| return USE_ITERATOR; |
| } else { |
| return USE_BYLIST; |
| } |
| } |
| } |
| |
| private static boolean useBYX(int freq, int freqConstant, int count) |
| { |
| return freq > freqConstant && count > 0; |
| } |
| |
| public static class DaySet |
| { |
| public DaySet(boolean zulu) |
| { |
| mTime = new Time(Time.TIMEZONE_UTC); |
| } |
| |
| void setRecurrence(EventRecurrence r) |
| { |
| mYear = 0; |
| mMonth = -1; |
| mR = r; |
| } |
| |
| boolean get(Time iterator, int day) |
| { |
| int realYear = iterator.year; |
| int realMonth = iterator.month; |
| |
| Time t = null; |
| |
| if (SPEW) { |
| Log.i(TAG, "get called with iterator=" + iterator |
| + " " + iterator.month |
| + "/" + iterator.monthDay |
| + "/" + iterator.year + " day=" + day); |
| } |
| if (day < 1 || day > 28) { |
| // if might be past the end of the month, we need to normalize it |
| t = mTime; |
| t.set(day, realMonth, realYear); |
| unsafeNormalize(t); |
| realYear = t.year; |
| realMonth = t.month; |
| day = t.monthDay; |
| if (SPEW) { |
| Log.i(TAG, "normalized t=" + t + " " + t.month |
| + "/" + t.monthDay |
| + "/" + t.year); |
| } |
| } |
| |
| /* |
| if (true || SPEW) { |
| Log.i(TAG, "set t=" + t + " " + realMonth + "/" + day + "/" + realYear); |
| } |
| */ |
| if (realYear != mYear || realMonth != mMonth) { |
| if (t == null) { |
| t = mTime; |
| t.set(day, realMonth, realYear); |
| unsafeNormalize(t); |
| if (SPEW) { |
| Log.i(TAG, "set t=" + t + " " + t.month |
| + "/" + t.monthDay |
| + "/" + t.year |
| + " realMonth=" + realMonth + " mMonth=" + mMonth); |
| } |
| } |
| mYear = realYear; |
| mMonth = realMonth; |
| mDays = generateDaysList(t, mR); |
| if (SPEW) { |
| Log.i(TAG, "generated days list"); |
| } |
| } |
| return (mDays & (1<<day)) != 0; |
| } |
| |
| /** |
| * Fill in a bit set containing the days of the month on which this |
| * will occur. |
| * |
| * Only call this if the r.freq > DAILY. Otherwise, we should be |
| * processing the BYDAY, BYMONTHDAY, etc. as filters instead. |
| * |
| * monthOffset may be -1, 0 or 1 |
| */ |
| private static int generateDaysList(Time generated, EventRecurrence r) |
| { |
| int days = 0; |
| |
| int i, count, v; |
| int[] byday, bydayNum, bymonthday; |
| int j, lastDayThisMonth; |
| int first; // Time.SUNDAY, etc |
| int k; |
| |
| lastDayThisMonth = generated.getActualMaximum(Time.MONTH_DAY); |
| |
| // BYDAY |
| count = r.bydayCount; |
| if (count > 0) { |
| // calculate the day of week for the first of this month (first) |
| j = generated.monthDay; |
| while (j >= 8) { |
| j -= 7; |
| } |
| first = generated.weekDay; |
| if (first >= j) { |
| first = first - j + 1; |
| } else { |
| first = first - j + 8; |
| } |
| |
| // What to do if the event is weekly: |
| // This isn't ideal, but we'll generate a month's worth of events |
| // and the code that calls this will only use the ones that matter |
| // for the current week. |
| byday = r.byday; |
| bydayNum = r.bydayNum; |
| for (i=0; i<count; i++) { |
| v = bydayNum[i]; |
| j = EventRecurrence.day2TimeDay(byday[i]) - first + 1; |
| if (j <= 0) { |
| j += 7; |
| } |
| if (v == 0) { |
| // v is 0, each day in the month/week |
| for (; j<=lastDayThisMonth; j+=7) { |
| if (SPEW) Log.i(TAG, "setting " + j + " for rule " |
| + v + "/" + EventRecurrence.day2TimeDay(byday[i])); |
| days |= 1 << j; |
| } |
| } |
| else if (v > 0) { |
| // v is positive, count from the beginning of the month |
| // -1 b/c the first one should add 0 |
| j += 7*(v-1); |
| if (j <= lastDayThisMonth) { |
| if (SPEW) Log.i(TAG, "setting " + j + " for rule " |
| + v + "/" + EventRecurrence.day2TimeDay(byday[i])); |
| // if it's impossible, we drop it |
| days |= 1 << j; |
| } |
| } |
| else { |
| // v is negative, count from the end of the month |
| // find the last one |
| for (; j<=lastDayThisMonth; j+=7) { |
| } |
| // v is negative |
| // should do +1 b/c the last one should add 0, but we also |
| // skipped the j -= 7 b/c the loop to find the last one |
| // overshot by one week |
| j += 7*v; |
| if (j >= 1) { |
| if (SPEW) Log.i(TAG, "setting " + j + " for rule " |
| + v + "/" + EventRecurrence.day2TimeDay(byday[i])); |
| days |= 1 << j; |
| } |
| } |
| } |
| } |
| |
| // BYMONTHDAY |
| // Q: What happens if we have BYMONTHDAY and BYDAY? |
| // A: I didn't see it in the spec, so in lieu of that, we'll |
| // intersect the two. That seems reasonable to me. |
| if (r.freq > EventRecurrence.WEEKLY) { |
| count = r.bymonthdayCount; |
| if (count != 0) { |
| bymonthday = r.bymonthday; |
| if (r.bydayCount == 0) { |
| for (i=0; i<count; i++) { |
| v = bymonthday[i]; |
| if (v >= 0) { |
| days |= 1 << v; |
| } else { |
| j = lastDayThisMonth + v + 1; // v is negative |
| if (j >= 1 && j <= lastDayThisMonth) { |
| days |= 1 << j; |
| } |
| } |
| } |
| } else { |
| // This is O(lastDayThisMonth*count), which is really |
| // O(count) with a decent sized constant. |
| for (j=1; j<=lastDayThisMonth; j++) { |
| next_day : { |
| if ((days&(1<<j)) != 0) { |
| for (i=0; i<count; i++) { |
| if (bymonthday[i] == j) { |
| break next_day; |
| } |
| } |
| days &= ~(1<<j); |
| } |
| } |
| } |
| } |
| } |
| } |
| return days; |
| } |
| |
| private EventRecurrence mR; |
| private int mDays; |
| private Time mTime; |
| private int mYear; |
| private int mMonth; |
| } |
| |
| /** |
| * Expands the recurrence within the given range using the given dtstart |
| * value. Returns an array of longs where each element is a date in UTC |
| * milliseconds. The return value is never null. If there are no dates |
| * then an array of length zero is returned. |
| * |
| * @param dtstart a Time object representing the first occurrence |
| * @param recur the recurrence rules, including RRULE, RDATES, EXRULE, and |
| * EXDATES |
| * @param rangeStartMillis the beginning of the range to expand, in UTC |
| * milliseconds |
| * @param rangeEndMillis the non-inclusive end of the range to expand, in |
| * UTC milliseconds; use -1 for the entire range. |
| * @return an array of dates, each date is in UTC milliseconds |
| * @throws DateException |
| * @throws android.util.TimeFormatException if recur cannot be parsed |
| */ |
| public long[] expand(Time dtstart, |
| RecurrenceSet recur, |
| long rangeStartMillis, |
| long rangeEndMillis) throws DateException { |
| String timezone = dtstart.timezone; |
| mIterator.clear(timezone); |
| mGenerated.clear(timezone); |
| |
| // We don't need to clear the mUntil (and it wouldn't do any good to |
| // do so) because the "until" date string is specified in UTC and that |
| // sets the timezone in the mUntil Time object. |
| |
| mIterator.set(rangeStartMillis); |
| long rangeStartDateValue = normDateTimeComparisonValue(mIterator); |
| |
| long rangeEndDateValue; |
| if (rangeEndMillis != -1) { |
| mIterator.set(rangeEndMillis); |
| rangeEndDateValue = normDateTimeComparisonValue(mIterator); |
| } else { |
| rangeEndDateValue = Long.MAX_VALUE; |
| } |
| |
| TreeSet<Long> dtSet = new TreeSet<Long>(); |
| |
| if (recur.rrules != null) { |
| for (EventRecurrence rrule : recur.rrules) { |
| expand(dtstart, rrule, rangeStartDateValue, |
| rangeEndDateValue, true /* add */, dtSet); |
| } |
| } |
| if (recur.rdates != null) { |
| for (long dt : recur.rdates) { |
| // The dates are stored as milliseconds. We need to convert |
| // them to year/month/day values in the local timezone. |
| mIterator.set(dt); |
| long dtvalue = normDateTimeComparisonValue(mIterator); |
| dtSet.add(dtvalue); |
| } |
| } |
| if (recur.exrules != null) { |
| for (EventRecurrence exrule : recur.exrules) { |
| expand(dtstart, exrule, rangeStartDateValue, |
| rangeEndDateValue, false /* remove */, dtSet); |
| } |
| } |
| if (recur.exdates != null) { |
| for (long dt : recur.exdates) { |
| // The dates are stored as milliseconds. We need to convert |
| // them to year/month/day values in the local timezone. |
| mIterator.set(dt); |
| long dtvalue = normDateTimeComparisonValue(mIterator); |
| dtSet.remove(dtvalue); |
| } |
| } |
| if (dtSet.isEmpty()) { |
| // this can happen if the recurrence does not occur within the |
| // expansion window. |
| return new long[0]; |
| } |
| |
| // The values in dtSet are represented in a special form that is useful |
| // for fast comparisons and that is easy to generate from year/month/day |
| // values. We need to convert these to UTC milliseconds and also to |
| // ensure that the dates are valid. |
| int len = dtSet.size(); |
| long[] dates = new long[len]; |
| int i = 0; |
| for (Long val: dtSet) { |
| setTimeFromLongValue(mIterator, val); |
| dates[i++] = mIterator.toMillis(true /* ignore isDst */); |
| } |
| return dates; |
| } |
| |
| /** |
| * Run the recurrence algorithm. Processes events defined in the local |
| * timezone of the event. Return a list of iCalendar DATETIME |
| * strings containing the start date/times of the occurrences; the output |
| * times are defined in the local timezone of the event. |
| * |
| * If you want all of the events, pass Long.MAX_VALUE for rangeEndDateValue. If you pass |
| * Long.MAX_VALUE for rangeEnd, and the event doesn't have a COUNT or UNTIL field, |
| * you'll get a DateException. |
| * |
| * @param dtstart the dtstart date as defined in RFC2445. This |
| * {@link Time} should be in the timezone of the event. |
| * @param r the parsed recurrence, as defiend in RFC2445 |
| * @param rangeStartDateValue the first date-time you care about, inclusive |
| * @param rangeEndDateValue the last date-time you care about, not inclusive (so |
| * if you care about everything up through and including |
| * Dec 22 1995, set last to Dec 23, 1995 00:00:00 |
| * @param add Whether or not we should add to out, or remove from out. |
| * @param out the TreeSet you'd like to fill with the events |
| * @throws DateException |
| * @throws android.util.TimeFormatException if r cannot be parsed. |
| */ |
| public void expand(Time dtstart, |
| EventRecurrence r, |
| long rangeStartDateValue, |
| long rangeEndDateValue, |
| boolean add, |
| TreeSet<Long> out) throws DateException { |
| unsafeNormalize(dtstart); |
| long dtstartDateValue = normDateTimeComparisonValue(dtstart); |
| int count = 0; |
| |
| // add the dtstart instance to the recurrence, if within range. |
| // For example, if dtstart is Mar 1, 2010 and the range is Jan 1 - Apr 1, |
| // then add it here and increment count. If the range is earlier or later, |
| // then don't add it here. In that case, count will be incremented later |
| // inside the loop. It is important that count gets incremented exactly |
| // once here or in the loop for dtstart. |
| // |
| // NOTE: if DTSTART is not synchronized with the recurrence rule, the first instance |
| // we return will not fit the RRULE pattern. |
| if (add && dtstartDateValue >= rangeStartDateValue |
| && dtstartDateValue < rangeEndDateValue) { |
| out.add(dtstartDateValue); |
| ++count; |
| } |
| |
| Time iterator = mIterator; |
| Time until = mUntil; |
| StringBuilder sb = mStringBuilder; |
| Time generated = mGenerated; |
| DaySet days = mDays; |
| |
| try { |
| |
| days.setRecurrence(r); |
| if (rangeEndDateValue == Long.MAX_VALUE && r.until == null && r.count == 0) { |
| throw new DateException( |
| "No range end provided for a recurrence that has no UNTIL or COUNT."); |
| } |
| |
| // the top-level frequency |
| int freqField; |
| int freqAmount = r.interval; |
| int freq = r.freq; |
| switch (freq) |
| { |
| case EventRecurrence.SECONDLY: |
| freqField = Time.SECOND; |
| break; |
| case EventRecurrence.MINUTELY: |
| freqField = Time.MINUTE; |
| break; |
| case EventRecurrence.HOURLY: |
| freqField = Time.HOUR; |
| break; |
| case EventRecurrence.DAILY: |
| freqField = Time.MONTH_DAY; |
| break; |
| case EventRecurrence.WEEKLY: |
| freqField = Time.MONTH_DAY; |
| freqAmount = 7 * r.interval; |
| if (freqAmount <= 0) { |
| freqAmount = 7; |
| } |
| break; |
| case EventRecurrence.MONTHLY: |
| freqField = Time.MONTH; |
| break; |
| case EventRecurrence.YEARLY: |
| freqField = Time.YEAR; |
| break; |
| default: |
| throw new DateException("bad freq=" + freq); |
| } |
| if (freqAmount <= 0) { |
| freqAmount = 1; |
| } |
| |
| int bymonthCount = r.bymonthCount; |
| boolean usebymonth = useBYX(freq, EventRecurrence.MONTHLY, bymonthCount); |
| boolean useDays = freq >= EventRecurrence.WEEKLY && |
| (r.bydayCount > 0 || r.bymonthdayCount > 0); |
| int byhourCount = r.byhourCount; |
| boolean usebyhour = useBYX(freq, EventRecurrence.HOURLY, byhourCount); |
| int byminuteCount = r.byminuteCount; |
| boolean usebyminute = useBYX(freq, EventRecurrence.MINUTELY, byminuteCount); |
| int bysecondCount = r.bysecondCount; |
| boolean usebysecond = useBYX(freq, EventRecurrence.SECONDLY, bysecondCount); |
| |
| // initialize the iterator |
| iterator.set(dtstart); |
| if (freqField == Time.MONTH) { |
| if (useDays) { |
| // if it's monthly, and we're going to be generating |
| // days, set the iterator day field to 1 because sometimes |
| // we'll skip months if it's greater than 28. |
| // XXX Do we generate days for MONTHLY w/ BYHOUR? If so, |
| // we need to do this then too. |
| iterator.monthDay = 1; |
| } |
| } |
| |
| long untilDateValue; |
| if (r.until != null) { |
| // Ensure that the "until" date string is specified in UTC. |
| String untilStr = r.until; |
| // 15 is length of date-time without trailing Z e.g. "20090204T075959" |
| // A string such as 20090204 is a valid UNTIL (see RFC 2445) and the |
| // Z should not be added. |
| if (untilStr.length() == 15) { |
| untilStr = untilStr + 'Z'; |
| } |
| // The parse() method will set the timezone to UTC |
| until.parse(untilStr); |
| |
| // We need the "until" year/month/day values to be in the same |
| // timezone as all the generated dates so that we can compare them |
| // using the values returned by normDateTimeComparisonValue(). |
| until.switchTimezone(dtstart.timezone); |
| untilDateValue = normDateTimeComparisonValue(until); |
| } else { |
| untilDateValue = Long.MAX_VALUE; |
| } |
| |
| sb.ensureCapacity(15); |
| sb.setLength(15); // TODO: pay attention to whether or not the event |
| // is an all-day one. |
| |
| if (SPEW) { |
| Log.i(TAG, "expand called w/ rangeStart=" + rangeStartDateValue |
| + " rangeEnd=" + rangeEndDateValue); |
| } |
| |
| // go until the end of the range or we're done with this event |
| boolean eventEnded = false; |
| int failsafe = 0; // Avoid infinite loops |
| events: { |
| while (true) { |
| int monthIndex = 0; |
| if (failsafe++ > MAX_ALLOWED_ITERATIONS) { // Give up after about 1 second of processing |
| Log.w(TAG, "Recurrence processing stuck with r=" + r + " rangeStart=" |
| + rangeStartDateValue + " rangeEnd=" + rangeEndDateValue); |
| break; |
| } |
| |
| unsafeNormalize(iterator); |
| |
| int iteratorYear = iterator.year; |
| int iteratorMonth = iterator.month + 1; |
| int iteratorDay = iterator.monthDay; |
| int iteratorHour = iterator.hour; |
| int iteratorMinute = iterator.minute; |
| int iteratorSecond = iterator.second; |
| |
| // year is never expanded -- there is no BYYEAR |
| generated.set(iterator); |
| |
| if (SPEW) Log.i(TAG, "year=" + generated.year); |
| |
| do { // month |
| int month = usebymonth |
| ? r.bymonth[monthIndex] |
| : iteratorMonth; |
| month--; |
| if (SPEW) Log.i(TAG, " month=" + month); |
| |
| int dayIndex = 1; |
| int lastDayToExamine = 0; |
| |
| // Use this to handle weeks that overlap the end of the month. |
| // Keep the year and month that days is for, and generate it |
| // when needed in the loop |
| if (useDays) { |
| // Determine where to start and end, don't worry if this happens |
| // to be before dtstart or after the end, because that will be |
| // filtered in the inner loop |
| if (freq == EventRecurrence.WEEKLY) { |
| /* |
| * iterator.weekDay indicates the day of the week (0-6, SU-SA). |
| * Because dayIndex might start in the middle of a week, and we're |
| * interested in treating a week as a unit, we want to move |
| * backward to the start of the week. (This could make the |
| * dayIndex negative, which will be corrected by normalization |
| * later on.) |
| * |
| * The day that starts the week is determined by WKST, which |
| * defaults to MO. |
| * |
| * Example: dayIndex is Tuesday the 8th, and weeks start on |
| * Thursdays. Tuesday is day 2, Thursday is day 4, so we |
| * want to move back (2 - 4 + 7) % 7 = 5 days to the previous |
| * Thursday. If weeks started on Mondays, we would only |
| * need to move back (2 - 1 + 7) % 7 = 1 day. |
| */ |
| int weekStartAdj = (iterator.weekDay - |
| EventRecurrence.day2TimeDay(r.wkst) + 7) % 7; |
| dayIndex = iterator.monthDay - weekStartAdj; |
| lastDayToExamine = dayIndex + 6; |
| } else { |
| lastDayToExamine = generated |
| .getActualMaximum(Time.MONTH_DAY); |
| } |
| if (SPEW) Log.i(TAG, "dayIndex=" + dayIndex |
| + " lastDayToExamine=" + lastDayToExamine |
| + " days=" + days); |
| } |
| |
| do { // day |
| int day; |
| if (useDays) { |
| if (!days.get(iterator, dayIndex)) { |
| dayIndex++; |
| continue; |
| } else { |
| day = dayIndex; |
| } |
| } else { |
| day = iteratorDay; |
| } |
| if (SPEW) Log.i(TAG, " day=" + day); |
| |
| // hour |
| int hourIndex = 0; |
| do { |
| int hour = usebyhour |
| ? r.byhour[hourIndex] |
| : iteratorHour; |
| if (SPEW) Log.i(TAG, " hour=" + hour + " usebyhour=" + usebyhour); |
| |
| // minute |
| int minuteIndex = 0; |
| do { |
| int minute = usebyminute |
| ? r.byminute[minuteIndex] |
| : iteratorMinute; |
| if (SPEW) Log.i(TAG, " minute=" + minute); |
| |
| // second |
| int secondIndex = 0; |
| do { |
| int second = usebysecond |
| ? r.bysecond[secondIndex] |
| : iteratorSecond; |
| if (SPEW) Log.i(TAG, " second=" + second); |
| |
| // we do this here each time, because if we distribute it, we find the |
| // month advancing extra times, as we set the month to the 32nd, 33rd, etc. |
| // days. |
| generated.set(second, minute, hour, day, month, iteratorYear); |
| unsafeNormalize(generated); |
| |
| long genDateValue = normDateTimeComparisonValue(generated); |
| // sometimes events get generated (BYDAY, BYHOUR, etc.) that |
| // are before dtstart. Filter these. I believe this is correct, |
| // but Google Calendar doesn't seem to always do this. |
| if (genDateValue >= dtstartDateValue) { |
| // filter and then add |
| // TODO: we don't check for stop conditions (like |
| // passing the "end" date) unless the filter |
| // allows the event. Could stop sooner. |
| int filtered = filter(r, generated); |
| if (0 == filtered) { |
| |
| // increase the count as long |
| // as this isn't the same |
| // as the first instance |
| // specified by the DTSTART |
| // (for RRULEs -- additive). |
| // This condition must be the complement of the |
| // condition for incrementing count at the |
| // beginning of the method, so if we don't |
| // increment count there, we increment it here. |
| // For example, if add is set and dtstartDateValue |
| // is inside the start/end range, then it was added |
| // and count was incremented at the beginning. |
| // If dtstartDateValue is outside the range or add |
| // is not set, then we must increment count here. |
| if (!(dtstartDateValue == genDateValue |
| && add |
| && dtstartDateValue >= rangeStartDateValue |
| && dtstartDateValue < rangeEndDateValue)) { |
| ++count; |
| } |
| // one reason we can stop is that |
| // we're past the until date |
| if (genDateValue > untilDateValue) { |
| if (SPEW) { |
| Log.i(TAG, "stopping b/c until=" |
| + untilDateValue |
| + " generated=" |
| + genDateValue); |
| } |
| break events; |
| } |
| // or we're past rangeEnd |
| if (genDateValue >= rangeEndDateValue) { |
| if (SPEW) { |
| Log.i(TAG, "stopping b/c rangeEnd=" |
| + rangeEndDateValue |
| + " generated=" + generated); |
| } |
| break events; |
| } |
| |
| if (genDateValue >= rangeStartDateValue) { |
| if (SPEW) { |
| Log.i(TAG, "adding date=" + generated + " filtered=" + filtered); |
| } |
| if (add) { |
| out.add(genDateValue); |
| } else { |
| out.remove(genDateValue); |
| } |
| } |
| // another is that count is high enough |
| if (r.count > 0 && r.count == count) { |
| //Log.i(TAG, "stopping b/c count=" + count); |
| break events; |
| } |
| } |
| } |
| secondIndex++; |
| } while (usebysecond && secondIndex < bysecondCount); |
| minuteIndex++; |
| } while (usebyminute && minuteIndex < byminuteCount); |
| hourIndex++; |
| } while (usebyhour && hourIndex < byhourCount); |
| dayIndex++; |
| } while (useDays && dayIndex <= lastDayToExamine); |
| monthIndex++; |
| } while (usebymonth && monthIndex < bymonthCount); |
| |
| // Add freqAmount to freqField until we get another date that we want. |
| // We don't want to "generate" dates with the iterator. |
| // XXX: We do this for days, because there is a varying number of days |
| // per month |
| int oldDay = iterator.monthDay; |
| generated.set(iterator); // just using generated as a temporary. |
| int n = 1; |
| while (true) { |
| int value = freqAmount * n; |
| switch (freqField) { |
| case Time.SECOND: |
| iterator.second += value; |
| break; |
| case Time.MINUTE: |
| iterator.minute += value; |
| break; |
| case Time.HOUR: |
| iterator.hour += value; |
| break; |
| case Time.MONTH_DAY: |
| iterator.monthDay += value; |
| break; |
| case Time.MONTH: |
| iterator.month += value; |
| break; |
| case Time.YEAR: |
| iterator.year += value; |
| break; |
| case Time.WEEK_DAY: |
| iterator.monthDay += value; |
| break; |
| case Time.YEAR_DAY: |
| iterator.monthDay += value; |
| break; |
| default: |
| throw new RuntimeException("bad field=" + freqField); |
| } |
| |
| unsafeNormalize(iterator); |
| if (freqField != Time.YEAR && freqField != Time.MONTH) { |
| break; |
| } |
| if (iterator.monthDay == oldDay) { |
| break; |
| } |
| n++; |
| iterator.set(generated); |
| } |
| } |
| } |
| } |
| catch (DateException e) { |
| Log.w(TAG, "DateException with r=" + r + " rangeStart=" + rangeStartDateValue |
| + " rangeEnd=" + rangeEndDateValue); |
| throw e; |
| } |
| catch (RuntimeException t) { |
| Log.w(TAG, "RuntimeException with r=" + r + " rangeStart=" + rangeStartDateValue |
| + " rangeEnd=" + rangeEndDateValue); |
| throw t; |
| } |
| } |
| |
| /** |
| * Normalizes the date fields to give a valid date, but if the time falls |
| * in the invalid window during a transition out of Daylight Saving Time |
| * when time jumps forward an hour, then the "normalized" value will be |
| * invalid. |
| * <p> |
| * This method also computes the weekDay and yearDay fields. |
| * |
| * <p> |
| * This method does not modify the fields isDst, or gmtOff. |
| */ |
| static void unsafeNormalize(Time date) { |
| int second = date.second; |
| int minute = date.minute; |
| int hour = date.hour; |
| int monthDay = date.monthDay; |
| int month = date.month; |
| int year = date.year; |
| |
| int addMinutes = ((second < 0) ? (second - 59) : second) / 60; |
| second -= addMinutes * 60; |
| minute += addMinutes; |
| int addHours = ((minute < 0) ? (minute - 59) : minute) / 60; |
| minute -= addHours * 60; |
| hour += addHours; |
| int addDays = ((hour < 0) ? (hour - 23) : hour) / 24; |
| hour -= addDays * 24; |
| monthDay += addDays; |
| |
| // We want to make "monthDay" positive. We do this by subtracting one |
| // from the year and adding a year's worth of days to "monthDay" in |
| // the following loop while "monthDay" <= 0. |
| while (monthDay <= 0) { |
| // If month is after Feb, then add this year's length so that we |
| // include this year's leap day, if any. |
| // Otherwise (the month is Feb or earlier), add last year's length. |
| // Subtract one from the year in either case. This gives the same |
| // effective date but makes monthDay (the day of the month) much |
| // larger. Eventually (usually in one iteration) monthDay will |
| // be positive. |
| int days = month > 1 ? yearLength(year) : yearLength(year - 1); |
| monthDay += days; |
| year -= 1; |
| } |
| // At this point, monthDay >= 1. Normalize the month to the range [0,11]. |
| if (month < 0) { |
| int years = (month + 1) / 12 - 1; |
| year += years; |
| month -= 12 * years; |
| } else if (month >= 12) { |
| int years = month / 12; |
| year += years; |
| month -= 12 * years; |
| } |
| // At this point, month is in the range [0,11] and monthDay >= 1. |
| // Now loop until the monthDay is in the correct range for the month. |
| while (true) { |
| // On January, check if we can jump forward a whole year. |
| if (month == 0) { |
| int yearLength = yearLength(year); |
| if (monthDay > yearLength) { |
| year++; |
| monthDay -= yearLength; |
| } |
| } |
| int monthLength = monthLength(year, month); |
| if (monthDay > monthLength) { |
| monthDay -= monthLength; |
| month++; |
| if (month >= 12) { |
| month -= 12; |
| year++; |
| } |
| } else break; |
| } |
| // At this point, monthDay <= the length of the current month and is |
| // in the range [1,31]. |
| |
| date.second = second; |
| date.minute = minute; |
| date.hour = hour; |
| date.monthDay = monthDay; |
| date.month = month; |
| date.year = year; |
| date.weekDay = weekDay(year, month, monthDay); |
| date.yearDay = yearDay(year, month, monthDay); |
| } |
| |
| /** |
| * Returns true if the given year is a leap year. |
| * |
| * @param year the given year to test |
| * @return true if the given year is a leap year. |
| */ |
| static boolean isLeapYear(int year) { |
| return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0)); |
| } |
| |
| /** |
| * Returns the number of days in the given year. |
| * |
| * @param year the given year |
| * @return the number of days in the given year. |
| */ |
| static int yearLength(int year) { |
| return isLeapYear(year) ? 366 : 365; |
| } |
| |
| private static final int[] DAYS_PER_MONTH = { 31, 28, 31, 30, 31, 30, 31, |
| 31, 30, 31, 30, 31 }; |
| private static final int[] DAYS_IN_YEAR_PRECEDING_MONTH = { 0, 31, 59, 90, |
| 120, 151, 181, 212, 243, 273, 304, 334 }; |
| |
| /** |
| * Returns the number of days in the given month of the given year. |
| * |
| * @param year the given year. |
| * @param month the given month in the range [0,11] |
| * @return the number of days in the given month of the given year. |
| */ |
| static int monthLength(int year, int month) { |
| int n = DAYS_PER_MONTH[month]; |
| if (n != 28) { |
| return n; |
| } |
| return isLeapYear(year) ? 29 : 28; |
| } |
| |
| /** |
| * Computes the weekday, a number in the range [0,6] where Sunday=0, from |
| * the given year, month, and day. |
| * |
| * @param year the year |
| * @param month the 0-based month in the range [0,11] |
| * @param day the 1-based day of the month in the range [1,31] |
| * @return the weekday, a number in the range [0,6] where Sunday=0 |
| */ |
| static int weekDay(int year, int month, int day) { |
| if (month <= 1) { |
| month += 12; |
| year -= 1; |
| } |
| return (day + (13 * month - 14) / 5 + year + year/4 - year/100 + year/400) % 7; |
| } |
| |
| /** |
| * Computes the 0-based "year day", given the year, month, and day. |
| * |
| * @param year the year |
| * @param month the 0-based month in the range [0,11] |
| * @param day the 1-based day in the range [1,31] |
| * @return the 0-based "year day", the number of days into the year |
| */ |
| static int yearDay(int year, int month, int day) { |
| int yearDay = DAYS_IN_YEAR_PRECEDING_MONTH[month] + day - 1; |
| if (month >= 2 && isLeapYear(year)) { |
| yearDay += 1; |
| } |
| return yearDay; |
| } |
| |
| /** |
| * Converts a normalized Time value to a 64-bit long. The mapping of Time |
| * values to longs provides a total ordering on the Time values so that |
| * two Time values can be compared efficiently by comparing their 64-bit |
| * long values. This is faster than converting the Time values to UTC |
| * millliseconds. |
| * |
| * @param normalized a Time object whose date and time fields have been |
| * normalized |
| * @return a 64-bit long value that can be used for comparing and ordering |
| * dates and times represented by Time objects |
| */ |
| private static final long normDateTimeComparisonValue(Time normalized) { |
| // 37 bits for the year, 4 bits for the month, 5 bits for the monthDay, |
| // 5 bits for the hour, 6 bits for the minute, 6 bits for the second. |
| return ((long)normalized.year << 26) + (normalized.month << 22) |
| + (normalized.monthDay << 17) + (normalized.hour << 12) |
| + (normalized.minute << 6) + normalized.second; |
| } |
| |
| private static final void setTimeFromLongValue(Time date, long val) { |
| date.year = (int) (val >> 26); |
| date.month = (int) (val >> 22) & 0xf; |
| date.monthDay = (int) (val >> 17) & 0x1f; |
| date.hour = (int) (val >> 12) & 0x1f; |
| date.minute = (int) (val >> 6) & 0x3f; |
| date.second = (int) (val & 0x3f); |
| } |
| } |
