content: /* //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);
      }
  }
  