Home | History | Annotate | Download | only in calendarcommon2
      1 /* //device/content/providers/pim/RecurrenceProcessor.java
      2 **
      3 ** Copyright 2006, The Android Open Source Project
      4 **
      5 ** Licensed under the Apache License, Version 2.0 (the "License");
      6 ** you may not use this file except in compliance with the License.
      7 ** You may obtain a copy of the License at
      8 **
      9 **     http://www.apache.org/licenses/LICENSE-2.0
     10 **
     11 ** Unless required by applicable law or agreed to in writing, software
     12 ** distributed under the License is distributed on an "AS IS" BASIS,
     13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14 ** See the License for the specific language governing permissions and
     15 ** limitations under the License.
     16 */
     17 
     18 package com.android.calendarcommon2;
     19 
     20 import android.text.format.Time;
     21 import android.util.Log;
     22 
     23 import java.util.TreeSet;
     24 
     25 public class RecurrenceProcessor
     26 {
     27     // these are created once and reused.
     28     private Time mIterator = new Time(Time.TIMEZONE_UTC);
     29     private Time mUntil = new Time(Time.TIMEZONE_UTC);
     30     private StringBuilder mStringBuilder = new StringBuilder();
     31     private Time mGenerated = new Time(Time.TIMEZONE_UTC);
     32     private DaySet mDays = new DaySet(false);
     33     // Give up after this many loops.  This is roughly 1 second of expansion.
     34     private static final int MAX_ALLOWED_ITERATIONS = 2000;
     35 
     36     public RecurrenceProcessor()
     37     {
     38     }
     39 
     40     private static final String TAG = "RecurrenceProcessor";
     41 
     42     private static final boolean SPEW = false;
     43 
     44     /**
     45      * Returns the time (millis since epoch) of the last occurrence,
     46      * or -1 if the event repeats forever.  If there are no occurrences
     47      * (because the exrule or exdates cancel all the occurrences) and the
     48      * event does not repeat forever, then 0 is returned.
     49      *
     50      * This computes a conservative estimate of the last occurrence. That is,
     51      * the time of the actual last occurrence might be earlier than the time
     52      * returned by this method.
     53      *
     54      * @param dtstart the time of the first occurrence
     55      * @param recur the recurrence
     56      * @return an estimate of the time (in UTC milliseconds) of the last
     57      * occurrence, which may be greater than the actual last occurrence
     58      * @throws DateException
     59      */
     60     public long getLastOccurence(Time dtstart,
     61                                  RecurrenceSet recur) throws DateException {
     62         return getLastOccurence(dtstart, null /* no limit */, recur);
     63     }
     64 
     65     /**
     66      * Returns the time (millis since epoch) of the last occurrence,
     67      * or -1 if the event repeats forever.  If there are no occurrences
     68      * (because the exrule or exdates cancel all the occurrences) and the
     69      * event does not repeat forever, then 0 is returned.
     70      *
     71      * This computes a conservative estimate of the last occurrence. That is,
     72      * the time of the actual last occurrence might be earlier than the time
     73      * returned by this method.
     74      *
     75      * @param dtstart the time of the first occurrence
     76      * @param maxtime the max possible time of the last occurrence. null means no limit
     77      * @param recur the recurrence
     78      * @return an estimate of the time (in UTC milliseconds) of the last
     79      * occurrence, which may be greater than the actual last occurrence
     80      * @throws DateException
     81      */
     82     public long getLastOccurence(Time dtstart, Time maxtime,
     83                                  RecurrenceSet recur) throws DateException {
     84         long lastTime = -1;
     85         boolean hasCount = false;
     86 
     87         // first see if there are any "until"s specified.  if so, use the latest
     88         // until / rdate.
     89         if (recur.rrules != null) {
     90             for (EventRecurrence rrule : recur.rrules) {
     91                 if (rrule.count != 0) {
     92                     hasCount = true;
     93                 } else if (rrule.until != null) {
     94                     // according to RFC 2445, until must be in UTC.
     95                     mIterator.parse(rrule.until);
     96                     long untilTime = mIterator.toMillis(false /* use isDst */);
     97                     if (untilTime > lastTime) {
     98                         lastTime = untilTime;
     99                     }
    100                 }
    101             }
    102             if (lastTime != -1 && recur.rdates != null) {
    103                 for (long dt : recur.rdates) {
    104                     if (dt > lastTime) {
    105                         lastTime = dt;
    106                     }
    107                 }
    108             }
    109 
    110             // If there were only "until"s and no "count"s, then return the
    111             // last "until" date or "rdate".
    112             if (lastTime != -1 && !hasCount) {
    113                 return lastTime;
    114             }
    115         } else if (recur.rdates != null &&
    116                    recur.exrules == null && recur.exdates == null) {
    117             // if there are only rdates, we can just pick the last one.
    118             for (long dt : recur.rdates) {
    119                 if (dt > lastTime) {
    120                     lastTime = dt;
    121                 }
    122             }
    123             return lastTime;
    124         }
    125 
    126         // Expand the complete recurrence if there were any counts specified,
    127         // or if there were rdates specified.
    128         if (hasCount || recur.rdates != null || maxtime != null) {
    129             // The expansion might not contain any dates if the exrule or
    130             // exdates cancel all the generated dates.
    131             long[] dates = expand(dtstart, recur,
    132                     dtstart.toMillis(false /* use isDst */) /* range start */,
    133                     (maxtime != null) ?
    134                             maxtime.toMillis(false /* use isDst */) : -1 /* range end */);
    135 
    136             // The expansion might not contain any dates if exrule or exdates
    137             // cancel all the generated dates.
    138             if (dates.length == 0) {
    139                 return 0;
    140             }
    141             return dates[dates.length - 1];
    142         }
    143         return -1;
    144     }
    145 
    146     /**
    147      * a -- list of values
    148      * N -- number of values to use in a
    149      * v -- value to check for
    150      */
    151     private static boolean listContains(int[] a, int N, int v)
    152     {
    153         for (int i=0; i<N; i++) {
    154             if (a[i] == v) {
    155                 return true;
    156             }
    157         }
    158         return false;
    159     }
    160 
    161     /**
    162      * a -- list of values
    163      * N -- number of values to use in a
    164      * v -- value to check for
    165      * max -- if a value in a is negative, add that negative value
    166      *        to max and compare that instead; this is how we deal with
    167      *        negative numbers being offsets from the end value
    168      */
    169     private static boolean listContains(int[] a, int N, int v, int max)
    170     {
    171         for (int i=0; i<N; i++) {
    172             int w = a[i];
    173             if (w > 0) {
    174                 if (w == v) {
    175                     return true;
    176                 }
    177             } else {
    178                 max += w; // w is negative
    179                 if (max == v) {
    180                     return true;
    181                 }
    182             }
    183         }
    184         return false;
    185     }
    186 
    187     /**
    188      * Filter out the ones for events whose BYxxx rule is for
    189      * a period greater than or equal to the period of the FREQ.
    190      *
    191      * Returns 0 if the event should not be filtered out
    192      * Returns something else (a rule number which is useful for debugging)
    193      * if the event should not be returned
    194      */
    195     private static int filter(EventRecurrence r, Time iterator)
    196     {
    197         boolean found;
    198         int freq = r.freq;
    199 
    200         if (EventRecurrence.MONTHLY >= freq) {
    201             // BYMONTH
    202             if (r.bymonthCount > 0) {
    203                 found = listContains(r.bymonth, r.bymonthCount,
    204                         iterator.month + 1);
    205                 if (!found) {
    206                     return 1;
    207                 }
    208             }
    209         }
    210         if (EventRecurrence.WEEKLY >= freq) {
    211             // BYWEEK -- this is just a guess.  I wonder how many events
    212             // acutally use BYWEEKNO.
    213             if (r.byweeknoCount > 0) {
    214                 found = listContains(r.byweekno, r.byweeknoCount,
    215                                 iterator.getWeekNumber(),
    216                                 iterator.getActualMaximum(Time.WEEK_NUM));
    217                 if (!found) {
    218                     return 2;
    219                 }
    220             }
    221         }
    222         if (EventRecurrence.DAILY >= freq) {
    223             // BYYEARDAY
    224             if (r.byyeardayCount > 0) {
    225                 found = listContains(r.byyearday, r.byyeardayCount,
    226                                 iterator.yearDay, iterator.getActualMaximum(Time.YEAR_DAY));
    227                 if (!found) {
    228                     return 3;
    229                 }
    230             }
    231             // BYMONTHDAY
    232             if (r.bymonthdayCount > 0 ) {
    233                 found = listContains(r.bymonthday, r.bymonthdayCount,
    234                                 iterator.monthDay,
    235                                 iterator.getActualMaximum(Time.MONTH_DAY));
    236                 if (!found) {
    237                     return 4;
    238                 }
    239             }
    240             // BYDAY -- when filtering, we ignore the number field, because it
    241             // only is meaningful when creating more events.
    242 byday:
    243             if (r.bydayCount > 0) {
    244                 int a[] = r.byday;
    245                 int N = r.bydayCount;
    246                 int v = EventRecurrence.timeDay2Day(iterator.weekDay);
    247                 for (int i=0; i<N; i++) {
    248                     if (a[i] == v) {
    249                         break byday;
    250                     }
    251                 }
    252                 return 5;
    253             }
    254         }
    255         if (EventRecurrence.HOURLY >= freq) {
    256             // BYHOUR
    257             found = listContains(r.byhour, r.byhourCount,
    258                             iterator.hour,
    259                             iterator.getActualMaximum(Time.HOUR));
    260             if (!found) {
    261                 return 6;
    262             }
    263         }
    264         if (EventRecurrence.MINUTELY >= freq) {
    265             // BYMINUTE
    266             found = listContains(r.byminute, r.byminuteCount,
    267                             iterator.minute,
    268                             iterator.getActualMaximum(Time.MINUTE));
    269             if (!found) {
    270                 return 7;
    271             }
    272         }
    273         if (EventRecurrence.SECONDLY >= freq) {
    274             // BYSECOND
    275             found = listContains(r.bysecond, r.bysecondCount,
    276                             iterator.second,
    277                             iterator.getActualMaximum(Time.SECOND));
    278             if (!found) {
    279                 return 8;
    280             }
    281         }
    282 
    283         if (r.bysetposCount > 0) {
    284 bysetpos:
    285             // BYSETPOS - we only handle rules like FREQ=MONTHLY;BYDAY=MO,TU,WE,TH,FR;BYSETPOS=-1
    286             if (freq == EventRecurrence.MONTHLY && r.bydayCount > 0) {
    287                 // Check for stuff like BYDAY=1TU
    288                 for (int i = r.bydayCount - 1; i >= 0; i--) {
    289                     if (r.bydayNum[i] != 0) {
    290                         if (Log.isLoggable(TAG, Log.VERBOSE)) {
    291                             Log.v(TAG, "BYSETPOS not supported with these rules: " + r);
    292                         }
    293                         break bysetpos;
    294                     }
    295                 }
    296                 if (!filterMonthlySetPos(r, iterator)) {
    297                     // Not allowed, filter it out.
    298                     return 9;
    299                 }
    300             } else {
    301                 if (Log.isLoggable(TAG, Log.VERBOSE)) {
    302                     Log.v(TAG, "BYSETPOS not supported with these rules: " + r);
    303                 }
    304             }
    305             // BYSETPOS was defined but we don't know how to handle it.  Do no filtering based
    306             // on it.
    307         }
    308 
    309         // if we got to here, we didn't filter it out
    310         return 0;
    311     }
    312 
    313     /**
    314      * Filters out instances that don't match the BYSETPOS clause of a monthly recurrence rule.
    315      * This is an awkward and inefficient way to go about it.
    316      *
    317      * @returns true if this instance should be kept
    318      */
    319     private static boolean filterMonthlySetPos(EventRecurrence r, Time instance) {
    320         /*
    321          * Compute the day of the week for the first day of the month.  "instance" has a
    322          * day number and a DotW, so we compute the DotW of the 1st from that.  Note DotW
    323          * is 0-6, where 0=SUNDAY.
    324          *
    325          * The basic calculation is to take the instance's "day of the week" number, subtract
    326          * (day of the month - 1) mod 7, and then make sure it's positive.  We can simplify
    327          * that with some algebra.
    328          */
    329         int dotw = (instance.weekDay - instance.monthDay + 36) % 7;
    330 
    331         /*
    332          * The byday[] values are specified as bits, so we can just OR them all
    333          * together.
    334          */
    335         int bydayMask = 0;
    336         for (int i = 0; i < r.bydayCount; i++) {
    337             bydayMask |= r.byday[i];
    338         }
    339 
    340         /*
    341          * Generate a set according to the BYDAY rules.  For each day of the month, determine
    342          * if its day of the week is included.  If so, append it to the day set.
    343          */
    344         int maxDay = instance.getActualMaximum(Time.MONTH_DAY);
    345         int daySet[] = new int[maxDay];
    346         int daySetLength = 0;
    347 
    348         for (int md = 1; md <= maxDay; md++) {
    349             // For each month day, see if it's part of the set.  (This makes some assumptions
    350             // about the exact form of the DotW constants.)
    351             int dayBit = EventRecurrence.SU << dotw;
    352             if ((bydayMask & dayBit) != 0) {
    353                 daySet[daySetLength++] = md;
    354             }
    355 
    356             dotw++;
    357             if (dotw == 7)
    358                 dotw = 0;
    359         }
    360 
    361         /*
    362          * Now walk through the BYSETPOS list and see if the instance is equal to any of the
    363          * specified daySet entries.
    364          */
    365         for (int i = r.bysetposCount - 1; i >= 0; i--) {
    366             int index = r.bysetpos[i];
    367             if (index > 0) {
    368                 if (index > daySetLength) {
    369                     continue;  // out of range
    370                 }
    371                 if (daySet[index-1] == instance.monthDay) {
    372                     return true;
    373                 }
    374             } else if (index < 0) {
    375                 if (daySetLength + index < 0) {
    376                     continue;  // out of range
    377                 }
    378                 if (daySet[daySetLength + index] == instance.monthDay) {
    379                     return true;
    380                 }
    381             } else {
    382                 // should have been caught by parser
    383                 throw new RuntimeException("invalid bysetpos value");
    384             }
    385         }
    386 
    387         return false;
    388     }
    389 
    390 
    391     private static final int USE_ITERATOR = 0;
    392     private static final int USE_BYLIST = 1;
    393 
    394     /**
    395      * Return whether we should make this list from the BYxxx list or
    396      * from the component of the iterator.
    397      */
    398     int generateByList(int count, int freq, int byFreq)
    399     {
    400         if (byFreq >= freq) {
    401             return USE_ITERATOR;
    402         } else {
    403             if (count == 0) {
    404                 return USE_ITERATOR;
    405             } else {
    406                 return USE_BYLIST;
    407             }
    408         }
    409     }
    410 
    411     private static boolean useBYX(int freq, int freqConstant, int count)
    412     {
    413         return freq > freqConstant && count > 0;
    414     }
    415 
    416     public static class DaySet
    417     {
    418         public DaySet(boolean zulu)
    419         {
    420             mTime = new Time(Time.TIMEZONE_UTC);
    421         }
    422 
    423         void setRecurrence(EventRecurrence r)
    424         {
    425             mYear = 0;
    426             mMonth = -1;
    427             mR = r;
    428         }
    429 
    430         boolean get(Time iterator, int day)
    431         {
    432             int realYear = iterator.year;
    433             int realMonth = iterator.month;
    434 
    435             Time t = null;
    436 
    437             if (SPEW) {
    438                 Log.i(TAG, "get called with iterator=" + iterator
    439                         + " " + iterator.month
    440                         + "/" + iterator.monthDay
    441                         + "/" + iterator.year + " day=" + day);
    442             }
    443             if (day < 1 || day > 28) {
    444                 // if might be past the end of the month, we need to normalize it
    445                 t = mTime;
    446                 t.set(day, realMonth, realYear);
    447                 unsafeNormalize(t);
    448                 realYear = t.year;
    449                 realMonth = t.month;
    450                 day = t.monthDay;
    451                 if (SPEW) {
    452                     Log.i(TAG, "normalized t=" + t + " " + t.month
    453                             + "/" + t.monthDay
    454                             + "/" + t.year);
    455                 }
    456             }
    457 
    458             /*
    459             if (true || SPEW) {
    460                 Log.i(TAG, "set t=" + t + " " + realMonth + "/" + day + "/" + realYear);
    461             }
    462             */
    463             if (realYear != mYear || realMonth != mMonth) {
    464                 if (t == null) {
    465                     t = mTime;
    466                     t.set(day, realMonth, realYear);
    467                     unsafeNormalize(t);
    468                     if (SPEW) {
    469                         Log.i(TAG, "set t=" + t + " " + t.month
    470                                 + "/" + t.monthDay
    471                                 + "/" + t.year
    472                                 + " realMonth=" + realMonth + " mMonth=" + mMonth);
    473                     }
    474                 }
    475                 mYear = realYear;
    476                 mMonth = realMonth;
    477                 mDays = generateDaysList(t, mR);
    478                 if (SPEW) {
    479                     Log.i(TAG, "generated days list");
    480                 }
    481             }
    482             return (mDays & (1<<day)) != 0;
    483         }
    484 
    485         /**
    486          * Fill in a bit set containing the days of the month on which this
    487          * will occur.
    488          *
    489          * Only call this if the r.freq > DAILY.  Otherwise, we should be
    490          * processing the BYDAY, BYMONTHDAY, etc. as filters instead.
    491          *
    492          * monthOffset may be -1, 0 or 1
    493          */
    494         private static int generateDaysList(Time generated, EventRecurrence r)
    495         {
    496             int days = 0;
    497 
    498             int i, count, v;
    499             int[] byday, bydayNum, bymonthday;
    500             int j, lastDayThisMonth;
    501             int first; // Time.SUNDAY, etc
    502             int k;
    503 
    504             lastDayThisMonth = generated.getActualMaximum(Time.MONTH_DAY);
    505 
    506             // BYDAY
    507             count = r.bydayCount;
    508             if (count > 0) {
    509                 // calculate the day of week for the first of this month (first)
    510                 j = generated.monthDay;
    511                 while (j >= 8) {
    512                     j -= 7;
    513                 }
    514                 first = generated.weekDay;
    515                 if (first >= j) {
    516                     first = first - j + 1;
    517                 } else {
    518                     first = first - j + 8;
    519                 }
    520 
    521                 // What to do if the event is weekly:
    522                 // This isn't ideal, but we'll generate a month's worth of events
    523                 // and the code that calls this will only use the ones that matter
    524                 // for the current week.
    525                 byday = r.byday;
    526                 bydayNum = r.bydayNum;
    527                 for (i=0; i<count; i++) {
    528                     v = bydayNum[i];
    529                     j = EventRecurrence.day2TimeDay(byday[i]) - first + 1;
    530                     if (j <= 0) {
    531                         j += 7;
    532                     }
    533                     if (v == 0) {
    534                         // v is 0, each day in the month/week
    535                         for (; j<=lastDayThisMonth; j+=7) {
    536                             if (SPEW) Log.i(TAG, "setting " + j + " for rule "
    537                                     + v + "/" + EventRecurrence.day2TimeDay(byday[i]));
    538                             days |= 1 << j;
    539                         }
    540                     }
    541                     else if (v > 0) {
    542                         // v is positive, count from the beginning of the month
    543                         // -1 b/c the first one should add 0
    544                         j += 7*(v-1);
    545                         if (j <= lastDayThisMonth) {
    546                             if (SPEW) Log.i(TAG, "setting " + j + " for rule "
    547                                     + v + "/" + EventRecurrence.day2TimeDay(byday[i]));
    548                             // if it's impossible, we drop it
    549                             days |= 1 << j;
    550                         }
    551                     }
    552                     else {
    553                         // v is negative, count from the end of the month
    554                         // find the last one
    555                         for (; j<=lastDayThisMonth; j+=7) {
    556                         }
    557                         // v is negative
    558                         // should do +1 b/c the last one should add 0, but we also
    559                         // skipped the j -= 7 b/c the loop to find the last one
    560                         // overshot by one week
    561                         j += 7*v;
    562                         if (j >= 1) {
    563                             if (SPEW) Log.i(TAG, "setting " + j + " for rule "
    564                                     + v + "/" + EventRecurrence.day2TimeDay(byday[i]));
    565                             days |= 1 << j;
    566                         }
    567                     }
    568                 }
    569             }
    570 
    571             // BYMONTHDAY
    572             // Q: What happens if we have BYMONTHDAY and BYDAY?
    573             // A: I didn't see it in the spec, so in lieu of that, we'll
    574             // intersect the two.  That seems reasonable to me.
    575             if (r.freq > EventRecurrence.WEEKLY) {
    576                 count = r.bymonthdayCount;
    577                 if (count != 0) {
    578                     bymonthday = r.bymonthday;
    579                     if (r.bydayCount == 0) {
    580                         for (i=0; i<count; i++) {
    581                             v = bymonthday[i];
    582                             if (v >= 0) {
    583                                 days |= 1 << v;
    584                             } else {
    585                                 j = lastDayThisMonth + v + 1; // v is negative
    586                                 if (j >= 1 && j <= lastDayThisMonth) {
    587                                     days |= 1 << j;
    588                                 }
    589                             }
    590                         }
    591                     } else {
    592                         // This is O(lastDayThisMonth*count), which is really
    593                         // O(count) with a decent sized constant.
    594                         for (j=1; j<=lastDayThisMonth; j++) {
    595                             next_day : {
    596                                 if ((days&(1<<j)) != 0) {
    597                                     for (i=0; i<count; i++) {
    598                                         if (bymonthday[i] == j) {
    599                                             break next_day;
    600                                         }
    601                                     }
    602                                     days &= ~(1<<j);
    603                                 }
    604                             }
    605                         }
    606                     }
    607                 }
    608             }
    609             return days;
    610         }
    611 
    612         private EventRecurrence mR;
    613         private int mDays;
    614         private Time mTime;
    615         private int mYear;
    616         private int mMonth;
    617     }
    618 
    619     /**
    620      * Expands the recurrence within the given range using the given dtstart
    621      * value. Returns an array of longs where each element is a date in UTC
    622      * milliseconds. The return value is never null.  If there are no dates
    623      * then an array of length zero is returned.
    624      *
    625      * @param dtstart a Time object representing the first occurrence
    626      * @param recur the recurrence rules, including RRULE, RDATES, EXRULE, and
    627      * EXDATES
    628      * @param rangeStartMillis the beginning of the range to expand, in UTC
    629      * milliseconds
    630      * @param rangeEndMillis the non-inclusive end of the range to expand, in
    631      * UTC milliseconds; use -1 for the entire range.
    632      * @return an array of dates, each date is in UTC milliseconds
    633      * @throws DateException
    634      * @throws android.util.TimeFormatException if recur cannot be parsed
    635      */
    636     public long[] expand(Time dtstart,
    637             RecurrenceSet recur,
    638             long rangeStartMillis,
    639             long rangeEndMillis) throws DateException {
    640         String timezone = dtstart.timezone;
    641         mIterator.clear(timezone);
    642         mGenerated.clear(timezone);
    643 
    644         // We don't need to clear the mUntil (and it wouldn't do any good to
    645         // do so) because the "until" date string is specified in UTC and that
    646         // sets the timezone in the mUntil Time object.
    647 
    648         mIterator.set(rangeStartMillis);
    649         long rangeStartDateValue = normDateTimeComparisonValue(mIterator);
    650 
    651         long rangeEndDateValue;
    652         if (rangeEndMillis != -1) {
    653             mIterator.set(rangeEndMillis);
    654             rangeEndDateValue = normDateTimeComparisonValue(mIterator);
    655         } else {
    656             rangeEndDateValue = Long.MAX_VALUE;
    657         }
    658 
    659         TreeSet<Long> dtSet = new TreeSet<Long>();
    660 
    661         if (recur.rrules != null) {
    662             for (EventRecurrence rrule : recur.rrules) {
    663                 expand(dtstart, rrule, rangeStartDateValue,
    664                         rangeEndDateValue, true /* add */, dtSet);
    665             }
    666         }
    667         if (recur.rdates != null) {
    668             for (long dt : recur.rdates) {
    669                 // The dates are stored as milliseconds. We need to convert
    670                 // them to year/month/day values in the local timezone.
    671                 mIterator.set(dt);
    672                 long dtvalue = normDateTimeComparisonValue(mIterator);
    673                 dtSet.add(dtvalue);
    674             }
    675         }
    676         if (recur.exrules != null) {
    677             for (EventRecurrence exrule : recur.exrules) {
    678                 expand(dtstart, exrule, rangeStartDateValue,
    679                         rangeEndDateValue, false /* remove */, dtSet);
    680             }
    681         }
    682         if (recur.exdates != null) {
    683             for (long dt : recur.exdates) {
    684                 // The dates are stored as milliseconds. We need to convert
    685                 // them to year/month/day values in the local timezone.
    686                 mIterator.set(dt);
    687                 long dtvalue = normDateTimeComparisonValue(mIterator);
    688                 dtSet.remove(dtvalue);
    689             }
    690         }
    691         if (dtSet.isEmpty()) {
    692             // this can happen if the recurrence does not occur within the
    693             // expansion window.
    694             return new long[0];
    695         }
    696 
    697         // The values in dtSet are represented in a special form that is useful
    698         // for fast comparisons and that is easy to generate from year/month/day
    699         // values. We need to convert these to UTC milliseconds and also to
    700         // ensure that the dates are valid.
    701         int len = dtSet.size();
    702         long[] dates = new long[len];
    703         int i = 0;
    704         for (Long val: dtSet) {
    705             setTimeFromLongValue(mIterator, val);
    706             dates[i++] = mIterator.toMillis(true /* ignore isDst */);
    707         }
    708         return dates;
    709     }
    710 
    711     /**
    712      * Run the recurrence algorithm.  Processes events defined in the local
    713      * timezone of the event.  Return a list of iCalendar DATETIME
    714      * strings containing the start date/times of the occurrences; the output
    715      * times are defined in the local timezone of the event.
    716      *
    717      * If you want all of the events, pass Long.MAX_VALUE for rangeEndDateValue.  If you pass
    718      * Long.MAX_VALUE for rangeEnd, and the event doesn't have a COUNT or UNTIL field,
    719      * you'll get a DateException.
    720      *
    721      * @param dtstart the dtstart date as defined in RFC2445.  This
    722      * {@link Time} should be in the timezone of the event.
    723      * @param r the parsed recurrence, as defiend in RFC2445
    724      * @param rangeStartDateValue the first date-time you care about, inclusive
    725      * @param rangeEndDateValue the last date-time you care about, not inclusive (so
    726      *                  if you care about everything up through and including
    727      *                  Dec 22 1995, set last to Dec 23, 1995 00:00:00
    728      * @param add Whether or not we should add to out, or remove from out.
    729      * @param out the TreeSet you'd like to fill with the events
    730      * @throws DateException
    731      * @throws android.util.TimeFormatException if r cannot be parsed.
    732      */
    733     public void expand(Time dtstart,
    734             EventRecurrence r,
    735             long rangeStartDateValue,
    736             long rangeEndDateValue,
    737             boolean add,
    738             TreeSet<Long> out) throws DateException {
    739         unsafeNormalize(dtstart);
    740         long dtstartDateValue = normDateTimeComparisonValue(dtstart);
    741         int count = 0;
    742 
    743         // add the dtstart instance to the recurrence, if within range.
    744         // For example, if dtstart is Mar 1, 2010 and the range is Jan 1 - Apr 1,
    745         // then add it here and increment count.  If the range is earlier or later,
    746         // then don't add it here.  In that case, count will be incremented later
    747         // inside  the loop.  It is important that count gets incremented exactly
    748         // once here or in the loop for dtstart.
    749         //
    750         // NOTE: if DTSTART is not synchronized with the recurrence rule, the first instance
    751         //       we return will not fit the RRULE pattern.
    752         if (add && dtstartDateValue >= rangeStartDateValue
    753                 && dtstartDateValue < rangeEndDateValue) {
    754             out.add(dtstartDateValue);
    755             ++count;
    756         }
    757 
    758         Time iterator = mIterator;
    759         Time until = mUntil;
    760         StringBuilder sb = mStringBuilder;
    761         Time generated = mGenerated;
    762         DaySet days = mDays;
    763 
    764         try {
    765 
    766             days.setRecurrence(r);
    767             if (rangeEndDateValue == Long.MAX_VALUE && r.until == null && r.count == 0) {
    768                 throw new DateException(
    769                         "No range end provided for a recurrence that has no UNTIL or COUNT.");
    770             }
    771 
    772             // the top-level frequency
    773             int freqField;
    774             int freqAmount = r.interval;
    775             int freq = r.freq;
    776             switch (freq)
    777             {
    778                 case EventRecurrence.SECONDLY:
    779                     freqField = Time.SECOND;
    780                     break;
    781                 case EventRecurrence.MINUTELY:
    782                     freqField = Time.MINUTE;
    783                     break;
    784                 case EventRecurrence.HOURLY:
    785                     freqField = Time.HOUR;
    786                     break;
    787                 case EventRecurrence.DAILY:
    788                     freqField = Time.MONTH_DAY;
    789                     break;
    790                 case EventRecurrence.WEEKLY:
    791                     freqField = Time.MONTH_DAY;
    792                     freqAmount = 7 * r.interval;
    793                     if (freqAmount <= 0) {
    794                         freqAmount = 7;
    795                     }
    796                     break;
    797                 case EventRecurrence.MONTHLY:
    798                     freqField = Time.MONTH;
    799                     break;
    800                 case EventRecurrence.YEARLY:
    801                     freqField = Time.YEAR;
    802                     break;
    803                 default:
    804                     throw new DateException("bad freq=" + freq);
    805             }
    806             if (freqAmount <= 0) {
    807                 freqAmount = 1;
    808             }
    809 
    810             int bymonthCount = r.bymonthCount;
    811             boolean usebymonth = useBYX(freq, EventRecurrence.MONTHLY, bymonthCount);
    812             boolean useDays = freq >= EventRecurrence.WEEKLY &&
    813                                  (r.bydayCount > 0 || r.bymonthdayCount > 0);
    814             int byhourCount = r.byhourCount;
    815             boolean usebyhour = useBYX(freq, EventRecurrence.HOURLY, byhourCount);
    816             int byminuteCount = r.byminuteCount;
    817             boolean usebyminute = useBYX(freq, EventRecurrence.MINUTELY, byminuteCount);
    818             int bysecondCount = r.bysecondCount;
    819             boolean usebysecond = useBYX(freq, EventRecurrence.SECONDLY, bysecondCount);
    820 
    821             // initialize the iterator
    822             iterator.set(dtstart);
    823             if (freqField == Time.MONTH) {
    824                 if (useDays) {
    825                     // if it's monthly, and we're going to be generating
    826                     // days, set the iterator day field to 1 because sometimes
    827                     // we'll skip months if it's greater than 28.
    828                     // XXX Do we generate days for MONTHLY w/ BYHOUR?  If so,
    829                     // we need to do this then too.
    830                     iterator.monthDay = 1;
    831                 }
    832             }
    833 
    834             long untilDateValue;
    835             if (r.until != null) {
    836                 // Ensure that the "until" date string is specified in UTC.
    837                 String untilStr = r.until;
    838                 // 15 is length of date-time without trailing Z e.g. "20090204T075959"
    839                 // A string such as 20090204 is a valid UNTIL (see RFC 2445) and the
    840                 // Z should not be added.
    841                 if (untilStr.length() == 15) {
    842                     untilStr = untilStr + 'Z';
    843                 }
    844                 // The parse() method will set the timezone to UTC
    845                 until.parse(untilStr);
    846 
    847                 // We need the "until" year/month/day values to be in the same
    848                 // timezone as all the generated dates so that we can compare them
    849                 // using the values returned by normDateTimeComparisonValue().
    850                 until.switchTimezone(dtstart.timezone);
    851                 untilDateValue = normDateTimeComparisonValue(until);
    852             } else {
    853                 untilDateValue = Long.MAX_VALUE;
    854             }
    855 
    856             sb.ensureCapacity(15);
    857             sb.setLength(15); // TODO: pay attention to whether or not the event
    858             // is an all-day one.
    859 
    860             if (SPEW) {
    861                 Log.i(TAG, "expand called w/ rangeStart=" + rangeStartDateValue
    862                         + " rangeEnd=" + rangeEndDateValue);
    863             }
    864 
    865             // go until the end of the range or we're done with this event
    866             boolean eventEnded = false;
    867             int failsafe = 0; // Avoid infinite loops
    868             events: {
    869                 while (true) {
    870                     int monthIndex = 0;
    871                     if (failsafe++ > MAX_ALLOWED_ITERATIONS) { // Give up after about 1 second of processing
    872                         throw new DateException("Recurrence processing stuck: " + r.toString());
    873                     }
    874 
    875                     unsafeNormalize(iterator);
    876 
    877                     int iteratorYear = iterator.year;
    878                     int iteratorMonth = iterator.month + 1;
    879                     int iteratorDay = iterator.monthDay;
    880                     int iteratorHour = iterator.hour;
    881                     int iteratorMinute = iterator.minute;
    882                     int iteratorSecond = iterator.second;
    883 
    884                     // year is never expanded -- there is no BYYEAR
    885                     generated.set(iterator);
    886 
    887                     if (SPEW) Log.i(TAG, "year=" + generated.year);
    888 
    889                     do { // month
    890                         int month = usebymonth
    891                                         ? r.bymonth[monthIndex]
    892                                         : iteratorMonth;
    893                         month--;
    894                         if (SPEW) Log.i(TAG, "  month=" + month);
    895 
    896                         int dayIndex = 1;
    897                         int lastDayToExamine = 0;
    898 
    899                         // Use this to handle weeks that overlap the end of the month.
    900                         // Keep the year and month that days is for, and generate it
    901                         // when needed in the loop
    902                         if (useDays) {
    903                             // Determine where to start and end, don't worry if this happens
    904                             // to be before dtstart or after the end, because that will be
    905                             // filtered in the inner loop
    906                             if (freq == EventRecurrence.WEEKLY) {
    907                                 /*
    908                                  * iterator.weekDay indicates the day of the week (0-6, SU-SA).
    909                                  * Because dayIndex might start in the middle of a week, and we're
    910                                  * interested in treating a week as a unit, we want to move
    911                                  * backward to the start of the week.  (This could make the
    912                                  * dayIndex negative, which will be corrected by normalization
    913                                  * later on.)
    914                                  *
    915                                  * The day that starts the week is determined by WKST, which
    916                                  * defaults to MO.
    917                                  *
    918                                  * Example: dayIndex is Tuesday the 8th, and weeks start on
    919                                  * Thursdays.  Tuesday is day 2, Thursday is day 4, so we
    920                                  * want to move back (2 - 4 + 7) % 7 = 5 days to the previous
    921                                  * Thursday.  If weeks started on Mondays, we would only
    922                                  * need to move back (2 - 1 + 7) % 7 = 1 day.
    923                                  */
    924                                 int weekStartAdj = (iterator.weekDay -
    925                                         EventRecurrence.day2TimeDay(r.wkst) + 7) % 7;
    926                                 dayIndex = iterator.monthDay - weekStartAdj;
    927                                 lastDayToExamine = dayIndex + 6;
    928                             } else {
    929                                 lastDayToExamine = generated
    930                                     .getActualMaximum(Time.MONTH_DAY);
    931                             }
    932                             if (SPEW) Log.i(TAG, "dayIndex=" + dayIndex
    933                                     + " lastDayToExamine=" + lastDayToExamine
    934                                     + " days=" + days);
    935                         }
    936 
    937                         do { // day
    938                             int day;
    939                             if (useDays) {
    940                                 if (!days.get(iterator, dayIndex)) {
    941                                     dayIndex++;
    942                                     continue;
    943                                 } else {
    944                                     day = dayIndex;
    945                                 }
    946                             } else {
    947                                 day = iteratorDay;
    948                             }
    949                             if (SPEW) Log.i(TAG, "    day=" + day);
    950 
    951                             // hour
    952                             int hourIndex = 0;
    953                             do {
    954                                 int hour = usebyhour
    955                                                 ? r.byhour[hourIndex]
    956                                                 : iteratorHour;
    957                                 if (SPEW) Log.i(TAG, "      hour=" + hour + " usebyhour=" + usebyhour);
    958 
    959                                 // minute
    960                                 int minuteIndex = 0;
    961                                 do {
    962                                     int minute = usebyminute
    963                                                     ? r.byminute[minuteIndex]
    964                                                     : iteratorMinute;
    965                                     if (SPEW) Log.i(TAG, "        minute=" + minute);
    966 
    967                                     // second
    968                                     int secondIndex = 0;
    969                                     do {
    970                                         int second = usebysecond
    971                                                         ? r.bysecond[secondIndex]
    972                                                         : iteratorSecond;
    973                                         if (SPEW) Log.i(TAG, "          second=" + second);
    974 
    975                                         // we do this here each time, because if we distribute it, we find the
    976                                         // month advancing extra times, as we set the month to the 32nd, 33rd, etc.
    977                                         // days.
    978                                         generated.set(second, minute, hour, day, month, iteratorYear);
    979                                         unsafeNormalize(generated);
    980 
    981                                         long genDateValue = normDateTimeComparisonValue(generated);
    982                                         // sometimes events get generated (BYDAY, BYHOUR, etc.) that
    983                                         // are before dtstart.  Filter these.  I believe this is correct,
    984                                         // but Google Calendar doesn't seem to always do this.
    985                                         if (genDateValue >= dtstartDateValue) {
    986                                             // filter and then add
    987                                             // TODO: we don't check for stop conditions (like
    988                                             //       passing the "end" date) unless the filter
    989                                             //       allows the event.  Could stop sooner.
    990                                             int filtered = filter(r, generated);
    991                                             if (0 == filtered) {
    992 
    993                                                 // increase the count as long
    994                                                 // as this isn't the same
    995                                                 // as the first instance
    996                                                 // specified by the DTSTART
    997                                                 // (for RRULEs -- additive).
    998                                                 // This condition must be the complement of the
    999                                                 // condition for incrementing count at the
   1000                                                 // beginning of the method, so if we don't
   1001                                                 // increment count there, we increment it here.
   1002                                                 // For example, if add is set and dtstartDateValue
   1003                                                 // is inside the start/end range, then it was added
   1004                                                 // and count was incremented at the beginning.
   1005                                                 // If dtstartDateValue is outside the range or add
   1006                                                 // is not set, then we must increment count here.
   1007                                                 if (!(dtstartDateValue == genDateValue
   1008                                                         && add
   1009                                                         && dtstartDateValue >= rangeStartDateValue
   1010                                                         && dtstartDateValue < rangeEndDateValue)) {
   1011                                                     ++count;
   1012                                                 }
   1013                                                 // one reason we can stop is that
   1014                                                 // we're past the until date
   1015                                                 if (genDateValue > untilDateValue) {
   1016                                                     if (SPEW) {
   1017                                                         Log.i(TAG, "stopping b/c until="
   1018                                                             + untilDateValue
   1019                                                             + " generated="
   1020                                                             + genDateValue);
   1021                                                     }
   1022                                                     break events;
   1023                                                 }
   1024                                                 // or we're past rangeEnd
   1025                                                 if (genDateValue >= rangeEndDateValue) {
   1026                                                     if (SPEW) {
   1027                                                         Log.i(TAG, "stopping b/c rangeEnd="
   1028                                                                 + rangeEndDateValue
   1029                                                                 + " generated=" + generated);
   1030                                                     }
   1031                                                     break events;
   1032                                                 }
   1033 
   1034                                                 if (genDateValue >= rangeStartDateValue) {
   1035                                                     if (SPEW) {
   1036                                                         Log.i(TAG, "adding date=" + generated + " filtered=" + filtered);
   1037                                                     }
   1038                                                     if (add) {
   1039                                                         out.add(genDateValue);
   1040                                                     } else {
   1041                                                         out.remove(genDateValue);
   1042                                                     }
   1043                                                 }
   1044                                                 // another is that count is high enough
   1045                                                 if (r.count > 0 && r.count == count) {
   1046                                                     //Log.i(TAG, "stopping b/c count=" + count);
   1047                                                     break events;
   1048                                                 }
   1049                                             }
   1050                                         }
   1051                                         secondIndex++;
   1052                                     } while (usebysecond && secondIndex < bysecondCount);
   1053                                     minuteIndex++;
   1054                                 } while (usebyminute && minuteIndex < byminuteCount);
   1055                                 hourIndex++;
   1056                             } while (usebyhour && hourIndex < byhourCount);
   1057                             dayIndex++;
   1058                         } while (useDays && dayIndex <= lastDayToExamine);
   1059                         monthIndex++;
   1060                     } while (usebymonth && monthIndex < bymonthCount);
   1061 
   1062                     // Add freqAmount to freqField until we get another date that we want.
   1063                     // We don't want to "generate" dates with the iterator.
   1064                     // XXX: We do this for days, because there is a varying number of days
   1065                     // per month
   1066                     int oldDay = iterator.monthDay;
   1067                     generated.set(iterator);  // just using generated as a temporary.
   1068                     int n = 1;
   1069                     while (true) {
   1070                         int value = freqAmount * n;
   1071                         switch (freqField) {
   1072                             case Time.SECOND:
   1073                                 iterator.second += value;
   1074                                 break;
   1075                             case Time.MINUTE:
   1076                                 iterator.minute += value;
   1077                                 break;
   1078                             case Time.HOUR:
   1079                                 iterator.hour += value;
   1080                                 break;
   1081                             case Time.MONTH_DAY:
   1082                                 iterator.monthDay += value;
   1083                                 break;
   1084                             case Time.MONTH:
   1085                                 iterator.month += value;
   1086                                 break;
   1087                             case Time.YEAR:
   1088                                 iterator.year += value;
   1089                                 break;
   1090                             case Time.WEEK_DAY:
   1091                                 iterator.monthDay += value;
   1092                                 break;
   1093                             case Time.YEAR_DAY:
   1094                                 iterator.monthDay += value;
   1095                                 break;
   1096                             default:
   1097                                 throw new RuntimeException("bad field=" + freqField);
   1098                         }
   1099 
   1100                         unsafeNormalize(iterator);
   1101                         if (freqField != Time.YEAR && freqField != Time.MONTH) {
   1102                             break;
   1103                         }
   1104                         if (iterator.monthDay == oldDay) {
   1105                             break;
   1106                         }
   1107                         n++;
   1108                         iterator.set(generated);
   1109                     }
   1110                 }
   1111             }
   1112         }
   1113         catch (DateException e) {
   1114             Log.w(TAG, "DateException with r=" + r + " rangeStart=" + rangeStartDateValue
   1115                     + " rangeEnd=" + rangeEndDateValue);
   1116             throw e;
   1117         }
   1118         catch (RuntimeException t) {
   1119             Log.w(TAG, "RuntimeException with r=" + r + " rangeStart=" + rangeStartDateValue
   1120                     + " rangeEnd=" + rangeEndDateValue);
   1121             throw t;
   1122         }
   1123     }
   1124 
   1125     /**
   1126      * Normalizes the date fields to give a valid date, but if the time falls
   1127      * in the invalid window during a transition out of Daylight Saving Time
   1128      * when time jumps forward an hour, then the "normalized" value will be
   1129      * invalid.
   1130      * <p>
   1131      * This method also computes the weekDay and yearDay fields.
   1132      *
   1133      * <p>
   1134      * This method does not modify the fields isDst, or gmtOff.
   1135      */
   1136     static void unsafeNormalize(Time date) {
   1137         int second = date.second;
   1138         int minute = date.minute;
   1139         int hour = date.hour;
   1140         int monthDay = date.monthDay;
   1141         int month = date.month;
   1142         int year = date.year;
   1143 
   1144         int addMinutes = ((second < 0) ? (second - 59) : second) / 60;
   1145         second -= addMinutes * 60;
   1146         minute += addMinutes;
   1147         int addHours = ((minute < 0) ? (minute - 59) : minute) / 60;
   1148         minute -= addHours * 60;
   1149         hour += addHours;
   1150         int addDays = ((hour < 0) ? (hour - 23) : hour) / 24;
   1151         hour -= addDays * 24;
   1152         monthDay += addDays;
   1153 
   1154         // We want to make "monthDay" positive. We do this by subtracting one
   1155         // from the year and adding a year's worth of days to "monthDay" in
   1156         // the following loop while "monthDay" <= 0.
   1157         while (monthDay <= 0) {
   1158             // If month is after Feb, then add this year's length so that we
   1159             // include this year's leap day, if any.
   1160             // Otherwise (the month is Feb or earlier), add last year's length.
   1161             // Subtract one from the year in either case. This gives the same
   1162             // effective date but makes monthDay (the day of the month) much
   1163             // larger. Eventually (usually in one iteration) monthDay will
   1164             // be positive.
   1165             int days = month > 1 ? yearLength(year) : yearLength(year - 1);
   1166             monthDay += days;
   1167             year -= 1;
   1168         }
   1169         // At this point, monthDay >= 1. Normalize the month to the range [0,11].
   1170         if (month < 0) {
   1171             int years = (month + 1) / 12 - 1;
   1172             year += years;
   1173             month -= 12 * years;
   1174         } else if (month >= 12) {
   1175             int years = month / 12;
   1176             year += years;
   1177             month -= 12 * years;
   1178         }
   1179         // At this point, month is in the range [0,11] and monthDay >= 1.
   1180         // Now loop until the monthDay is in the correct range for the month.
   1181         while (true) {
   1182             // On January, check if we can jump forward a whole year.
   1183             if (month == 0) {
   1184                 int yearLength = yearLength(year);
   1185                 if (monthDay > yearLength) {
   1186                     year++;
   1187                     monthDay -= yearLength;
   1188                 }
   1189             }
   1190             int monthLength = monthLength(year, month);
   1191             if (monthDay > monthLength) {
   1192                 monthDay -= monthLength;
   1193                 month++;
   1194                 if (month >= 12) {
   1195                     month -= 12;
   1196                     year++;
   1197                 }
   1198             } else break;
   1199         }
   1200         // At this point, monthDay <= the length of the current month and is
   1201         // in the range [1,31].
   1202 
   1203         date.second = second;
   1204         date.minute = minute;
   1205         date.hour = hour;
   1206         date.monthDay = monthDay;
   1207         date.month = month;
   1208         date.year = year;
   1209         date.weekDay = weekDay(year, month, monthDay);
   1210         date.yearDay = yearDay(year, month, monthDay);
   1211     }
   1212 
   1213     /**
   1214      * Returns true if the given year is a leap year.
   1215      *
   1216      * @param year the given year to test
   1217      * @return true if the given year is a leap year.
   1218      */
   1219     static boolean isLeapYear(int year) {
   1220         return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0));
   1221     }
   1222 
   1223     /**
   1224      * Returns the number of days in the given year.
   1225      *
   1226      * @param year the given year
   1227      * @return the number of days in the given year.
   1228      */
   1229     static int yearLength(int year) {
   1230         return isLeapYear(year) ? 366 : 365;
   1231     }
   1232 
   1233     private static final int[] DAYS_PER_MONTH = { 31, 28, 31, 30, 31, 30, 31,
   1234             31, 30, 31, 30, 31 };
   1235     private static final int[] DAYS_IN_YEAR_PRECEDING_MONTH = { 0, 31, 59, 90,
   1236         120, 151, 180, 212, 243, 273, 304, 334 };
   1237 
   1238     /**
   1239      * Returns the number of days in the given month of the given year.
   1240      *
   1241      * @param year the given year.
   1242      * @param month the given month in the range [0,11]
   1243      * @return the number of days in the given month of the given year.
   1244      */
   1245     static int monthLength(int year, int month) {
   1246         int n = DAYS_PER_MONTH[month];
   1247         if (n != 28) {
   1248             return n;
   1249         }
   1250         return isLeapYear(year) ? 29 : 28;
   1251     }
   1252 
   1253     /**
   1254      * Computes the weekday, a number in the range [0,6] where Sunday=0, from
   1255      * the given year, month, and day.
   1256      *
   1257      * @param year the year
   1258      * @param month the 0-based month in the range [0,11]
   1259      * @param day the 1-based day of the month in the range [1,31]
   1260      * @return the weekday, a number in the range [0,6] where Sunday=0
   1261      */
   1262     static int weekDay(int year, int month, int day) {
   1263         if (month <= 1) {
   1264             month += 12;
   1265             year -= 1;
   1266         }
   1267         return (day + (13 * month - 14) / 5 + year + year/4 - year/100 + year/400) % 7;
   1268     }
   1269 
   1270     /**
   1271      * Computes the 0-based "year day", given the year, month, and day.
   1272      *
   1273      * @param year the year
   1274      * @param month the 0-based month in the range [0,11]
   1275      * @param day the 1-based day in the range [1,31]
   1276      * @return the 0-based "year day", the number of days into the year
   1277      */
   1278     static int yearDay(int year, int month, int day) {
   1279         int yearDay = DAYS_IN_YEAR_PRECEDING_MONTH[month] + day - 1;
   1280         if (month >= 2 && isLeapYear(year)) {
   1281             yearDay += 1;
   1282         }
   1283         return yearDay;
   1284     }
   1285 
   1286     /**
   1287      * Converts a normalized Time value to a 64-bit long. The mapping of Time
   1288      * values to longs provides a total ordering on the Time values so that
   1289      * two Time values can be compared efficiently by comparing their 64-bit
   1290      * long values.  This is faster than converting the Time values to UTC
   1291      * millliseconds.
   1292      *
   1293      * @param normalized a Time object whose date and time fields have been
   1294      * normalized
   1295      * @return a 64-bit long value that can be used for comparing and ordering
   1296      * dates and times represented by Time objects
   1297      */
   1298     private static final long normDateTimeComparisonValue(Time normalized) {
   1299         // 37 bits for the year, 4 bits for the month, 5 bits for the monthDay,
   1300         // 5 bits for the hour, 6 bits for the minute, 6 bits for the second.
   1301         return ((long)normalized.year << 26) + (normalized.month << 22)
   1302                 + (normalized.monthDay << 17) + (normalized.hour << 12)
   1303                 + (normalized.minute << 6) + normalized.second;
   1304     }
   1305 
   1306     private static final void setTimeFromLongValue(Time date, long val) {
   1307         date.year = (int) (val >> 26);
   1308         date.month = (int) (val >> 22) & 0xf;
   1309         date.monthDay = (int) (val >> 17) & 0x1f;
   1310         date.hour = (int) (val >> 12) & 0x1f;
   1311         date.minute = (int) (val >> 6) & 0x3f;
   1312         date.second = (int) (val & 0x3f);
   1313     }
   1314 }
   1315