/* //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, 180, 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);
    }
}