src/plugins/vcalendar/libical/libical/icalrecur.c

   1 /* -*- Mode: C -*-
   2   ======================================================================
   3   FILE: icalrecur.c
   4   CREATOR: eric 16 May 2000
   5
   6   $Id$
   7   $Locker$
   8
   9
  10  (C) COPYRIGHT 2000, Eric Busboom, http://www.softwarestudio.org
  11
  12  This program is free software; you can redistribute it and/or modify
  13  it under the terms of either:
  14
  15     The LGPL as published by the Free Software Foundation, version
  16     2.1, available at: http://www.fsf.org/copyleft/lesser.html
  17
  18   Or:
  19
  20     The Mozilla Public License Version 1.0. You may obtain a copy of
  21     the License at http://www.mozilla.org/MPL/
  22
  23
  24   How this code works:
  25
  26   Processing starts when the caller generates a new recurrence
  27   iterator via icalrecur_iterator_new(). This routine copies the
  28   recurrence rule into the iterator and extracts things like start and
  29   end dates. Then, it checks if the rule is legal, using some logic
  30   from RFC2445 and some logic that probably should be in RFC2445.
  31
  32   Then, icalrecur_iterator_new() re-writes some of the BY*
  33   arrays. This involves ( via a call to setup_defaults() ) :
  34
  35   1) For BY rule parts with no data ( ie BYSECOND was not specified )
  36   copy the corresponding time part from DTSTART into the BY array. (
  37   So impl->by_ptrs[BY_SECOND] will then have one element if is
  38   originally had none ) This only happens if the BY* rule part data
  39   would expand the number of occurrences in the occurrence set. This
  40   lets the code ignore DTSTART later on and still use it to get the
  41   time parts that were not specified in any other way.
  42
  43   2) For the by rule part that are not the same interval as the
  44   frequency -- for HOURLY anything but BYHOUR, for instance -- copy the
  45   first data element from the rule part into the first occurrence. For
  46   example, for "INTERVAL=MONTHLY and BYHOUR=10,30", initialize the
  47   first time to be returned to have an hour of 10.
  48
  49   Finally, for INTERVAL=YEARLY, the routine expands the rule to get
  50   all of the days specified in the rule. The code will do this for
  51   each new year, and this is the first expansion. This is a special
  52   case for the yearly interval; no other frequency gets expanded this
  53   way. The yearly interval is the most complex, so some special
  54   processing is required.
  55
  56   After creating a new iterator, the caller will make successive calls
  57   to icalrecur_iterator_next() to get the next time specified by the
  58   rule. The main part of this routine is a switch on the frequency of
  59   the rule. Each different frequency is handled by a different
  60   routine.
  61
  62   For example, next_hour handles the case of INTERVAL=HOURLY, and it
  63   is called by other routines to get the next hour. First, the routine
  64   tries to get the next minute part of a time with a call to
  65   next_minute(). If next_minute() returns 1, it has reached the end of
  66   its data, usually the last element of the BYMINUTE array. Then, if
  67   there is data in the BYHOUR array, the routine changes the hour to
  68   the next one in the array. If INTERVAL=HOURLY, the routine advances
  69   the hour by the interval.
  70
  71   If the routine used the last hour in the BYHOUR array, and the
  72   INTERVAL=HOURLY, then the routine calls increment_monthday() to set
  73   the next month day. The increment_* routines may call higher routine
  74   to increment the month or year also.
  75
  76   The code for INTERVAL=DAILY is handled by next_day(). First, the
  77   routine tries to get the next hour part of a time with a call to
  78   next_hour. If next_hour() returns 1, it has reached the end of its
  79   data, usually the last element of the BYHOUR array. This means that
  80   next_day() should increment the time to the next day. If FREQUENCY==DAILY,
  81   the routine increments the day by the interval; otherwise, it
  82   increments the day by 1.
  83
  84   Next_day() differs from next_hour because it does not use the BYDAY
  85   array to select an appropriate day. Instead, it returns every day (
  86   incrementing by 1 if the frequency is not DAILY with INTERVAL!=1)
  87   Any days that are not specified in an non-empty BYDAY array are
  88   filtered out later.
  89
  90   Generally, the flow of these routine is for a next_* call a next_*
  91   routine of a lower interval ( next_day calls next_hour) and then to
  92   possibly call an increment_* routine of an equal or higher
  93   interval. ( next_day calls increment_monthday() )
  94
  95   When the call to the original next_* routine returns,
  96   icalrecur_iterator_next() will check the returned data against other
  97   BYrule parts to determine if is should be excluded by calling
  98   check_contracting_rules. Generally, a contracting rule is any with a
  99   larger time span than the interval. For instance, if
 100   INTERVAL=DAILY, BYMONTH is a contracting rule part.
 101
 102   Check_contracting_rules() uses icalrecur_check_rulepart() to do its
 103   work. icalrecur_check_rulepart() uses expand_map[] to determine if a rule
 104   is contracting, and if it is, and if the BY rule part has some data,
 105   then the routine checks if the value of a component of the time is
 106   part of the byrule part. For instance, for "INTERVAL=DAILY;
 107   BYMONTH=6,10", icalrecur_check_rulepart() would check that the time value
 108   given to it has a month of either 6 or 10.
 109
 110   Finally, icalrecur_iterator_next() does a few other checks on the
 111   time value, and if it passes, it returns the time.
 112
 113   A note about the end_of_data flag. The flag indicates that the
 114   routine is at the end of its data -- the last BY rule if the routine
 115   is using by rules, or the last day of the week/month/year/etc if
 116   not.
 117
 118   This flag is usually set early in a next_* routine and returned in
 119   the end. The way it is used allows the next_* routine to set the
 120   last time back to the first element in a BYxx rule, and then signal
 121   to the higer level routine to increment the next higher level. For
 122   instance. WITH FREQ=MONTHLY;BYDAY=TU,FR, After next_weekday_by_month
 123   runs though both TU and FR, it sets the week day back to TU and sets
 124   end_of_data to 1x. This signals next_month to increment the month.
 125
 126
 127  ======================================================================*/
 128
 129 #ifdef HAVE_CONFIG_H
 130 #include "config.h"
 131 #endif
 132
 133 #include "icalrecur.h"
 134
 135 #ifdef ICAL_NO_LIBICAL
 136 #define icalerror_set_errno(x)
 137 #define  icalerror_check_arg_rv(x,y)
 138 #else
 139 #include "icalerror.h"
 140 #include "icalmemory.h"
 141 #endif
 142
 143 #include <glib.h> /* for malloc */
 144 #include <stdlib.h> /* for malloc */
 145 #include <errno.h> /* for errno */
 146 #include <string.h> /* for strdup and strchr*/
 147 #include <assert.h>
 148 #include <stddef.h> /* For offsetof() macro */
 149
 150 #include "pvl.h"
 151
 152 #define TEMP_MAX 1024
 153
 154
 155 #define BYDAYIDX impl->by_indices[BY_DAY]
 156 #define BYDAYPTR impl->by_ptrs[BY_DAY]
 157
 158 #define BYMONIDX impl->by_indices[BY_MONTH]
 159 #define BYMONPTR impl->by_ptrs[BY_MONTH]
 160
 161 #define BYMDIDX impl->by_indices[BY_MONTH_DAY]
 162 #define BYMDPTR impl->by_ptrs[BY_MONTH_DAY]
 163
 164 #define BYWEEKIDX impl->by_indices[BY_WEEK_NO]
 165 #define BYWEEKPTR impl->by_ptrs[BY_WEEK_NO]
 166
 167 const char* icalrecur_freq_to_string(icalrecurrencetype_frequency kind);
 168 icalrecurrencetype_frequency icalrecur_string_to_freq(const char* str);
 169
 170 const char* icalrecur_weekday_to_string(icalrecurrencetype_weekday kind);
 171 icalrecurrencetype_weekday icalrecur_string_to_weekday(const char* str);
 172
 173
 174
 175 /*********************** Rule parsing routines ************************/
 176
 177 struct icalrecur_parser {
 178         const char* rule;
 179         char* copy;
 180         char* this_clause;
 181         char* next_clause;
 182
 183         struct icalrecurrencetype rt;
 184 };
 185
 186 const char* icalrecur_first_clause(struct icalrecur_parser *parser)
 187 {
 188     char *idx;
 189     parser->this_clause = parser->copy;
 190
 191     idx = strchr(parser->this_clause,';');
 192
 193     if (idx == 0){
 194         parser->next_clause = 0;
 195         return 0;
 196     }
 197
 198     *idx = 0;
 199     idx++;
 200     parser->next_clause = idx;
 201
 202     return parser->this_clause;
 203
 204 }
 205
 206 const char* icalrecur_next_clause(struct icalrecur_parser *parser)
 207 {
 208     char* idx;
 209
 210     parser->this_clause = parser->next_clause;
 211
 212     if(parser->this_clause == 0){
 213         return 0;
 214     }
 215
 216     idx = strchr(parser->this_clause,';');
 217
 218     if (idx == 0){
 219         parser->next_clause = 0;
 220     } else {
 221
 222         *idx = 0;
 223         idx++;
 224         parser->next_clause = idx;
 225     }
 226
 227     return parser->this_clause;
 228
 229 }
 230
 231 void icalrecur_clause_name_and_value(struct icalrecur_parser *parser,
 232                                      char** name, char** value)
 233 {
 234     char *idx;
 235
 236     *name = parser->this_clause;
 237
 238     idx = strchr(parser->this_clause,'=');
 239
 240     if (idx == 0){
 241         *name = 0;
 242         *value = 0;
 243         return;
 244     }
 245
 246     *idx = 0;
 247     idx++;
 248     *value = idx;
 249 }
 250
 251 void icalrecur_add_byrules(struct icalrecur_parser *parser, short *array,
 252                            int size, char* vals)
 253 {
 254     char *t, *n;
 255     int i=0;
 256     int sign = 1;
 257     short v;
 258
 259     n = vals;
 260
 261     while(n != 0){
 262
 263         if(i == size){
 264             return;
 265         }
 266
 267         t = n;
 268
 269         n = strchr(t,',');
 270
 271         if(n != 0){
 272             *n = 0;
 273             n++;
 274         }
 275
 276         /* Get optional sign. HACK. sign is not allowed for all BYxxx
 277            rule parts */
 278         if( *t == '-'){
 279             sign = -1;
 280             t++;
 281         } else if (*t == '+'){
 282             sign = 1;
 283             t++;
 284         }
 285
 286         v = atoi(t) * sign ;
 287
 288
 289         array[i++] = v;
 290         array[i] =  ICAL_RECURRENCE_ARRAY_MAX;
 291
 292     }
 293
 294 }
 295
 296 void icalrecur_add_bydayrules(struct icalrecur_parser *parser, const char* vals)
 297 {
 298
 299     char *t, *n;
 300     int i=0;
 301     int sign = 1;
 302     int weekno = 0;
 303     icalrecurrencetype_weekday wd;
 304     short *array = parser->rt.by_day;
 305     char* end;
 306     char* vals_copy;
 307
 308     vals_copy = icalmemory_strdup(vals);
 309
 310     end = (char*)vals_copy+strlen(vals_copy);
 311     n = vals_copy;
 312
 313     while(n != 0){
 314
 315
 316         t = n;
 317
 318         n = strchr(t,',');
 319
 320         if(n != 0){
 321             *n = 0;
 322             n++;
 323         }
 324
 325         /* Get optional sign. */
 326         if( *t == '-'){
 327             sign = -1;
 328             t++;
 329         } else if (*t == '+'){
 330             sign = 1;
 331             t++;
 332         } else {
 333             sign = 1;
 334         }
 335
 336         weekno = 0;
 337         /* Get Optional weekno */
 338         if( sscanf(t,"%d",&weekno) != 0){
 339             if (n != 0){
 340                 int weeknolen = (n-t)-3; /* 3 -> one for \0, 2 for day name */
 341                 /* could use abs(log10(weekno))+1, but that needs libm */
 342                 t += weeknolen;
 343             } else {
 344                 t = end -2;
 345             }
 346         }
 347
 348         wd = icalrecur_string_to_weekday(t);
 349
 350         array[i++] = sign* ((int)wd + 8*weekno);
 351         array[i] =  ICAL_RECURRENCE_ARRAY_MAX;
 352
 353     }
 354
 355     free(vals_copy);
 356
 357 }
 358
 359
 360 struct icalrecurrencetype icalrecurrencetype_from_string(const char* str)
 361 {
 362     struct icalrecur_parser parser;
 363
 364     memset(&parser,0,sizeof(parser));
 365     icalrecurrencetype_clear(&parser.rt);
 366
 367     icalerror_check_arg_re(str!=0,"str",parser.rt);
 368
 369
 370     /* Set up the parser struct */
 371     parser.rule = str;
 372     parser.copy = icalmemory_strdup(parser.rule);
 373     parser.this_clause = parser.copy;
 374
 375     if(parser.copy == 0){
 376         icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 377         return parser.rt;
 378     }
 379
 380     /* Loop through all of the clauses */
 381     for(icalrecur_first_clause(&parser);
 382         parser.this_clause != 0;
 383         icalrecur_next_clause(&parser))
 384     {
 385         char *name, *value;
 386         icalrecur_clause_name_and_value(&parser,&name,&value);
 387
 388         if(name == 0){
 389             icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 390             icalrecurrencetype_clear(&parser.rt);
 391             return parser.rt;
 392         }
 393
 394         if (strcmp(name,"FREQ") == 0){
 395             parser.rt.freq = icalrecur_string_to_freq(value);
 396         } else if (strcmp(name,"COUNT") == 0){
 397             parser.rt.count = atoi(value);
 398         } else if (strcmp(name,"UNTIL") == 0){
 399             parser.rt.until = icaltime_from_string(value);
 400         } else if (strcmp(name,"INTERVAL") == 0){
 401             parser.rt.interval = atoi(value);
 402         } else if (strcmp(name,"WKST") == 0){
 403             parser.rt.week_start = icalrecur_string_to_weekday(value);
 404         } else if (strcmp(name,"BYSECOND") == 0){
 405             icalrecur_add_byrules(&parser,parser.rt.by_second,
 406                                   ICAL_BY_SECOND_SIZE,value);
 407         } else if (strcmp(name,"BYMINUTE") == 0){
 408             icalrecur_add_byrules(&parser,parser.rt.by_minute,
 409                                   ICAL_BY_MINUTE_SIZE,value);
 410         } else if (strcmp(name,"BYHOUR") == 0){
 411             icalrecur_add_byrules(&parser,parser.rt.by_hour,
 412                                   ICAL_BY_HOUR_SIZE,value);
 413         } else if (strcmp(name,"BYDAY") == 0){
 414             icalrecur_add_bydayrules(&parser,value);
 415         } else if (strcmp(name,"BYMONTHDAY") == 0){
 416             icalrecur_add_byrules(&parser,parser.rt.by_month_day,
 417                                   ICAL_BY_MONTHDAY_SIZE,value);
 418         } else if (strcmp(name,"BYYEARDAY") == 0){
 419             icalrecur_add_byrules(&parser,parser.rt.by_year_day,
 420                                   ICAL_BY_YEARDAY_SIZE,value);
 421         } else if (strcmp(name,"BYWEEKNO") == 0){
 422             icalrecur_add_byrules(&parser,parser.rt.by_week_no,
 423                                   ICAL_BY_WEEKNO_SIZE,value);
 424         } else if (strcmp(name,"BYMONTH") == 0){
 425             icalrecur_add_byrules(&parser,parser.rt.by_month,
 426                                   ICAL_BY_MONTH_SIZE,value);
 427         } else if (strcmp(name,"BYSETPOS") == 0){
 428             icalrecur_add_byrules(&parser,parser.rt.by_set_pos,
 429                                   ICAL_BY_SETPOS_SIZE,value);
 430         } else {
 431             icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 432             icalrecurrencetype_clear(&parser.rt);
 433             return parser.rt;
 434         }
 435
 436     }
 437
 438     free(parser.copy);
 439
 440     return parser.rt;
 441
 442 }
 443
 444 #ifndef ICAL_NO_LIBICAL
 445
 446 struct { char* str;size_t offset; short limit;  } recurmap[] =
 447 {
 448     {";BYSECOND=",offsetof(struct icalrecurrencetype,by_second),60},
 449     {";BYMINUTE=",offsetof(struct icalrecurrencetype,by_minute),60},
 450     {";BYHOUR=",offsetof(struct icalrecurrencetype,by_hour),24},
 451     {";BYDAY=",offsetof(struct icalrecurrencetype,by_day),7},
 452     {";BYMONTHDAY=",offsetof(struct icalrecurrencetype,by_month_day),31},
 453     {";BYYEARDAY=",offsetof(struct icalrecurrencetype,by_year_day),366},
 454     {";BYWEEKNO=",offsetof(struct icalrecurrencetype,by_week_no),52},
 455     {";BYMONTH=",offsetof(struct icalrecurrencetype,by_month),12},
 456     {";BYSETPOS=",offsetof(struct icalrecurrencetype,by_set_pos),366},
 457     {0,0,0},
 458 };
 459
 460 /* A private routine in icalvalue.c */
 461 void print_datetime_to_string(char* str,  struct icaltimetype *data);
 462
 463 char* icalrecurrencetype_as_string(struct icalrecurrencetype *recur)
 464 {
 465     char* str;
 466     char *str_p;
 467     size_t buf_sz = 200;
 468     char temp[20];
 469     int i,j;
 470
 471     if(recur->freq == ICAL_NO_RECURRENCE){
 472         return 0;
 473     }
 474
 475     str = (char*)icalmemory_tmp_buffer(buf_sz);
 476     str_p = str;
 477
 478     icalmemory_append_string(&str,&str_p,&buf_sz,"FREQ=");
 479     icalmemory_append_string(&str,&str_p,&buf_sz,
 480                              icalrecur_freq_to_string(recur->freq));
 481
 482     if(recur->until.year != 0){
 483
 484         temp[0] = 0;
 485         print_datetime_to_string(temp,&(recur->until));
 486
 487         icalmemory_append_string(&str,&str_p,&buf_sz,";UNTIL=");
 488         icalmemory_append_string(&str,&str_p,&buf_sz, temp);
 489     }
 490
 491     if(recur->count != 0){
 492         sprintf(temp,"%d",recur->count);
 493         icalmemory_append_string(&str,&str_p,&buf_sz,";COUNT=");
 494         icalmemory_append_string(&str,&str_p,&buf_sz, temp);
 495     }
 496
 497     if(recur->interval != 0){
 498         sprintf(temp,"%d",recur->interval);
 499         icalmemory_append_string(&str,&str_p,&buf_sz,";INTERVAL=");
 500         icalmemory_append_string(&str,&str_p,&buf_sz, temp);
 501     }
 502
 503     for(j =0; recurmap[j].str != 0; j++){
 504         short* array = (short*)(recurmap[j].offset+ (size_t)recur);
 505         short limit = recurmap[j].limit;
 506
 507         /* Skip unused arrays */
 508         if( array[0] != ICAL_RECURRENCE_ARRAY_MAX ) {
 509
 510             icalmemory_append_string(&str,&str_p,&buf_sz,recurmap[j].str);
 511
 512             for(i=0;
 513                 i< limit  && array[i] != ICAL_RECURRENCE_ARRAY_MAX;
 514                 i++){
 515                 if (j == 3) { /* BYDAY */
 516                     short dow = icalrecurrencetype_day_day_of_week(array[i]);
 517                     const char *daystr = icalrecur_weekday_to_string(dow);
 518                     short pos;
 519
 520                     pos = icalrecurrencetype_day_position(array[i]);
 521
 522                     if (pos == 0)
 523                         icalmemory_append_string(&str,&str_p,&buf_sz,daystr);
 524                     else {
 525                         sprintf(temp,"%d%s",pos,daystr);
 526                         icalmemory_append_string(&str,&str_p,&buf_sz,temp);
 527                     }
 528
 529                 } else {
 530                     sprintf(temp,"%d",array[i]);
 531                     icalmemory_append_string(&str,&str_p,&buf_sz, temp);
 532                 }
 533
 534                 if( (i+1)<limit &&array[i+1]
 535                     != ICAL_RECURRENCE_ARRAY_MAX){
 536                     icalmemory_append_char(&str,&str_p,&buf_sz,',');
 537                 }
 538             }
 539         }
 540     }
 541
 542     return  str;
 543 }
 544 #endif
 545
 546
 547
 548 /************************* occurrence iteration routiens ******************/
 549
 550 enum byrule {
 551     NO_CONTRACTION = -1,
 552     BY_SECOND = 0,
 553     BY_MINUTE = 1,
 554     BY_HOUR = 2,
 555     BY_DAY = 3,
 556     BY_MONTH_DAY = 4,
 557     BY_YEAR_DAY = 5,
 558     BY_WEEK_NO = 6,
 559     BY_MONTH = 7,
 560     BY_SET_POS
 561 };
 562
 563
 564
 565 struct icalrecur_iterator_impl {
 566
 567     struct icaltimetype dtstart; /* Hack. Make into time_t */
 568     struct icaltimetype last; /* last time return from _iterator_next*/
 569     int occurrence_no; /* number of step made on t iterator */
 570     struct icalrecurrencetype rule;
 571
 572     short days[366];
 573     short days_index;
 574
 575     enum byrule byrule;
 576     short by_indices[9];
 577     short orig_data[9]; /* 1 if there was data in the byrule */
 578
 579
 580     short *by_ptrs[9]; /* Pointers into the by_* array elements of the rule */
 581
 582 };
 583
 584 int icalrecur_iterator_sizeof_byarray(short* byarray)
 585 {
 586     int array_itr;
 587
 588     for(array_itr = 0;
 589         byarray[array_itr] != ICAL_RECURRENCE_ARRAY_MAX;
 590         array_itr++){
 591     }
 592
 593     return array_itr;
 594 }
 595
 596 enum expand_table {
 597     UNKNOWN  = 0,
 598     CONTRACT = 1,
 599     EXPAND =2,
 600     ILLEGAL=3
 601 };
 602
 603 /* The split map indicates, for a particular interval, wether a BY_*
 604    rule part expands the number of instances in the occcurrence set or
 605    contracts it. 1=> contract, 2=>expand, and 3 means the pairing is
 606    not allowed. */
 607 struct expand_split_map_struct
 608 {
 609         icalrecurrencetype_frequency frequency;
 610
 611         /* Elements of the 'map' array correspond to the BYxxx rules:
 612            Second,Minute,Hour,Day,Month Day,Year Day,Week No,Month*/
 613
 614         short map[8];
 615 };
 616
 617 struct expand_split_map_struct expand_map[] =
 618 {
 619     {ICAL_SECONDLY_RECURRENCE,{1,1,1,1,1,1,1,1}},
 620     {ICAL_MINUTELY_RECURRENCE,{2,1,1,1,1,1,1,1}},
 621     {ICAL_HOURLY_RECURRENCE,  {2,2,1,1,1,1,1,1}},
 622     {ICAL_DAILY_RECURRENCE,   {2,2,2,1,1,1,1,1}},
 623     {ICAL_WEEKLY_RECURRENCE,  {2,2,2,2,3,3,1,1}},
 624     {ICAL_MONTHLY_RECURRENCE, {2,2,2,2,2,3,3,1}},
 625     {ICAL_YEARLY_RECURRENCE,  {2,2,2,2,2,2,2,2}},
 626     {ICAL_NO_RECURRENCE,      {0,0,0,0,0,0,0,0}}
 627
 628 };
 629
 630
 631
 632 /* Check that the rule has only the two given interday byrule parts. */
 633 int icalrecur_two_byrule(struct icalrecur_iterator_impl* impl,
 634                          enum byrule one,enum byrule two)
 635 {
 636     short test_array[9];
 637     enum byrule itr;
 638     int passes = 0;
 639
 640     memset(test_array,0,9);
 641
 642     test_array[one] = 1;
 643     test_array[two] = 1;
 644
 645     for(itr = BY_DAY; itr != BY_SET_POS; itr++){
 646
 647         if( (test_array[itr] == 0  &&
 648              impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX
 649             ) ||
 650             (test_array[itr] == 1  &&
 651              impl->by_ptrs[itr][0] == ICAL_RECURRENCE_ARRAY_MAX
 652                 )
 653             ) {
 654             /* test failed */
 655             passes = 0;
 656         }
 657     }
 658
 659     return passes;
 660
 661 }
 662
 663 /* Check that the rule has only the one given interdat byrule parts. */
 664 int icalrecur_one_byrule(struct icalrecur_iterator_impl* impl,enum byrule one)
 665 {
 666     int passes = 1;
 667     enum byrule itr;
 668
 669     for(itr = BY_DAY; itr != BY_SET_POS; itr++){
 670
 671         if ((itr==one && impl->by_ptrs[itr][0] == ICAL_RECURRENCE_ARRAY_MAX) ||
 672             (itr!=one && impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX)) {
 673             passes = 0;
 674         }
 675     }
 676
 677     return passes;
 678 }
 679
 680 int count_byrules(struct icalrecur_iterator_impl* impl)
 681 {
 682     int count = 0;
 683     enum byrule itr;
 684
 685     for(itr = BY_DAY; itr <= BY_SET_POS; itr++){
 686         if(impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX){
 687             count++;
 688         }
 689     }
 690
 691     return count;
 692 }
 693
 694
 695 void setup_defaults(struct icalrecur_iterator_impl* impl,
 696                     enum byrule byrule, icalrecurrencetype_frequency req,
 697                     short deftime, int *timepart)
 698 {
 699
 700     icalrecurrencetype_frequency freq;
 701     freq = impl->rule.freq;
 702
 703     /* Re-write the BY rule arrays with data from the DTSTART time so
 704        we don't have to explicitly deal with DTSTART */
 705
 706     if(impl->by_ptrs[byrule][0] == ICAL_RECURRENCE_ARRAY_MAX &&
 707         expand_map[freq].map[byrule] != CONTRACT){
 708         impl->by_ptrs[byrule][0] = deftime;
 709     }
 710
 711     /* Initialize the first occurence */
 712     if( freq != req && expand_map[freq].map[byrule] != CONTRACT){
 713         *timepart = impl->by_ptrs[byrule][0];
 714     }
 715
 716
 717 }
 718
 719 int has_by_data(struct icalrecur_iterator_impl* impl, enum byrule byrule){
 720
 721     return (impl->orig_data[byrule] == 1);
 722 }
 723
 724
 725 int expand_year_days(struct icalrecur_iterator_impl* impl,short year);
 726
 727
 728 icalrecur_iterator* icalrecur_iterator_new(struct icalrecurrencetype rule,
 729                                            struct icaltimetype dtstart)
 730 {
 731     struct icalrecur_iterator_impl* impl;
 732     icalrecurrencetype_frequency freq;
 733
 734     short days_in_month;
 735
 736     if ( ( impl = (struct icalrecur_iterator_impl *)
 737            malloc(sizeof(struct icalrecur_iterator_impl))) == 0) {
 738         icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 739         return 0;
 740     }
 741
 742     memset(impl,0,sizeof(struct icalrecur_iterator_impl));
 743
 744     impl->rule = rule;
 745     impl->last = dtstart;
 746     impl->dtstart = dtstart;
 747     impl->days_index =0;
 748     impl->occurrence_no = 0;
 749     freq = impl->rule.freq;
 750
 751     /* Set up convienience pointers to make the code simpler. Allows
 752        us to iterate through all of the BY* arrays in the rule. */
 753
 754     impl->by_ptrs[BY_MONTH]=impl->rule.by_month;
 755     impl->by_ptrs[BY_WEEK_NO]=impl->rule.by_week_no;
 756     impl->by_ptrs[BY_YEAR_DAY]=impl->rule.by_year_day;
 757     impl->by_ptrs[BY_MONTH_DAY]=impl->rule.by_month_day;
 758     impl->by_ptrs[BY_DAY]=impl->rule.by_day;
 759     impl->by_ptrs[BY_HOUR]=impl->rule.by_hour;
 760     impl->by_ptrs[BY_MINUTE]=impl->rule.by_minute;
 761     impl->by_ptrs[BY_SECOND]=impl->rule.by_second;
 762     impl->by_ptrs[BY_SET_POS]=impl->rule.by_set_pos;
 763
 764     memset(impl->orig_data,0,9);
 765
 766     /* Note which by rules had data in them when the iterator was
 767        created. We can't use the actuall by_x arrays, because the
 768        empty ones will be given default values later in this
 769        routine. The orig_data array will be used later in has_by_data */
 770
 771     impl->orig_data[BY_MONTH]
 772         = (impl->rule.by_month[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 773     impl->orig_data[BY_WEEK_NO]
 774       =(impl->rule.by_week_no[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 775     impl->orig_data[BY_YEAR_DAY]
 776     =(impl->rule.by_year_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 777     impl->orig_data[BY_MONTH_DAY]
 778     =(impl->rule.by_month_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 779     impl->orig_data[BY_DAY]
 780         = (impl->rule.by_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 781     impl->orig_data[BY_HOUR]
 782         = (impl->rule.by_hour[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 783     impl->orig_data[BY_MINUTE]
 784      = (impl->rule.by_minute[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 785     impl->orig_data[BY_SECOND]
 786      = (impl->rule.by_second[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 787     impl->orig_data[BY_SET_POS]
 788      = (impl->rule.by_set_pos[0]!=ICAL_RECURRENCE_ARRAY_MAX);
 789
 790
 791     /* Check if the recurrence rule is legal */
 792
 793     /* If the BYYEARDAY appears, no other date rule part may appear.   */
 794
 795     if(icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_MONTH) ||
 796        icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_WEEK_NO) ||
 797        icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_MONTH_DAY) ||
 798        icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_DAY) ){
 799
 800         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 801         free(impl);
 802         return 0;
 803     }
 804
 805     /* BYWEEKNO and BYMONTH rule parts may not both appear.*/
 806
 807     if(icalrecur_two_byrule(impl,BY_WEEK_NO,BY_MONTH)){
 808         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 809         free(impl);
 810         return 0;
 811     }
 812
 813     /* BYWEEKNO and BYMONTHDAY rule parts may not both appear.*/
 814
 815     if(icalrecur_two_byrule(impl,BY_WEEK_NO,BY_MONTH_DAY)){
 816         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 817         free(impl);
 818         return 0;
 819     }
 820
 821
 822     /*For MONTHLY recurrences (FREQ=MONTHLY) neither BYYEARDAY nor
 823       BYWEEKNO may appear. */
 824
 825     if(freq == ICAL_MONTHLY_RECURRENCE &&
 826        icalrecur_one_byrule(impl,BY_WEEK_NO)){
 827         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 828         free(impl);
 829         return 0;
 830     }
 831
 832
 833     /*For WEEKLY recurrences (FREQ=WEEKLY) neither BYMONTHDAY nor
 834       BYYEARDAY may appear. */
 835
 836     if(freq == ICAL_WEEKLY_RECURRENCE &&
 837        icalrecur_one_byrule(impl,BY_MONTH_DAY )) {
 838         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 839         free(impl);
 840         return 0;
 841     }
 842
 843     /* BYYEARDAY may only appear in YEARLY rules */
 844     if(freq != ICAL_YEARLY_RECURRENCE &&
 845        icalrecur_one_byrule(impl,BY_YEAR_DAY )) {
 846         icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 847         free(impl);
 848         return 0;
 849     }
 850
 851     /* Rewrite some of the rules and set up defaults to make later
 852        processing easier. Primarily, t involves copying an element
 853        from the start time into the coresponding BY_* array when the
 854        BY_* array is empty */
 855
 856
 857     setup_defaults(impl,BY_SECOND,ICAL_SECONDLY_RECURRENCE,impl->dtstart.second,
 858                    &(impl->last.second));
 859
 860     setup_defaults(impl,BY_MINUTE,ICAL_MINUTELY_RECURRENCE,impl->dtstart.minute,
 861                    &(impl->last.minute));
 862
 863     setup_defaults(impl,BY_HOUR,ICAL_HOURLY_RECURRENCE,impl->dtstart.hour,
 864                    &(impl->last.hour));
 865
 866     setup_defaults(impl,BY_MONTH_DAY,ICAL_DAILY_RECURRENCE,impl->dtstart.day,
 867                    &(impl->last.day));
 868
 869     setup_defaults(impl,BY_MONTH,ICAL_MONTHLY_RECURRENCE,impl->dtstart.month,
 870                    &(impl->last.month));
 871
 872
 873     if(impl->rule.freq == ICAL_WEEKLY_RECURRENCE ){
 874
 875        if(impl->by_ptrs[BY_DAY][0] == ICAL_RECURRENCE_ARRAY_MAX){
 876
 877            /* Weekly recurrences with no BY_DAY data should occur on the
 878               same day of the week as the start time . */
 879            impl->by_ptrs[BY_DAY][0] = icaltime_day_of_week(impl->dtstart);
 880
 881        } else {
 882           /* If there is BY_DAY data, then we need to move the initial
 883              time to the start of the BY_DAY data. That is if the
 884              start time is on a Wednesday, and the rule has
 885              BYDAY=MO,WE,FR, move the initial time back to
 886              monday. Otherwise, jumping to the next week ( jumping 7
 887              days ahead ) will skip over some occurrences in the
 888              second week. */
 889
 890           /* This is probably a HACK. There should be some more
 891              general way to solve this problem */
 892
 893           short dow = impl->by_ptrs[BY_DAY][0]-icaltime_day_of_week(impl->last);
 894
 895           if(dow < 0) {
 896               /* initial time is after first day of BY_DAY data */
 897
 898               impl->last.day += dow;
 899               impl->last = icaltime_normalize(impl->last);
 900           }
 901       }
 902
 903
 904     }
 905
 906     /* For YEARLY rule, begin by setting up the year days array */
 907
 908     if(impl->rule.freq == ICAL_YEARLY_RECURRENCE){
 909         expand_year_days(impl,impl->last.year);
 910     }
 911
 912
 913     /* If this is a monthly interval with by day data, then we need to
 914        set the last value to the appropriate day of the month */
 915
 916     if(impl->rule.freq == ICAL_MONTHLY_RECURRENCE &&
 917        has_by_data(impl,BY_DAY)) {
 918
 919         short dow = icalrecurrencetype_day_day_of_week(
 920             impl->by_ptrs[BY_DAY][impl->by_indices[BY_DAY]]);
 921         short pos =  icalrecurrencetype_day_position(
 922             impl->by_ptrs[BY_DAY][impl->by_indices[BY_DAY]]);
 923
 924         short poscount = 0;
 925         days_in_month =
 926             icaltime_days_in_month(impl->last.month, impl->last.year);
 927
 928         if(pos >= 0){
 929             /* Count up from the first day pf the month to find the
 930                pos'th weekday of dow ( like the second monday. ) */
 931
 932             for(impl->last.day = 1;
 933                 impl->last.day <= days_in_month;
 934                 impl->last.day++){
 935
 936                 if(icaltime_day_of_week(impl->last) == dow){
 937                     if(++poscount == pos || pos == 0){
 938                         break;
 939                     }
 940                 }
 941             }
 942         } else {
 943             /* Count down from the last day pf the month to find the
 944                pos'th weekday of dow ( like the second to last monday. ) */
 945             pos = -pos;
 946             for(impl->last.day = days_in_month;
 947                 impl->last.day != 0;
 948                 impl->last.day--){
 949
 950                 if(icaltime_day_of_week(impl->last) == dow){
 951                     if(++poscount == pos ){
 952                         break;
 953                     }
 954                 }
 955             }
 956         }
 957
 958
 959         if(impl->last.day > days_in_month || impl->last.day == 0){
 960             icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
 961             free(impl);
 962             return 0;
 963         }
 964
 965     }
 966
 967     return impl;
 968 }
 969
 970
 971 void icalrecur_iterator_free(icalrecur_iterator* i)
 972 {
 973
 974     struct icalrecur_iterator_impl* impl =
 975         (struct icalrecur_iterator_impl*)i;
 976
 977     icalerror_check_arg_rv((impl!=0),"impl");
 978
 979     free(impl);
 980
 981 }
 982
 983
 984 void increment_year(struct icalrecur_iterator_impl* impl, int inc)
 985 {
 986     impl->last.year+=inc;
 987 }
 988
 989 /* Increment month is different that the other incement_* routines --
 990    it figures out the interval for itself, and uses BYMONTH data if
 991    available. */
 992 void increment_month(struct icalrecur_iterator_impl* impl)
 993 {
 994     int years;
 995
 996      if(has_by_data(impl,BY_MONTH) ){
 997          /* Ignore the frequency and use the byrule data */
 998
 999          impl->by_indices[BY_MONTH]++;
1000
1001          if (impl->by_ptrs[BY_MONTH][impl->by_indices[BY_MONTH]]
1002              ==ICAL_RECURRENCE_ARRAY_MAX){
1003              impl->by_indices[BY_MONTH] = 0;
1004
1005              increment_year(impl,1);
1006
1007          }
1008
1009          impl->last.month =
1010              impl->by_ptrs[BY_MONTH][impl->by_indices[BY_MONTH]];
1011
1012      } else {
1013
1014          int inc;
1015
1016          if(impl->rule.freq == ICAL_MONTHLY_RECURRENCE){
1017             inc =  impl->rule.interval;
1018          } else {
1019              inc = 1;
1020          }
1021
1022          impl->last.month+=inc;
1023
1024          /* Months are offset by one */
1025          impl->last.month--;
1026
1027          years = impl->last.month / 12;
1028
1029          impl->last.month = impl->last.month % 12;
1030
1031          impl->last.month++;
1032
1033          if (years != 0){
1034              increment_year(impl,years);
1035          }
1036      }
1037 }
1038
1039 void increment_monthday(struct icalrecur_iterator_impl* impl, int inc)
1040 {
1041     int i;
1042
1043     for(i=0; i<inc; i++){
1044
1045         short days_in_month =
1046             icaltime_days_in_month(impl->last.month,impl->last.year);
1047
1048         impl->last.day++;
1049
1050         if (impl->last.day > days_in_month){
1051             impl->last.day = impl->last.day-days_in_month;
1052             increment_month(impl);
1053         }
1054     }
1055 }
1056
1057
1058 void increment_hour(struct icalrecur_iterator_impl* impl, int inc)
1059 {
1060     short days;
1061
1062     impl->last.hour+=inc;
1063
1064     days = impl->last.hour / 24;
1065     impl->last.hour = impl->last.hour % 24;
1066
1067     if (impl->days != 0){
1068         increment_monthday(impl,days);
1069     }
1070 }
1071
1072 void increment_minute(struct icalrecur_iterator_impl* impl, int inc)
1073 {
1074     short hours;
1075
1076     impl->last.minute+=inc;
1077
1078     hours = impl->last.minute / 60;
1079      impl->last.minute =  impl->last.minute % 60;
1080
1081      if (hours != 0){
1082         increment_hour(impl,hours);
1083     }
1084
1085 }
1086
1087 void increment_second(struct icalrecur_iterator_impl* impl, int inc)
1088 {
1089     short minutes;
1090
1091     impl->last.second+=inc;
1092
1093     minutes = impl->last.second / 60;
1094     impl->last.second = impl->last.second % 60;
1095
1096     if (minutes != 0)
1097     {
1098         increment_minute(impl, minutes);
1099     }
1100 }
1101
1102 #if 0
1103 #include "ical.h"
1104 void test_increment()
1105 {
1106     struct icalrecur_iterator_impl impl;
1107
1108     impl.last =  icaltime_from_string("20000101T000000Z");
1109
1110     printf("Orig: %s\n",icaltime_as_ctime(impl.last));
1111
1112     increment_second(&impl,5);
1113     printf("+ 5 sec    : %s\n",icaltime_as_ctime(impl.last));
1114
1115     increment_second(&impl,355);
1116     printf("+ 355 sec  : %s\n",icaltime_as_ctime(impl.last));
1117
1118     increment_minute(&impl,5);
1119     printf("+ 5 min    : %s\n",icaltime_as_ctime(impl.last));
1120
1121     increment_minute(&impl,360);
1122     printf("+ 360 min  : %s\n",icaltime_as_ctime(impl.last));
1123     increment_hour(&impl,5);
1124     printf("+ 5 hours  : %s\n",icaltime_as_ctime(impl.last));
1125     increment_hour(&impl,43);
1126     printf("+ 43 hours : %s\n",icaltime_as_ctime(impl.last));
1127     increment_monthday(&impl,3);
1128     printf("+ 3 days   : %s\n",icaltime_as_ctime(impl.last));
1129     increment_monthday(&impl,600);
1130     printf("+ 600 days  : %s\n",icaltime_as_ctime(impl.last));
1131
1132 }
1133
1134 #endif
1135
1136 short next_second(struct icalrecur_iterator_impl* impl)
1137 {
1138
1139   short has_by_data = (impl->by_ptrs[BY_SECOND][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1140   short this_frequency = (impl->rule.freq == ICAL_SECONDLY_RECURRENCE);
1141
1142   short end_of_data = 0;
1143
1144   assert(has_by_data || this_frequency);
1145
1146   if(  has_by_data ){
1147       /* Ignore the frequency and use the byrule data */
1148
1149       impl->by_indices[BY_SECOND]++;
1150
1151       if (impl->by_ptrs[BY_SECOND][impl->by_indices[BY_SECOND]]
1152           ==ICAL_RECURRENCE_ARRAY_MAX){
1153           impl->by_indices[BY_SECOND] = 0;
1154
1155           end_of_data = 1;
1156       }
1157
1158
1159       impl->last.second =
1160           impl->by_ptrs[BY_SECOND][impl->by_indices[BY_SECOND]];
1161
1162
1163   } else if( !has_by_data &&  this_frequency ){
1164       /* Compute the next value from the last time and the frequency interval*/
1165       increment_second(impl, impl->rule.interval);
1166
1167   }
1168
1169   /* If we have gone through all of the seconds on the BY list, then we
1170      need to move to the next minute */
1171
1172   if(has_by_data && end_of_data && this_frequency ){
1173       increment_minute(impl,1);
1174   }
1175
1176   return end_of_data;
1177
1178 }
1179
1180 int next_minute(struct icalrecur_iterator_impl* impl)
1181 {
1182
1183   short has_by_data = (impl->by_ptrs[BY_MINUTE][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1184   short this_frequency = (impl->rule.freq == ICAL_MINUTELY_RECURRENCE);
1185
1186   short end_of_data = 0;
1187
1188   assert(has_by_data || this_frequency);
1189
1190
1191   if (next_second(impl) == 0){
1192       return 0;
1193   }
1194
1195   if(  has_by_data ){
1196       /* Ignore the frequency and use the byrule data */
1197
1198       impl->by_indices[BY_MINUTE]++;
1199
1200       if (impl->by_ptrs[BY_MINUTE][impl->by_indices[BY_MINUTE]]
1201           ==ICAL_RECURRENCE_ARRAY_MAX){
1202
1203           impl->by_indices[BY_MINUTE] = 0;
1204
1205           end_of_data = 1;
1206       }
1207
1208       impl->last.minute =
1209           impl->by_ptrs[BY_MINUTE][impl->by_indices[BY_MINUTE]];
1210
1211   } else if( !has_by_data &&  this_frequency ){
1212       /* Compute the next value from the last time and the frequency interval*/
1213       increment_minute(impl,impl->rule.interval);
1214   }
1215
1216 /* If we have gone through all of the minutes on the BY list, then we
1217      need to move to the next hour */
1218
1219   if(has_by_data && end_of_data && this_frequency ){
1220       increment_hour(impl,1);
1221   }
1222
1223   return end_of_data;
1224 }
1225
1226 int next_hour(struct icalrecur_iterator_impl* impl)
1227 {
1228
1229   short has_by_data = (impl->by_ptrs[BY_HOUR][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1230   short this_frequency = (impl->rule.freq == ICAL_HOURLY_RECURRENCE);
1231
1232   short end_of_data = 0;
1233
1234   assert(has_by_data || this_frequency);
1235
1236   if (next_minute(impl) == 0){
1237       return 0;
1238   }
1239
1240   if(  has_by_data ){
1241       /* Ignore the frequency and use the byrule data */
1242
1243       impl->by_indices[BY_HOUR]++;
1244
1245       if (impl->by_ptrs[BY_HOUR][impl->by_indices[BY_HOUR]]
1246           ==ICAL_RECURRENCE_ARRAY_MAX){
1247           impl->by_indices[BY_HOUR] = 0;
1248
1249           end_of_data = 1;
1250       }
1251
1252       impl->last.hour =
1253           impl->by_ptrs[BY_HOUR][impl->by_indices[BY_HOUR]];
1254
1255   } else if( !has_by_data &&  this_frequency ){
1256       /* Compute the next value from the last time and the frequency interval*/
1257       increment_hour(impl,impl->rule.interval);
1258
1259   }
1260
1261   /* If we have gone through all of the hours on the BY list, then we
1262      need to move to the next day */
1263
1264   if(has_by_data && end_of_data && this_frequency ){
1265       increment_monthday(impl,1);
1266   }
1267
1268   return end_of_data;
1269
1270 }
1271
1272 int next_day(struct icalrecur_iterator_impl* impl)
1273 {
1274
1275   short this_frequency = (impl->rule.freq == ICAL_DAILY_RECURRENCE);
1276 #ifndef NDEBUG
1277   short has_by_data = (impl->by_ptrs[BY_DAY][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1278
1279   assert(has_by_data || this_frequency);
1280 #endif /* NDEBUG */
1281
1282   if (next_hour(impl) == 0){
1283       return 0;
1284   }
1285
1286   /* Always increment through the interval, since this routine is not
1287      called by any other next_* routine, and the days that are
1288      excluded will be taken care of by restriction filtering */
1289
1290   if(this_frequency){
1291       increment_monthday(impl,impl->rule.interval);
1292   } else {
1293       increment_monthday(impl,1);
1294   }
1295
1296
1297   return 0;
1298
1299 }
1300
1301
1302 int next_yearday(struct icalrecur_iterator_impl* impl)
1303 {
1304
1305   short has_by_data = (impl->by_ptrs[BY_YEAR_DAY][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1306
1307   short end_of_data = 0;
1308
1309   assert(has_by_data );
1310
1311   if (next_hour(impl) == 0){
1312       return 0;
1313   }
1314
1315   impl->by_indices[BY_YEAR_DAY]++;
1316
1317   if (impl->by_ptrs[BY_YEAR_DAY][impl->by_indices[BY_YEAR_DAY]]
1318       ==ICAL_RECURRENCE_ARRAY_MAX){
1319       impl->by_indices[BY_YEAR_DAY] = 0;
1320
1321       end_of_data = 1;
1322   }
1323
1324   impl->last.day =
1325       impl->by_ptrs[BY_YEAR_DAY][impl->by_indices[BY_YEAR_DAY]];
1326
1327   if(has_by_data && end_of_data){
1328       increment_year(impl,1);
1329   }
1330
1331   return end_of_data;
1332
1333 }
1334
1335 /* This routine is only called by next_week. It is certain that BY_DAY
1336 has data */
1337
1338 int next_weekday_by_week(struct icalrecur_iterator_impl* impl)
1339 {
1340
1341   short end_of_data = 0;
1342   short start_of_week, dow;
1343   struct icaltimetype next;
1344
1345   if (next_hour(impl) == 0){
1346       return 0;
1347   }
1348
1349   assert( impl->by_ptrs[BY_DAY][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1350
1351   while(1) {
1352
1353       impl->by_indices[BY_DAY]++; /* Look at next elem in BYDAY array */
1354
1355       /* Are we at the end of the BYDAY array? */
1356       if (impl->by_ptrs[BY_DAY][impl->by_indices[BY_DAY]]
1357           ==ICAL_RECURRENCE_ARRAY_MAX){
1358
1359           impl->by_indices[BY_DAY] = 0; /* Reset to 0 */
1360           end_of_data = 1; /* Signal that we're at the end */
1361       }
1362
1363       /* Add the day of week offset to to the start of this week, and use
1364          that to get the next day */
1365       dow = impl->by_ptrs[BY_DAY][impl->by_indices[BY_DAY]];
1366       start_of_week = icaltime_start_doy_of_week(impl->last);
1367
1368       dow--; /*Sun is 1, not 0 */
1369
1370       if(dow+start_of_week <1 && !end_of_data){
1371           /* The selected date is in the previous year. */
1372           continue;
1373       }
1374
1375       next = icaltime_from_day_of_year(start_of_week + dow,impl->last.year);
1376
1377       impl->last.day =  next.day;
1378       impl->last.month =  next.month;
1379       impl->last.year =  next.year;
1380
1381       return end_of_data;
1382   }
1383
1384 }
1385
1386 int nth_weekday(short dow, short pos, struct icaltimetype t){
1387
1388     short days_in_month = icaltime_days_in_month(t.month,t.year);
1389     short end_dow, start_dow;
1390     short wd;
1391
1392     if(pos >= 0){
1393         t.day = 1;
1394         start_dow = icaltime_day_of_week(t);
1395
1396         if (pos != 0) {
1397             pos--;
1398         }
1399
1400         /* find month day of first occurrence of dow -- such as the
1401            month day of the first monday */
1402
1403         wd = dow-start_dow+1;
1404
1405         if (wd <= 0){
1406             wd = wd + 7;
1407         }
1408
1409         wd = wd + pos * 7;
1410
1411     } else {
1412         t.day = days_in_month;
1413         end_dow = icaltime_day_of_week(t);
1414
1415         pos++;
1416
1417         /* find month day of last occurrence of dow -- such as the
1418            month day of the last monday */
1419
1420         wd = (end_dow - dow);
1421
1422         if (wd < 0){
1423             wd = wd+ 7;
1424         }
1425
1426         wd = days_in_month - wd;
1427
1428         wd = wd + pos * 7;
1429     }
1430
1431     return wd;
1432 }
1433
1434
1435 int next_month(struct icalrecur_iterator_impl* impl)
1436 {
1437     int data_valid = 1;
1438
1439 #ifndef NDEBUG
1440     short this_frequency = (impl->rule.freq == ICAL_MONTHLY_RECURRENCE);
1441
1442     assert( has_by_data(impl,BY_MONTH) || this_frequency);
1443 #endif /* NDEBUG */
1444
1445     /* Iterate through the occurrences within a day. If we don't get to
1446        the end of the intra-day data, don't bother going to the next
1447        month */
1448
1449     if (next_hour(impl) == 0){
1450         return data_valid; /* Signal that the data is valid */
1451     }
1452
1453
1454     /* Now iterate through the occurrences within a month -- by days,
1455        weeks or weekdays.  */
1456
1457     if(has_by_data(impl,BY_DAY) && has_by_data(impl,BY_MONTH_DAY)){
1458       /* Cases like: FREQ=MONTHLY;INTERVAL=1;BYDAY=FR;BYMONTHDAY=13 */
1459       short day, idx,j;
1460       short days_in_month = icaltime_days_in_month(impl->last.month,
1461                                                    impl->last.year);
1462       /* Iterate through the remaining days in the month and check if
1463          each day is listed in the BY_DAY array and in the BY_MONTHDAY
1464          array. This seems very inneficient, but I think it is the
1465          simplest way to account for both BYDAY=1FR (First friday in
1466          month) and BYDAY=FR ( every friday in month ) */
1467
1468       for(day = impl->last.day+1; day <= days_in_month; day++){
1469           for(idx = 0; BYDAYPTR[idx] != ICAL_RECURRENCE_ARRAY_MAX; idx++){
1470               for(j = 0; BYMDPTR[j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
1471                   short dow =
1472                       icalrecurrencetype_day_day_of_week(BYDAYPTR[idx]);
1473                   short pos =  icalrecurrencetype_day_position(BYDAYPTR[idx]);
1474                   short mday = BYMDPTR[j];
1475                   short this_dow;
1476
1477                   impl->last.day = day;
1478                   this_dow = icaltime_day_of_week(impl->last);
1479
1480                   if( (pos == 0 &&  dow == this_dow && mday == day) ||
1481                       (nth_weekday(dow,pos,impl->last) == day && mday==day)){
1482                       goto MDEND;
1483                   }
1484               }
1485           }
1486       }
1487
1488   MDEND:
1489
1490       if ( day > days_in_month){
1491           impl->last.day = 1;
1492           increment_month(impl);
1493           data_valid = 0; /* signal that impl->last is invalid */
1494       }
1495
1496
1497   }  else if(has_by_data(impl,BY_DAY)){
1498       /* Cases like: FREQ=MONTHLY;INTERVAL=1;BYDAY=FR */
1499       /* For this case, the weekdays are relative to the
1500          month. BYDAY=FR -> First Friday in month, etc. */
1501
1502       short day, idx;
1503       short days_in_month = icaltime_days_in_month(impl->last.month,
1504                                                    impl->last.year);
1505
1506       assert( BYDAYPTR[0]!=ICAL_RECURRENCE_ARRAY_MAX);
1507
1508       /* Iterate through the remaining days in the month and check if
1509          each day is listed in the BY_DAY array. This seems very
1510          inneficient, but I think it is the simplest way to account
1511          for both BYDAY=1FR (First friday in month) and BYDAY=FR (
1512          every friday in month ) */
1513
1514       for(day = impl->last.day+1; day <= days_in_month; day++){
1515           for(idx = 0; BYDAYPTR[idx] != ICAL_RECURRENCE_ARRAY_MAX; idx++){
1516               short dow = icalrecurrencetype_day_day_of_week(BYDAYPTR[idx]);
1517               short pos =  icalrecurrencetype_day_position(BYDAYPTR[idx]);
1518               short this_dow;
1519
1520               impl->last.day = day;
1521               this_dow = icaltime_day_of_week(impl->last);
1522
1523               if( (pos == 0 &&  dow == this_dow ) ||
1524                   (nth_weekday(dow,pos,impl->last) == day)){
1525                   goto DEND;
1526               }
1527           }
1528       }
1529
1530   DEND:
1531
1532       if ( day > days_in_month){
1533           impl->last.day = 1;
1534           increment_month(impl);
1535           data_valid = 0; /* signal that impl->last is invalid */
1536       }
1537
1538   } else if (has_by_data(impl,BY_MONTH_DAY)) {
1539       /* Cases like: FREQ=MONTHLY;COUNT=10;BYMONTHDAY=-3  */
1540       short day;
1541
1542       assert( BYMDPTR[0]!=ICAL_RECURRENCE_ARRAY_MAX);
1543
1544       BYMDIDX++;
1545
1546       /* Are we at the end of the BYDAY array? */
1547       if (BYMDPTR[BYMDIDX] ==ICAL_RECURRENCE_ARRAY_MAX){
1548
1549           BYMDIDX = 0; /* Reset to 0 */
1550           increment_month(impl);
1551       }
1552
1553       day = BYMDPTR[BYMDIDX];
1554
1555       if (day < 0) {
1556           day = icaltime_days_in_month(impl->last.month,impl->last.year)+
1557               day + 1;
1558       }
1559
1560       impl->last.day = day;
1561
1562   } else {
1563       increment_month(impl);
1564   }
1565
1566   return data_valid; /* Signal that the data is valid */
1567
1568 }
1569
1570
1571 int next_week(struct icalrecur_iterator_impl* impl)
1572 {
1573   short has_by_data = (impl->by_ptrs[BY_WEEK_NO][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1574   short this_frequency = (impl->rule.freq == ICAL_WEEKLY_RECURRENCE);
1575   short end_of_data = 0;
1576
1577   /* Increment to the next week day */
1578   if (next_weekday_by_week(impl) == 0){
1579       return 0; /* Have not reached end of week yet */
1580   }
1581
1582   /* If we get here, we have incremented through the entire week, and
1583      can increment to the next week */
1584
1585
1586   if( has_by_data){
1587     /* Use the Week Number byrule data */
1588       int week_no;
1589
1590       impl->by_indices[BY_WEEK_NO]++;
1591
1592       if (impl->by_ptrs[BY_WEEK_NO][impl->by_indices[BY_WEEK_NO]]
1593           ==ICAL_RECURRENCE_ARRAY_MAX){
1594           impl->by_indices[BY_WEEK_NO] = 0;
1595
1596           end_of_data = 1;
1597       }
1598
1599       week_no = impl->by_ptrs[BY_WEEK_NO][impl->by_indices[BY_WEEK_NO]];
1600
1601       impl->last.day += week_no*7;
1602
1603       impl->last = icaltime_normalize(impl->last);
1604
1605   } else if( !has_by_data &&  this_frequency ){
1606       /* If there is no BY_WEEK_NO data, just jump forward 7 days. */
1607       increment_monthday(impl,7*impl->rule.interval);
1608   }
1609
1610
1611   if(has_by_data && end_of_data && this_frequency ){
1612       increment_year(impl,1);
1613   }
1614
1615   return end_of_data;
1616
1617 }
1618
1619
1620 pvl_list expand_by_day(struct icalrecur_iterator_impl* impl,short year)
1621 {
1622     /* Try to calculate each of the occurrences. */
1623     int i;
1624     pvl_list days_list = pvl_newlist();
1625
1626     short start_dow, end_year_day, start_doy;
1627     struct icaltimetype tmp = impl->last;
1628
1629     tmp.year= year;
1630     tmp.month = 1;
1631     tmp.day = 1;
1632     tmp.is_date = 1;
1633
1634     start_dow = icaltime_day_of_week(tmp);
1635     start_doy =  icaltime_start_doy_of_week(tmp);
1636
1637     /* Get the last day of the year*/
1638     tmp.year++;
1639     tmp = icaltime_normalize(tmp);
1640     tmp.day--;
1641     tmp = icaltime_normalize(tmp);
1642
1643     end_year_day = icaltime_day_of_year(tmp);
1644
1645     for(i = 0; BYDAYPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
1646         short dow =
1647             icalrecurrencetype_day_day_of_week(BYDAYPTR[i]);
1648         short pos =  icalrecurrencetype_day_position(BYDAYPTR[i]);
1649
1650         if(pos == 0){
1651             /* add all of the days of the year with this day-of-week*/
1652             int week;
1653             for(week = 0; week < 52 ; week ++){
1654                 short doy = start_doy + (week * 7) + dow-1;
1655
1656                 if(doy > end_year_day){
1657                     break;
1658                 } else {
1659                     pvl_push(days_list, GINT_TO_POINTER((int)doy));
1660                 }
1661             }
1662
1663         } else if ( pos > 0) {
1664             int first;
1665             /* First occurrence of dow in year */
1666             if( dow >= start_dow) {
1667                 first = dow - start_dow + 1;
1668             } else {
1669                 first = dow - start_dow + 8;
1670             }
1671
1672             pvl_push(days_list,GINT_TO_POINTER(first+  (pos-1) * 7));
1673
1674         } else { /* pos < 0 */
1675             assert(0);
1676         }
1677     }
1678
1679     return days_list;
1680 }
1681
1682
1683 /* For INTERVAL=YEARLY, set up the days[] array in the iterator to
1684    list all of the days of the current year that are specified in this
1685    rule. */
1686
1687 int expand_year_days(struct icalrecur_iterator_impl* impl,short year)
1688 {
1689     int j,k;
1690     int days_index=0;
1691     struct icaltimetype t;
1692     int flags;
1693
1694 #define HBD(x) has_by_data(impl,x)
1695
1696     t.is_date = 1; /* Needed to make day_of_year routines work property */
1697
1698     memset(&t,0,sizeof(t));
1699     memset(impl->days,ICAL_RECURRENCE_ARRAY_MAX_BYTE,sizeof(impl->days));
1700
1701     flags = (HBD(BY_DAY) ? 1<<BY_DAY : 0) +
1702         (HBD(BY_WEEK_NO) ? 1<<BY_WEEK_NO : 0) +
1703         (HBD(BY_MONTH_DAY) ? 1<<BY_MONTH_DAY : 0) +
1704         (HBD(BY_MONTH) ? 1<<BY_MONTH : 0) +
1705         (HBD(BY_YEAR_DAY) ? 1<<BY_YEAR_DAY : 0);
1706
1707
1708     switch(flags) {
1709
1710     case 0: {
1711         /* FREQ=YEARLY; */
1712
1713         break;
1714     }
1715     case 1<<BY_MONTH: {
1716         /* FREQ=YEARLY; BYMONTH=3,11*/
1717
1718         for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
1719             struct icaltimetype t;
1720             short month = impl->by_ptrs[BY_MONTH][j];
1721             short doy;
1722
1723             t = impl->dtstart;
1724             t.year = year;
1725             t.month = month;
1726             t.is_date = 1;
1727
1728             doy = icaltime_day_of_year(t);
1729
1730             impl->days[days_index++] = doy;
1731
1732         }
1733         break;
1734     }
1735
1736     case 1<<BY_MONTH_DAY:  {
1737         /* FREQ=YEARLY; BYMONTHDAY=1,15*/
1738         assert(0);
1739         break;
1740     }
1741
1742     case (1<<BY_MONTH_DAY) + (1<<BY_MONTH): {
1743         /* FREQ=YEARLY; BYMONTHDAY=1,15; BYMONTH=10 */
1744
1745         for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
1746             for(k=0;impl->by_ptrs[BY_MONTH_DAY][k]!=ICAL_RECURRENCE_ARRAY_MAX;k++){
1747                 short month = impl->by_ptrs[BY_MONTH][j];
1748                 short month_day = impl->by_ptrs[BY_MONTH_DAY][k];
1749                 short doy;
1750
1751                 t.day = month_day;
1752                 t.month = month;
1753                 t.year = year;
1754                 t.is_date = 1;
1755
1756                 doy = icaltime_day_of_year(t);
1757
1758                 impl->days[days_index++] = doy;
1759
1760             }
1761         }
1762
1763         break;
1764     }
1765
1766     case 1<<BY_WEEK_NO: {
1767         /* FREQ=YEARLY; BYWEEKNO=20,50 */
1768
1769         break;
1770     }
1771
1772     case (1<<BY_WEEK_NO) + (1<<BY_MONTH_DAY): {
1773         /*FREQ=YEARLY; WEEKNO=20,50; BYMONTH= 6,11 */
1774         assert(0);
1775         break;
1776     }
1777
1778     case 1<<BY_DAY: {
1779         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR*/
1780         int days_index = 0;
1781         pvl_elem i;
1782         pvl_list days = expand_by_day(impl,year);
1783
1784
1785         for(i=pvl_head(days);i!=0;i=pvl_next(i)){
1786             short day = (short)GPOINTER_TO_INT(pvl_data(i));
1787             impl->days[days_index++] = day;
1788         }
1789         pvl_free(days);
1790         break;
1791     }
1792
1793     case (1<<BY_DAY)+(1<<BY_MONTH): {
1794         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTH = 12*/
1795
1796
1797         for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
1798             short month = impl->by_ptrs[BY_MONTH][j];
1799             short days_in_month = icaltime_days_in_month(month,year);
1800
1801             struct icaltimetype t;
1802             memset(&t,0,sizeof(struct icaltimetype));
1803             t.day = 1;
1804             t.year = year;
1805             t.month = month;
1806             t.is_date = 1;
1807
1808             for(t.day = 1; t.day <=days_in_month; t.day++){
1809
1810                 short current_dow = icaltime_day_of_week(t);
1811
1812                 for(k=0;impl->by_ptrs[BY_DAY][k]!=ICAL_RECURRENCE_ARRAY_MAX;k++){
1813
1814                     enum icalrecurrencetype_weekday dow =
1815                         icalrecurrencetype_day_day_of_week(impl->by_ptrs[BY_DAY][k]);
1816
1817                     if(current_dow == dow){
1818                         short doy = icaltime_day_of_year(t);
1819                         /* HACK, incomplete Nth day of week handling */
1820                         impl->days[days_index++] = doy;
1821
1822                     }
1823                 }
1824             }
1825         }
1826         break;
1827     }
1828
1829     case (1<<BY_DAY) + (1<<BY_MONTH_DAY) : {
1830         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTHDAY=1,15*/
1831         assert(0);
1832         break;
1833     }
1834
1835     case (1<<BY_DAY) + (1<<BY_MONTH_DAY) + (1<<BY_MONTH): {
1836         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTHDAY=10; MYMONTH=6,11*/
1837
1838         int days_index = 0;
1839         pvl_elem itr;
1840         pvl_list days = expand_by_day(impl,year);
1841
1842         for(itr=pvl_head(days);itr!=0;itr=pvl_next(itr)){
1843             short day = (short)GPOINTER_TO_INT(pvl_data(itr));
1844             struct icaltimetype tt;
1845             short i,j;
1846
1847             tt = icaltime_from_day_of_year(day,year);
1848
1849             for(i = 0; BYMONPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
1850                 for(j = 0; BYMDPTR[j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
1851                     short mday = BYMDPTR[j];
1852                     short month = BYMONPTR[i];
1853
1854                     if(tt.month == month  && tt.day == mday){
1855                         impl->days[days_index++] = day;
1856                     }
1857                 }
1858             }
1859         }
1860         pvl_free(days);
1861
1862        break;
1863
1864     }
1865
1866     case (1<<BY_DAY) + (1<<BY_WEEK_NO) : {
1867         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR;  WEEKNO=20,50*/
1868
1869         int days_index = 0;
1870         pvl_elem itr;
1871         pvl_list days = expand_by_day(impl,year);
1872
1873         for(itr=pvl_head(days);itr!=0;itr=pvl_next(itr)){
1874             short day = (short)GPOINTER_TO_INT(pvl_data(itr));
1875             struct icaltimetype tt;
1876             short i;
1877
1878             tt = icaltime_from_day_of_year(day,year);
1879
1880             for(i = 0; BYWEEKPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
1881                     short weekno = BYWEEKPTR[i];
1882
1883                     if(weekno== icaltime_week_number(tt)){
1884                         impl->days[days_index++] = day;
1885                     }
1886             }
1887
1888         }
1889         pvl_free(days);
1890         break;
1891     }
1892
1893     case (1<<BY_DAY) + (1<<BY_WEEK_NO) + (1<<BY_MONTH_DAY): {
1894         /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR;  WEEKNO=20,50; BYMONTHDAY=1,15*/
1895         assert(0);
1896         break;
1897     }
1898
1899     case 1<<BY_YEAR_DAY: {
1900         for(j=0;impl->by_ptrs[BY_YEAR_DAY][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
1901             short doy = impl->by_ptrs[BY_YEAR_DAY][j];
1902             impl->days[days_index++] = doy;
1903         }
1904         break;
1905     }
1906
1907     default: {
1908         assert(0);
1909         break;
1910     }
1911
1912     }
1913
1914     return 0;
1915 }
1916
1917
1918 int next_year(struct icalrecur_iterator_impl* impl)
1919 {
1920     struct icaltimetype next;
1921
1922     if (next_hour(impl) == 0){
1923         return 0;
1924     }
1925
1926     if (impl->days[++impl->days_index] == ICAL_RECURRENCE_ARRAY_MAX){
1927         impl->days_index = 0;
1928         increment_year(impl,impl->rule.interval);
1929         expand_year_days(impl,impl->last.year);
1930     }
1931
1932     next = icaltime_from_day_of_year(impl->days[impl->days_index],impl->last.year);
1933
1934     impl->last.day =  next.day;
1935     impl->last.month =  next.month;
1936
1937     return 1;
1938 }
1939
1940 int icalrecur_check_rulepart(struct icalrecur_iterator_impl* impl,
1941                       short v, enum byrule byrule)
1942 {
1943     int itr;
1944
1945     if(impl->by_ptrs[byrule][0]!=ICAL_RECURRENCE_ARRAY_MAX){
1946         for(itr=0; impl->by_ptrs[byrule][itr]!=ICAL_RECURRENCE_ARRAY_MAX;itr++){
1947             if(impl->by_ptrs[byrule][itr] == v){
1948                 return 1;
1949             }
1950         }
1951     }
1952
1953     return 0;
1954 }
1955
1956 int check_contract_restriction(struct icalrecur_iterator_impl* impl,
1957                       enum byrule byrule, short v)
1958 {
1959     int pass = 0;
1960     int itr;
1961     icalrecurrencetype_frequency freq = impl->rule.freq;
1962
1963     if(impl->by_ptrs[byrule][0]!=ICAL_RECURRENCE_ARRAY_MAX &&
1964         expand_map[freq].map[byrule] == CONTRACT){
1965         for(itr=0; impl->by_ptrs[byrule][itr]!=ICAL_RECURRENCE_ARRAY_MAX;itr++){
1966             if(impl->by_ptrs[byrule][itr] == v){
1967                 pass=1;
1968                 break;
1969             }
1970         }
1971
1972         return pass;
1973     } else {
1974         /* This is not a contracting byrule, or it has no data, so the
1975            test passes*/
1976         return 1;
1977     }
1978 }
1979
1980
1981 int check_contracting_rules(struct icalrecur_iterator_impl* impl)
1982 {
1983
1984     int day_of_week=0;
1985     int week_no=0;
1986     int year_day=0;
1987
1988     if (
1989         check_contract_restriction(impl,BY_SECOND,impl->last.second) &&
1990         check_contract_restriction(impl,BY_MINUTE,impl->last.minute) &&
1991         check_contract_restriction(impl,BY_HOUR,impl->last.hour) &&
1992         check_contract_restriction(impl,BY_DAY,day_of_week) &&
1993         check_contract_restriction(impl,BY_WEEK_NO,week_no) &&
1994         check_contract_restriction(impl,BY_MONTH_DAY,impl->last.day) &&
1995         check_contract_restriction(impl,BY_MONTH,impl->last.month) &&
1996         check_contract_restriction(impl,BY_YEAR_DAY,year_day) )
1997     {
1998
1999         return 1;
2000     } else {
2001         return 0;
2002     }
2003 }
2004
2005 struct icaltimetype icalrecur_iterator_next(icalrecur_iterator *itr)
2006 {
2007     int valid = 1;
2008     struct icalrecur_iterator_impl* impl =
2009         (struct icalrecur_iterator_impl*)itr;
2010
2011     if( (impl->rule.count!=0 &&impl->occurrence_no >= impl->rule.count) ||
2012        (!icaltime_is_null_time(impl->rule.until) &&
2013         icaltime_compare(impl->last,impl->rule.until) > 0)) {
2014         return icaltime_null_time();
2015     }
2016
2017     if(impl->occurrence_no == 0
2018        &&  icaltime_compare(impl->last,impl->dtstart) >= 0){
2019
2020         impl->occurrence_no++;
2021         return impl->last;
2022     }
2023
2024     do {
2025         valid = 1;
2026         switch(impl->rule.freq){
2027
2028             case ICAL_SECONDLY_RECURRENCE: {
2029                 next_second(impl);
2030                 break;
2031             }
2032             case ICAL_MINUTELY_RECURRENCE: {
2033                 next_minute(impl);
2034                 break;
2035             }
2036             case ICAL_HOURLY_RECURRENCE: {
2037                 next_hour(impl);
2038                 break;
2039             }
2040             case ICAL_DAILY_RECURRENCE: {
2041                 next_day(impl);
2042                 break;
2043             }
2044             case ICAL_WEEKLY_RECURRENCE: {
2045                 next_week(impl);
2046                 break;
2047             }
2048             case ICAL_MONTHLY_RECURRENCE: {
2049                 valid = next_month(impl);
2050                 break;
2051             }
2052             case ICAL_YEARLY_RECURRENCE:{
2053                 next_year(impl);
2054                 break;
2055             }
2056             default:{
2057                 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
2058                 return icaltime_null_time();
2059             }
2060         }
2061
2062         if(impl->last.year >= 2038 ){
2063             /* HACK */
2064             return icaltime_null_time();
2065         }
2066
2067     } while(!check_contracting_rules(impl)
2068             || icaltime_compare(impl->last,impl->dtstart) < 0
2069             || valid == 0);
2070
2071
2072 /* Ignore null times and times that are after the until time */
2073     if( !icaltime_is_null_time(impl->rule.until) &&
2074         icaltime_compare(impl->last,impl->rule.until) > 0 ) {
2075         return icaltime_null_time();
2076     }
2077
2078     impl->occurrence_no++;
2079
2080     return impl->last;
2081 }
2082
2083
2084 /************************** Type Routines **********************/
2085
2086
2087 void icalrecurrencetype_clear(struct icalrecurrencetype *recur)
2088 {
2089     memset(recur,ICAL_RECURRENCE_ARRAY_MAX_BYTE,
2090            sizeof(struct icalrecurrencetype));
2091
2092     recur->week_start = ICAL_MONDAY_WEEKDAY;
2093     recur->freq = ICAL_NO_RECURRENCE;
2094     recur->interval = 1;
2095     memset(&(recur->until),0,sizeof(struct icaltimetype));
2096     recur->count = 0;
2097 }
2098
2099 /* The 'day' element of icalrecurrencetype_weekday is encoded to allow
2100 reporesentation of both the day of the week ( Monday, Tueday), but
2101 also the Nth day of the week ( First tuesday of the month, last
2102 thursday of the year) These routines decode the day values.
2103
2104 The day's position in the period ( Nth-ness) and the numerical value
2105 of the day are encoded together as: pos*7 + dow
2106
2107 A position of 0 means 'any' or 'every'
2108
2109  */
2110
2111 enum icalrecurrencetype_weekday icalrecurrencetype_day_day_of_week(short day)
2112 {
2113     return abs(day)%8;
2114 }
2115
2116 short icalrecurrencetype_day_position(short day)
2117 {
2118     short wd, pos;
2119
2120     wd = icalrecurrencetype_day_day_of_week(day);
2121
2122     pos = (abs(day)-wd)/8 * ((day<0)?-1:1);
2123
2124
2125     return pos;
2126 }
2127
2128
2129 /****************** Enumeration Routines ******************/
2130
2131 struct {icalrecurrencetype_weekday wd; const char * str; }
2132 wd_map[] = {
2133     {ICAL_SUNDAY_WEEKDAY,"SU"},
2134     {ICAL_MONDAY_WEEKDAY,"MO"},
2135     {ICAL_TUESDAY_WEEKDAY,"TU"},
2136     {ICAL_WEDNESDAY_WEEKDAY,"WE"},
2137     {ICAL_THURSDAY_WEEKDAY,"TH"},
2138     {ICAL_FRIDAY_WEEKDAY,"FR"},
2139     {ICAL_SATURDAY_WEEKDAY,"SA"},
2140     {ICAL_NO_WEEKDAY,0}
2141 };
2142
2143 const char* icalrecur_weekday_to_string(icalrecurrencetype_weekday kind)
2144 {
2145     int i;
2146
2147     for (i=0; wd_map[i].wd  != ICAL_NO_WEEKDAY; i++) {
2148         if ( wd_map[i].wd ==  kind) {
2149             return wd_map[i].str;
2150         }
2151     }
2152
2153     return 0;
2154 }
2155
2156 icalrecurrencetype_weekday icalrecur_string_to_weekday(const char* str)
2157 {
2158     int i;
2159
2160     for (i=0; wd_map[i].wd  != ICAL_NO_WEEKDAY; i++) {
2161         if ( strcmp(str,wd_map[i].str) == 0){
2162             return wd_map[i].wd;
2163         }
2164     }
2165
2166     return ICAL_NO_WEEKDAY;
2167 }
2168
2169
2170
2171 struct {
2172         icalrecurrencetype_frequency kind;
2173         const char* str;
2174 } freq_map[] = {
2175     {ICAL_SECONDLY_RECURRENCE,"SECONDLY"},
2176     {ICAL_MINUTELY_RECURRENCE,"MINUTELY"},
2177     {ICAL_HOURLY_RECURRENCE,"HOURLY"},
2178     {ICAL_DAILY_RECURRENCE,"DAILY"},
2179     {ICAL_WEEKLY_RECURRENCE,"WEEKLY"},
2180     {ICAL_MONTHLY_RECURRENCE,"MONTHLY"},
2181     {ICAL_YEARLY_RECURRENCE,"YEARLY"},
2182     {ICAL_NO_RECURRENCE,0}
2183 };
2184
2185 const char* icalrecur_freq_to_string(icalrecurrencetype_frequency kind)
2186 {
2187     int i;
2188
2189     for (i=0; freq_map[i].kind != ICAL_NO_RECURRENCE ; i++) {
2190         if ( freq_map[i].kind == kind ) {
2191             return freq_map[i].str;
2192         }
2193     }
2194     return 0;
2195 }
2196
2197 icalrecurrencetype_frequency icalrecur_string_to_freq(const char* str)
2198 {
2199     int i;
2200
2201     for (i=0; freq_map[i].kind != ICAL_NO_RECURRENCE ; i++) {
2202         if ( strcmp(str,freq_map[i].str) == 0){
2203             return freq_map[i].kind;
2204         }
2205     }
2206     return ICAL_NO_RECURRENCE;
2207 }
2208
2209 /* Fill an array with the 'count' number of occurrences generated by
2210    the rrule. Note that the times are returned in UTC, but the times
2211    are calculated in local time. YOu will have to convert the results
2212    back into local time before using them. */
2213
2214 int icalrecur_expand_recurrence(char* rule, time_t start,
2215                                 int count, time_t* array)
2216 {
2217     struct icalrecurrencetype recur;
2218     icalrecur_iterator* ritr;
2219     time_t tt;
2220     struct icaltimetype icstart, next;
2221     int i = 0;
2222
2223     memset(array, 0, count*sizeof(time_t));
2224
2225     icstart = icaltime_from_timet(start,0);
2226
2227     recur = icalrecurrencetype_from_string(rule);
2228
2229     for(ritr = icalrecur_iterator_new(recur,icstart),
2230         next = icalrecur_iterator_next(ritr);
2231         !icaltime_is_null_time(next) && i < count;
2232         next = icalrecur_iterator_next(ritr)){
2233
2234         tt = icaltime_as_timet(next);
2235
2236         if (tt >= start ){
2237             array[i++] = tt;
2238         }
2239
2240     }
2241
2242     icalrecur_iterator_free(ritr);
2243
2244     return 1;
2245 }