added test-recur test program.

2000-05-31  Damon Chaplin  <damon@helixcode.com>

        * cal-util/Makefile.am: added test-recur test program.

        * cal-util/test-recur.c: new file to test the recurrence code.

        * cal-util/.cvsignore: added test-recur.

        * cal-util/cal-recur.c: updated.

svn path=/trunk/; revision=3315

6 files changed, 1879 insertions, 347 deletions

diff --git a/calendar/ChangeLog b/calendar/ChangeLog
index 2905f6774f..6a913637af 100644
--- a/calendar/ChangeLog
+++ b/calendar/ChangeLog
@@ -1,3 +1,13 @@
+2000-05-31  Damon Chaplin  <damon@helixcode.com>
+
+	* cal-util/Makefile.am: added test-recur test program.
+
+	* cal-util/test-recur.c: new file to test the recurrence code.
+
+	* cal-util/.cvsignore: added test-recur.
+
+	* cal-util/cal-recur.c: updated.
+
 2000-05-30  Federico Mena Quintero  <federico@helixcode.com>
 
 	* gui/event-editor.c (event_editor_construct): Create the UI
diff --git a/calendar/cal-util/.cvsignore b/calendar/cal-util/.cvsignore
index fe97f9aa2c..9f93120f8a 100644
--- a/calendar/cal-util/.cvsignore
+++ b/calendar/cal-util/.cvsignore
@@ -4,3 +4,4 @@ Makefile
 .deps
 *.lo
 *.la
+test-recur
diff --git a/calendar/cal-util/Makefile.am b/calendar/cal-util/Makefile.am
index f110e96394..d3517c2102 100644
--- a/calendar/cal-util/Makefile.am
+++ b/calendar/cal-util/Makefile.am
@@ -1,3 +1,6 @@
+
+noinst_PROGRAMS = test-recur
+
 INCLUDES =						\
         -DGNOMELOCALEDIR=\""$(datadir)/locale"\"	\
 	-DG_LOG_DOMAIN=\"cal-util\"			\
@@ -23,3 +26,13 @@ libcal_utilinclude_HEADERS =	\
 	cal-util.h		\
 	calobj.h		\
 	timeutil.h
+
+
+test_recur_SOURCES = 	\
+	test-recur.c
+
+test_recur_LDADD = 	\
+	libcal-util.la	\
+	$(top_builddir)/libversit/libversit.la		\
+	$(top_builddir)/libical/src/libical/libical.la	\
+	$(EXTRA_GNOME_LIBS)
diff --git a/calendar/cal-util/cal-recur.c b/calendar/cal-util/cal-recur.c
index 711ef5e64d..e3a0872934 100644
--- a/calendar/cal-util/cal-recur.c
+++ b/calendar/cal-util/cal-recur.c
@@ -21,8 +21,10 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  */
 
+#include <config.h>
 #include <stdlib.h>
 #include <string.h>
+#include <cal-util/calobj.h>
 #include <cal-util/cal-recur.h>
 #include <cal-util/timeutil.h>
 
@@ -46,26 +48,38 @@
  *
  * o There are 7 frequencies of occurrences: YEARLY, MONTHLY, WEEKLY, DAILY,
  *   HOURLY, MINUTELY & SECONDLY. The 'interval' property specifies the
- *   multiples of the frequency between each 'set' of occurrences. So for
- *   a YEARLY frequency with an interval of 3, we generate a set of occurrences
- *   for every 3rd year. We use complete years here -  any generated
- *   occurrences that occur before the event's start (or after its end)
- *   are just discarded.
+ *   multiples of the frequency which we step by. We generate a 'set' of
+ *   occurrences for each period defined by the frequency & interval.
+ *   So for a YEARLY frequency with an interval of 3, we generate a set of
+ *   occurrences for every 3rd year. We use complete years here -  any
+ *   generated occurrences that occur before the event's start (or after its
+ *   end) are just discarded.
  *
  * o There are 8 frequency modifiers: BYMONTH, BYWEEKNO, BYYEARDAY, BYMONTHDAY,
- *   BYDAY, BYHOUR & BYSECOND. These can either add extra occurrences or
- *   filter out occurrences. For example 'FREQ=YEARLY;BYMONTH=1,2' produces
+ *   BYDAY, BYHOUR, BYMINUTE & BYSECOND. These can either add extra occurrences
+ *   or filter out occurrences. For example 'FREQ=YEARLY;BYMONTH=1,2' produces
  *   2 occurrences for each year rather than the default 1. And
- *   'FREQ=DAILY; BYMONTH=1' filters out all occurrences except those in Jan.
+ *   'FREQ=DAILY;BYMONTH=1' filters out all occurrences except those in Jan.
  *   If the modifier works on periods which are less than the recurrence
- *   frequency, then extra occurrences are added, else occurrences are
+ *   frequency, then extra occurrences are added, otherwise occurrences are
  *   filtered. So we have 2 functions for each modifier - one to expand events
  *   and the other to filter. We use a table of functions for each frequency
  *   which points to the appropriate function to use for each modifier.
  *
- * o Any number of frequency modifiers can be used in a recurrence rule
- *   (though BYWEEKNO can only be used in a YEARLY rule). They are applied in
- *   the order given above.
+ * o Any number of frequency modifiers can be used in a recurrence rule.
+ *   (Though the iCalendar spec says that BYWEEKNO can only be used in a YEARLY
+ *   rule, and some modifiers aren't appropriate for some frequencies - e.g.
+ *   BYMONTHDAY is not really useful in a WEEKLY frequency, and BYYEARDAY is
+ *   not useful in a MONTHLY or WEEKLY frequency).
+ *   The frequency modifiers are applied in the order given above. The first 5
+ *   modifier rules (BYMONTH, BYWEEKNO, BYYEARDAY, BYMONTHDAY & BYDAY) all
+ *   produce the days on which the occurrences take place, and so we have to
+ *   compute some of these in parallel rather than sequentially, or we may end
+ *   up with too many days.
+ *
+ * o Note that some expansion functions may produce days which are invalid,
+ *   e.g. 31st September, 30th Feb. These invalid days are removed before the
+ *   BYHOUR, BYMINUTE & BYSECOND modifier functions are applied.
  *
  * o After the set of occurrences for the frequency interval are generated,
  *   the BYSETPOS property is used to select which of the occurrences are
@@ -74,286 +88,435 @@
  */
 
 
-#define CAL_OBJ_NUM_FILTERS	8
+/* This is what we use to pass to all the filter functions. */
+typedef struct _RecurData RecurData;
+struct _RecurData {
+	CalObjRecurrence *recur;
+
+	/* This is used for the WEEKLY frequency. */
+	gint weekday;
+
+	/* This is used for fast lookup in BYMONTH filtering. */
+	guint8 months[12];
+
+	/* This is used for fast lookup in BYYEARDAY filtering. */
+	guint8 yeardays[367], neg_yeardays[367]; /* Days are 1 - 366. */
+
+	/* This is used for fast lookup in BYMONTHDAY filtering. */
+	guint8 monthdays[32], neg_monthdays[32]; /* Days are 1 to 31. */
+
+	/* This is used for fast lookup in BYDAY filtering. */
+	guint8 weekdays[7];
+
+	/* This is used for fast lookup in BYHOUR filtering. */
+	guint8 hours[24];
+
+	/* This is used for fast lookup in BYMINUTE filtering. */
+	guint8 minutes[60];
+
+	/* This is used for fast lookup in BYSECOND filtering. */
+	guint8 seconds[61];
+};
+
+
 
 typedef gboolean (*CalObjFindStartFn) (CalObjTime *event_start,
 				       CalObjTime *event_end,
-				       Recurrence *recur,
+				       RecurData  *recur_data,
 				       CalObjTime *interval_start,
 				       CalObjTime *interval_end,
 				       CalObjTime *cotime);
 typedef gboolean (*CalObjFindNextFn)  (CalObjTime *cotime,
 				       CalObjTime *event_end,
-				       Recurrence *recur,
+				       RecurData  *recur_data,
 				       CalObjTime *interval_end);
-typedef GArray* (*CalObjFilterFn)    (Recurrence *recur,
-				      GArray     *occs);
+typedef GArray*	 (*CalObjFilterFn)    (RecurData  *recur_data,
+				       GArray     *occs);
 
 typedef struct _CalObjRecurVTable CalObjRecurVTable;
 struct _CalObjRecurVTable {
 	CalObjFindStartFn find_start_position;
 	CalObjFindNextFn find_next_position;
-	CalObjFilterFn filters[CAL_OBJ_NUM_FILTERS];
+
+	CalObjFilterFn bymonth_filter;
+	CalObjFilterFn byweekno_filter;
+	CalObjFilterFn byyearday_filter;
+	CalObjFilterFn bymonthday_filter;
+	CalObjFilterFn byday_filter;
+	CalObjFilterFn byhour_filter;
+	CalObjFilterFn byminute_filter;
+	CalObjFilterFn bysecond_filter;
 };
 
 
-static CalObjRecurVTable* cal_obj_get_vtable (Recurrence *recur);
-static void cal_obj_sort_occurrences (GArray *occs);
-static gint cal_obj_time_compare_func (const void *arg1,
-				       const void *arg2);
-static void cal_obj_remove_duplicates (GArray *occs);
-static GArray* cal_obj_bysetpos_filter (GArray *occs);
+/* This is used to specify which parts of the CalObjTime to compare in
+   cal_obj_time_compare(). */
+typedef enum {
+	CALOBJ_YEAR,
+	CALOBJ_MONTH,
+	CALOBJ_DAY,
+	CALOBJ_HOUR,
+	CALOBJ_MINUTE,
+	CALOBJ_SECOND
+} CalObjTimeComparison;
+
+static GArray*	cal_obj_generate_set_yearly	(RecurData	*recur_data,
+						 CalObjRecurVTable *vtable,
+						 CalObjTime	*occ);
+static GArray*	cal_obj_generate_set_monthly	(RecurData	*recur_data,
+						 CalObjRecurVTable *vtable,
+						 CalObjTime	*occ);
+static GArray*	cal_obj_generate_set_default	(RecurData	*recur_data,
+						 CalObjRecurVTable *vtable,
+						 CalObjTime	*occ);
+
+
+static CalObjRecurVTable* cal_obj_get_vtable	(CalObjRecurType	 recur_type);
+static void	cal_obj_initialize_recur_data	(RecurData	*recur_data,
+						 CalObjRecurrence	*recur,
+						 CalObjTime	*event_start);
+static void	cal_obj_sort_occurrences	(GArray		*occs);
+static gint	cal_obj_time_compare_func	(const void	*arg1,
+						 const void	*arg2);
+static void	cal_obj_remove_duplicates_and_invalid_dates (GArray	*occs);
+static GArray*	cal_obj_bysetpos_filter		(CalObjRecurrence	*recur,
+						 GArray		*occs);
 
 
 static gboolean cal_obj_yearly_find_start_position (CalObjTime *event_start,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_start,
 						    CalObjTime *interval_end,
 						    CalObjTime *cotime);
 static gboolean cal_obj_yearly_find_next_position  (CalObjTime *cotime,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_end);
 
 static gboolean cal_obj_monthly_find_start_position (CalObjTime *event_start,
 						     CalObjTime *event_end,
-						     Recurrence *recur,
+						     RecurData  *recur_data,
 						     CalObjTime *interval_start,
 						     CalObjTime *interval_end,
 						     CalObjTime *cotime);
 static gboolean cal_obj_monthly_find_next_position  (CalObjTime *cotime,
 						     CalObjTime *event_end,
-						     Recurrence *recur,
+						     RecurData  *recur_data,
 						     CalObjTime *interval_end);
 
 static gboolean cal_obj_weekly_find_start_position (CalObjTime *event_start,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_start,
 						    CalObjTime *interval_end,
 						    CalObjTime *cotime);
 static gboolean cal_obj_weekly_find_next_position  (CalObjTime *cotime,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_end);
 
 static gboolean cal_obj_daily_find_start_position  (CalObjTime *event_start,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_start,
 						    CalObjTime *interval_end,
 						    CalObjTime *cotime);
 static gboolean cal_obj_daily_find_next_position   (CalObjTime *cotime,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_end);
 
 static gboolean cal_obj_hourly_find_start_position (CalObjTime *event_start,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_start,
 						    CalObjTime *interval_end,
 						    CalObjTime *cotime);
 static gboolean cal_obj_hourly_find_next_position  (CalObjTime *cotime,
 						    CalObjTime *event_end,
-						    Recurrence *recur,
+						    RecurData  *recur_data,
 						    CalObjTime *interval_end);
 
 static gboolean cal_obj_minutely_find_start_position (CalObjTime *event_start,
 						      CalObjTime *event_end,
-						      Recurrence *recur,
+						      RecurData  *recur_data,
 						      CalObjTime *interval_start,
 						      CalObjTime *interval_end,
 						      CalObjTime *cotime);
 static gboolean cal_obj_minutely_find_next_position  (CalObjTime *cotime,
 						      CalObjTime *event_end,
-						      Recurrence *recur,
+						      RecurData  *recur_data,
 						      CalObjTime *interval_end);
 
 static gboolean cal_obj_secondly_find_start_position (CalObjTime *event_start,
 						      CalObjTime *event_end,
-						      Recurrence *recur,
+						      RecurData  *recur_data,
 						      CalObjTime *interval_start,
 						      CalObjTime *interval_end,
 						      CalObjTime *cotime);
 static gboolean cal_obj_secondly_find_next_position  (CalObjTime *cotime,
 						      CalObjTime *event_end,
-						      Recurrence *recur,
+						      RecurData  *recur_data,
 						      CalObjTime *interval_end);
 
-static GArray* cal_obj_bymonth_expand		(Recurrence *recur,
+static GArray* cal_obj_bymonth_expand		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_bymonth_filter		(Recurrence *recur,
+static GArray* cal_obj_bymonth_filter		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byweekno_expand		(Recurrence *recur,
+static GArray* cal_obj_byweekno_expand		(RecurData  *recur_data,
 						 GArray     *occs);
 #if 0
 /* This isn't used at present. */
-static GArray* cal_obj_byweekno_filter		(Recurrence *recur,
+static GArray* cal_obj_byweekno_filter		(RecurData  *recur_data,
 						 GArray     *occs);
 #endif
-static GArray* cal_obj_byyearday_expand		(Recurrence *recur,
+static GArray* cal_obj_byyearday_expand		(RecurData  *recur_data,
+						 GArray     *occs);
+static GArray* cal_obj_byyearday_filter		(RecurData  *recur_data,
+						 GArray     *occs);
+static GArray* cal_obj_bymonthday_expand	(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byyearday_filter		(Recurrence *recur,
+static GArray* cal_obj_bymonthday_filter	(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_bymonthday_expand	(Recurrence *recur,
+static GArray* cal_obj_byday_expand_yearly	(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_bymonthday_filter	(Recurrence *recur,
+static GArray* cal_obj_byday_expand_monthly	(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byday_expand		(Recurrence *recur,
+static GArray* cal_obj_byday_expand_weekly	(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byday_filter		(Recurrence *recur,
+static GArray* cal_obj_byday_filter		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byhour_expand		(Recurrence *recur,
+static GArray* cal_obj_byhour_expand		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byhour_filter		(Recurrence *recur,
+static GArray* cal_obj_byhour_filter		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byminute_expand		(Recurrence *recur,
+static GArray* cal_obj_byminute_expand		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_byminute_filter		(Recurrence *recur,
+static GArray* cal_obj_byminute_filter		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_bysecond_expand		(Recurrence *recur,
+static GArray* cal_obj_bysecond_expand		(RecurData  *recur_data,
 						 GArray     *occs);
-static GArray* cal_obj_bysecond_filter		(Recurrence *recur,
+static GArray* cal_obj_bysecond_filter		(RecurData  *recur_data,
 						 GArray     *occs);
 
-static void cal_obj_time_add_days (CalObjTime *cotime,
-				   gint	       days);
+static void cal_obj_time_add_months		(CalObjTime *cotime,
+						 gint	     months);
+static void cal_obj_time_add_days		(CalObjTime *cotime,
+						 gint	     days);
+static void cal_obj_time_subtract_days		(CalObjTime *cotime,
+						 gint	     days);
+static void cal_obj_time_add_hours		(CalObjTime *cotime,
+						 gint	     hours);
+static void cal_obj_time_add_minutes		(CalObjTime *cotime,
+						 gint	     minutes);
+static void cal_obj_time_add_seconds		(CalObjTime *cotime,
+						 gint	     seconds);
+static gint cal_obj_time_compare		(CalObjTime *cotime1,
+						 CalObjTime *cotime2,
+						 CalObjTimeComparison type);
+static gint cal_obj_time_weekday		(CalObjTime *cotime,
+						 CalObjRecurrence *recur);
+static gint cal_obj_time_day_of_year		(CalObjTime *cotime);
+static void cal_obj_time_find_first_week	(CalObjTime *cotime,
+						 RecurData  *recur_data);
 
 
 CalObjRecurVTable cal_obj_yearly_vtable = {
 	cal_obj_yearly_find_start_position,
 	cal_obj_yearly_find_next_position,
-	{
-		cal_obj_bymonth_expand,
-		cal_obj_byweekno_expand,
-		cal_obj_byyearday_expand,
-		cal_obj_bymonthday_expand,
-		cal_obj_byday_expand,
-		cal_obj_byhour_expand,
-		cal_obj_byminute_expand,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_expand,
+	cal_obj_byweekno_expand,
+	cal_obj_byyearday_expand,
+	cal_obj_bymonthday_expand,
+	cal_obj_byday_expand_yearly,
+	cal_obj_byhour_expand,
+	cal_obj_byminute_expand,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_monthly_vtable = {
 	cal_obj_monthly_find_start_position,
 	cal_obj_monthly_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_expand,
-		cal_obj_byday_expand,
-		cal_obj_byhour_expand,
-		cal_obj_byminute_expand,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	NULL, /* BYYEARDAY is not useful in a MONTHLY frequency. */
+	cal_obj_bymonthday_expand,
+	cal_obj_byday_expand_monthly,
+	cal_obj_byhour_expand,
+	cal_obj_byminute_expand,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_weekly_vtable = {
 	cal_obj_weekly_find_start_position,
 	cal_obj_weekly_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_filter,
-		cal_obj_byday_expand,
-		cal_obj_byhour_expand,
-		cal_obj_byminute_expand,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	NULL, /* BYYEARDAY is not useful in a WEEKLY frequency. */
+	NULL, /* BYMONTHDAY is not useful in a WEEKLY frequency. */
+	cal_obj_byday_expand_weekly,
+	cal_obj_byhour_expand,
+	cal_obj_byminute_expand,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_daily_vtable = {
 	cal_obj_daily_find_start_position,
 	cal_obj_daily_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_filter,
-		cal_obj_byday_filter,
-		cal_obj_byhour_expand,
-		cal_obj_byminute_expand,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	cal_obj_byyearday_filter,
+	cal_obj_bymonthday_filter,
+	cal_obj_byday_filter,
+	cal_obj_byhour_expand,
+	cal_obj_byminute_expand,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_hourly_vtable = {
 	cal_obj_hourly_find_start_position,
 	cal_obj_hourly_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_filter,
-		cal_obj_byday_filter,
-		cal_obj_byhour_filter,
-		cal_obj_byminute_expand,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	cal_obj_byyearday_filter,
+	cal_obj_bymonthday_filter,
+	cal_obj_byday_filter,
+	cal_obj_byhour_filter,
+	cal_obj_byminute_expand,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_minutely_vtable = {
 	cal_obj_minutely_find_start_position,
 	cal_obj_minutely_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_filter,
-		cal_obj_byday_filter,
-		cal_obj_byhour_filter,
-		cal_obj_byminute_filter,
-		cal_obj_bysecond_expand
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	cal_obj_byyearday_filter,
+	cal_obj_bymonthday_filter,
+	cal_obj_byday_filter,
+	cal_obj_byhour_filter,
+	cal_obj_byminute_filter,
+	cal_obj_bysecond_expand
 };
 
 CalObjRecurVTable cal_obj_secondly_vtable = {
 	cal_obj_secondly_find_start_position,
 	cal_obj_secondly_find_next_position,
-	{
-		cal_obj_bymonth_filter,
-		NULL,
-		cal_obj_byyearday_filter,
-		cal_obj_bymonthday_filter,
-		cal_obj_byday_filter,
-		cal_obj_byhour_filter,
-		cal_obj_byminute_filter,
-		cal_obj_bysecond_filter
-	},
+
+	cal_obj_bymonth_filter,
+	NULL, /* BYWEEKNO is only applicable to YEARLY frequency. */
+	cal_obj_byyearday_filter,
+	cal_obj_bymonthday_filter,
+	cal_obj_byday_filter,
+	cal_obj_byhour_filter,
+	cal_obj_byminute_filter,
+	cal_obj_bysecond_filter
 };
 
 
 
+/*
+ * Calls the given callback function for each occurrence of the event between
+ * the given start and end times. If end is 0 it continues until the event
+ * ends or forever if the event has an infinite recurrence rule.
+ * If the callback routine return 0 the occurrence generation stops.
+ *
+ * NOTE: This could replace ical_object_generate_events() eventually.
+ */
+void
+cal_object_generate_events (iCalObject	*ico,
+			    time_t	 start,
+			    time_t	 end,
+			    calendarfn   cb,
+			    void	*closure)
+{
+
+	/* FIXME: The iCalObject should have a list of RRULES & RDATES and a
+	   list of EXRULES & EXDATES. */
+
+
+	/* If there is no recurrence, just call the callback if the event
+	   intersects the given interval. */
+	if (!ico->recur) {
+		if ((end && (ico->dtstart < end) && (ico->dtend > start))
+		    || ((end == 0) && (ico->dtend > start))) {
+			(* cb) (ico, ico->dtstart, ico->dtend, closure);
+		}
+		return;
+	}
+
+
+	/* Expand each of the recurrence rules. */
+
+
+
+	/* Add on specific occurrence dates. */
+
+
+	/* Expand each of the exception rules. */
 
-/* Returns an unsorted array of time_t's resulting from expanding the
-   recurrence within the given interval. Each iCalendar event can have any
-   number of recurrence rules specifying occurrences of the event, as well as
-   any number of recurrence rules specifying exceptions. */
+
+	/* Add on specific exception dates. */
+
+
+	/* Sort both arrays. */
+
+
+	/* Create the final array, by removing the exceptions from the
+	   occurrences, and removing any duplicates. */
+
+
+}
+
+
+
+/* Returns an unsorted GArray of CalObjTime's resulting from expanding the
+   given recurrence rule within the given interval. */
 GArray*
 cal_obj_expand_recurrence		(CalObjTime	*event_start,
-					 CalObjTime	*event_end,
-					 Recurrence	*recur,
+					 CalObjRecurrence *recur,
 					 CalObjTime	*interval_start,
 					 CalObjTime	*interval_end)
 {
 	CalObjRecurVTable *vtable;
+	CalObjTime *event_end = NULL, event_end_cotime;
+	RecurData recur_data;
 	CalObjTime occ;
 	GArray *all_occs, *occs;
-	gint filter;
+	struct tm *event_end_tm;
 
-	vtable = cal_obj_get_vtable (recur);
+	vtable = cal_obj_get_vtable (recur->type);
 
 	/* This is the resulting array of CalObjTime elements. */
 	all_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
 
+	/* Calculate some useful data such as some fast lookup tables. */
+	cal_obj_initialize_recur_data (&recur_data, recur, event_start);
+
+	/* Compute the event_end, if the recur's enddate is set. */
+	if (recur->enddate) {
+		event_end_tm = localtime (&recur->enddate);
+		event_end_cotime.year   = event_end_tm->tm_year + 1900;
+		event_end_cotime.month  = event_end_tm->tm_mon;
+		event_end_cotime.day    = event_end_tm->tm_mday;
+		event_end_cotime.hour   = event_end_tm->tm_hour;
+		event_end_cotime.minute = event_end_tm->tm_min;
+		event_end_cotime.second = event_end_tm->tm_sec;
+
+		event_end = &event_end_cotime;
+	}
+
 	/* Get the first period based on the frequency and the interval that
 	   intersects the interval between start and end. */
-	if ((*vtable->find_start_position) (event_start, event_end, recur,
+	if ((*vtable->find_start_position) (event_start, event_end,
+					    &recur_data,
 					    interval_start, interval_end,
 					    &occ))
 		return all_occs;
@@ -361,31 +524,40 @@ cal_obj_expand_recurrence		(CalObjTime	*event_start,
 	/* Loop until the event ends or we go past the end of the required
 	   interval. */
 	for (;;) {
-
-		/* We start with just the one time in the set. */
-		occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
-		g_array_append_val (occs, occ);
-
 		/* Generate the set of occurrences for this period. */
-		for (filter = 0; filter < CAL_OBJ_NUM_FILTERS; filter++) {
-			if (vtable->filters[filter])
-				occs = (*vtable->filters[filter]) (recur,
-								   occs);
+		/* FIXME: We shouldn't allow multiple expansion filters to be
+		   used to expand the days. They should be done separately and
+		   combined after, if needed. */
+		/* FIXME: Remove invalid days before HOURLY/MINUTELY/SECONDLY
+		   rules? Problems with WEEKLY as well? */
+		switch (recur->type) {
+		case CAL_RECUR_YEARLY:
+			occs = cal_obj_generate_set_yearly (&recur_data,
+							    vtable, &occ);
+			break;
+		case CAL_RECUR_MONTHLY:
+			occs = cal_obj_generate_set_monthly (&recur_data,
+							     vtable, &occ);
+			break;
+		default:
+			occs = cal_obj_generate_set_default (&recur_data,
+							     vtable, &occ);
+			break;
 		}
 
 		/* Sort the occurrences and remove duplicates. */
 		cal_obj_sort_occurrences (occs);
-		cal_obj_remove_duplicates (occs);
+		cal_obj_remove_duplicates_and_invalid_dates (occs);
 
 		/* Apply the BYSETPOS property. */
-		occs = cal_obj_bysetpos_filter (occs);
+		occs = cal_obj_bysetpos_filter (recur, occs);
 
 		/* Add the occurrences onto the main array. */
 		g_array_append_vals (all_occs, occs->data, occs->len);
 
 		/* Skip to the next period, or exit the loop if finished. */
-		if ((*vtable->find_next_position) (&occ, event_end, recur,
-						   interval_end))
+		if ((*vtable->find_next_position) (&occ, event_end,
+						   &recur_data, interval_end))
 			break;
 	}
 
@@ -393,93 +565,341 @@ cal_obj_expand_recurrence		(CalObjTime	*event_start,
 }
 
 
+static GArray*
+cal_obj_generate_set_yearly	(RecurData *recur_data,
+				 CalObjRecurVTable *vtable,
+				 CalObjTime *occ)
+{
+	CalObjRecurrence *recur = recur_data->recur;
+	GArray *occs_arrays[4], *occs, *occs2;
+	gint num_occs_arrays = 0, i;
+
+	/* This is a bit complicated, since the iCalendar spec says that
+	   several BYxxx modifiers can be used simultaneously. So we have to
+	   be quite careful when determining the days of the occurrences.
+	   The BYHOUR, BYMINUTE & BYSECOND modifiers are no problem at all.
+
+	   The modifiers we have to worry about are: BYMONTH, BYWEEKNO,
+	   BYYEARDAY, BYMONTHDAY & BYDAY. We can't do these sequentially
+	   since each filter will mess up the results of the previous one.
+	   But they aren't all completely independant, e.g. BYMONTHDAY and
+	   BYDAY are related to BYMONTH, and BYDAY is related to BYWEEKNO.
+
+	   BYDAY can also be applied independently, which makes it worse.
+	   So we assume that if BYMONTH or BYWEEKNO is used, then the BYDAY
+	   modifier applies to those, else it is applied independantly.
+
+	   We expand the occurrences in parallel into the occs_arrays[] array,
+	   and then merge them all into one GArray before expanding BYHOUR,
+	   BYMINUTE & BYSECOND. */
+	   
+	if (recur->bymonth) {
+		occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+		g_array_append_vals (occs, occ, 1);
+
+		occs = (*vtable->bymonth_filter) (recur_data, occs);
+
+		/* If BYMONTHDAY & BYDAY are both set we need to expand them
+		   in parallel and add the results. */
+		if (recur->bymonthday && recur->byday) {
+			/* Copy the occs array. */
+			occs2 = g_array_new (FALSE, FALSE,
+					     sizeof (CalObjTime));
+			g_array_append_vals (occs2, occs->data, occs->len);
+
+			occs = (*vtable->bymonthday_filter) (recur_data, occs);
+			/* Note that we explicitly call the monthly version
+			   of the BYDAY expansion filter. */
+			occs2 = cal_obj_byday_expand_monthly (recur_data,
+							      occs2);
+
+			/* Add the 2 resulting arrays together. */
+			g_array_append_vals (occs, occs2->data, occs2->len);
+			g_array_free (occs2, TRUE);
+		} else {
+			occs = (*vtable->bymonthday_filter) (recur_data, occs);
+			/* Note that we explicitly call the monthly version
+			   of the BYDAY expansion filter. */
+			occs = cal_obj_byday_expand_monthly (recur_data, occs);
+		}
+
+		occs_arrays[num_occs_arrays++] = occs;
+	}
+
+	if (recur->byweekno) {
+		occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+		g_array_append_vals (occs, occ, 1);
+
+		/* FIXME: We may have an invalid date here. What to do?? */
+
+		occs = (*vtable->byweekno_filter) (recur_data, occs);
+		/* Note that we explicitly call the weekly version of the
+		   BYDAY expansion filter. */
+		occs = cal_obj_byday_expand_weekly (recur_data, occs);
+
+		occs_arrays[num_occs_arrays++] = occs;
+	}
+
+	if (recur->byyearday) {
+		occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+		g_array_append_vals (occs, occ, 1);
+
+		occs = (*vtable->byyearday_filter) (recur_data, occs);
+
+		occs_arrays[num_occs_arrays++] = occs;
+	}
+
+	/* If BYDAY is set, and BYMONTH and BYWEEKNO are not set, we need to
+	   expand BYDAY independantly. */
+	if (recur->byday && !recur->bymonth && !recur->byweekno) {
+		occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+		g_array_append_vals (occs, occ, 1);
+
+		occs = (*vtable->byday_filter) (recur_data, occs);
+
+		occs_arrays[num_occs_arrays++] = occs;
+	}
+
+	/* Add all the arrays together. */
+	occs = occs_arrays[0];
+	for (i = 1; i < num_occs_arrays; i++) {
+		occs2 = occs_arrays[i];
+		g_array_append_vals (occs, occs2->data, occs2->len);
+		g_array_free (occs2, TRUE);
+	}
+
+	/* Now expand BYHOUR, BYMINUTE & BYSECOND. */
+	occs = (*vtable->byhour_filter) (recur_data, occs);
+	occs = (*vtable->byminute_filter) (recur_data, occs);
+	occs = (*vtable->bysecond_filter) (recur_data, occs);
+
+	return occs;
+}
+
+
+static GArray*
+cal_obj_generate_set_monthly	(RecurData *recur_data,
+				 CalObjRecurVTable *vtable,
+				 CalObjTime *occ)
+{
+	GArray *occs, *occs2;
+
+	/* We start with just the one time in each set. */
+	occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+	g_array_append_vals (occs, occ, 1);
+
+	occs = (*vtable->bymonth_filter) (recur_data, occs);
+
+	/* We need to combine the output of BYMONTHDAY & BYDAY, by doing them
+	   in parallel rather than sequentially. If we did them sequentially
+	   then we would lose the occurrences generated by BYMONTHDAY, and
+	   instead have repetitions of the occurrences from BYDAY. */
+	if (recur_data->recur->bymonthday && recur_data->recur->byday) {
+		occs2 = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+		g_array_append_vals (occs2, occs->data, occs->len);
+
+		occs = (*vtable->bymonthday_filter) (recur_data, occs);
+		occs2 = (*vtable->byday_filter) (recur_data, occs2);
+
+		g_array_append_vals (occs, occs2->data, occs2->len);
+		g_array_free (occs2, TRUE);
+	} else {
+		occs = (*vtable->bymonthday_filter) (recur_data, occs);
+		occs = (*vtable->byday_filter) (recur_data, occs);
+	}
+
+	occs = (*vtable->byhour_filter) (recur_data, occs);
+	occs = (*vtable->byminute_filter) (recur_data, occs);
+	occs = (*vtable->bysecond_filter) (recur_data, occs);
+
+	return occs;
+}
+
+
+static GArray*
+cal_obj_generate_set_default	(RecurData *recur_data,
+				 CalObjRecurVTable *vtable,
+				 CalObjTime *occ)
+{
+	GArray *occs;
+
+	/* We start with just the one time in the set. */
+	occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+	g_array_append_vals (occs, occ, 1);
+
+	occs = (*vtable->bymonth_filter) (recur_data, occs);
+	if (vtable->byweekno_filter)
+		occs = (*vtable->byweekno_filter) (recur_data, occs);
+	if (vtable->byyearday_filter)
+		occs = (*vtable->byyearday_filter) (recur_data, occs);
+	if (vtable->bymonthday_filter)
+		occs = (*vtable->bymonthday_filter) (recur_data, occs);
+	occs = (*vtable->byday_filter) (recur_data, occs);
+
+	occs = (*vtable->byhour_filter) (recur_data, occs);
+	occs = (*vtable->byminute_filter) (recur_data, occs);
+	occs = (*vtable->bysecond_filter) (recur_data, occs);
+
+	return occs;
+}
+
+
+
 /* Returns the function table corresponding to the recurrence frequency. */
 static CalObjRecurVTable*
-cal_obj_get_vtable (Recurrence *recur)
+cal_obj_get_vtable (CalObjRecurType recur_type)
 {
-	switch (recur->type) {
-	case RECUR_YEARLY:
+	switch (recur_type) {
+	case CAL_RECUR_YEARLY:
 		return &cal_obj_yearly_vtable;
-	case RECUR_MONTHLY:
+	case CAL_RECUR_MONTHLY:
 		return &cal_obj_monthly_vtable;
-	case RECUR_WEEKLY:
+	case CAL_RECUR_WEEKLY:
 		return &cal_obj_weekly_vtable;
-	case RECUR_DAILY:
+	case CAL_RECUR_DAILY:
 		return &cal_obj_daily_vtable;
-	case RECUR_HOURLY:
+	case CAL_RECUR_HOURLY:
 		return &cal_obj_hourly_vtable;
-	case RECUR_MINUTELY:
+	case CAL_RECUR_MINUTELY:
 		return &cal_obj_minutely_vtable;
-	case RECUR_SECONDLY:
+	case CAL_RECUR_SECONDLY:
 		return &cal_obj_secondly_vtable;
 	}
 	return NULL;
 }
 
 
+/* This creates a number of fast lookup tables used when filtering with the
+   modifier properties BYMONTH, BYYEARDAY etc. */
 static void
-cal_obj_sort_occurrences (GArray *occs)
+cal_obj_initialize_recur_data (RecurData  *recur_data,
+			       CalObjRecurrence *recur,
+			       CalObjTime *event_start)
 {
-	qsort (occs->data, occs->len, sizeof (CalObjTime),
-	       cal_obj_time_compare_func);
-}
+	GList *elem;
+	gint month, yearday, monthday, weekday, week_num, hour, minute, second;
 
+	/* Clear the entire RecurData. */
+	memset (recur_data, 0, sizeof (RecurData));
 
-static gint
-cal_obj_time_compare_func (const void *arg1,
-			   const void *arg2)
-{
-	CalObjTime *cotime1, *cotime2;
+	recur_data->recur = recur;
 
-	cotime1 = (CalObjTime*) arg1;
-	cotime2 = (CalObjTime*) arg2;
+	/* Set the weekday, used for the WEEKLY frequency and the BYWEEKNO
+	   modifier. */
+	recur_data->weekday = cal_obj_time_weekday (event_start, recur);
 
-	if (cotime1->year < cotime2->year)
-		return -1;
-	if (cotime1->year > cotime2->year)
-		return 1;
+	/* Create an array of months from bymonths for fast lookup. */
+	elem = recur->bymonth;
+	while (elem) {
+		month = GPOINTER_TO_INT (elem->data);
+		recur_data->months[month] = 1;
+		elem = elem->next;
+	}
 
-	if (cotime1->month < cotime2->month)
-		return -1;
-	if (cotime1->month > cotime2->month)
-		return 1;
+	/* Create an array of yeardays from byyearday for fast lookup.
+	   We create a second array to handle the negative values. The first
+	   element there corresponds to the last day of the year. */
+	elem = recur->byyearday;
+	while (elem) {
+		yearday = GPOINTER_TO_INT (elem->data);
+		if (yearday >= 0)
+			recur_data->yeardays[yearday] = 1;
+		else
+			recur_data->neg_yeardays[-yearday] = 1;
+		elem = elem->next;
+	}
 
-	if (cotime1->day < cotime2->day)
-		return -1;
-	if (cotime1->day > cotime2->day)
-		return 1;
+	/* Create an array of monthdays from bymonthday for fast lookup.
+	   We create a second array to handle the negative values. The first
+	   element there corresponds to the last day of the month. */
+	elem = recur->bymonthday;
+	while (elem) {
+		monthday = GPOINTER_TO_INT (elem->data);
+		if (monthday >= 0)
+			recur_data->monthdays[monthday] = 1;
+		else
+			recur_data->neg_monthdays[-monthday] = 1;
+		elem = elem->next;
+	}
 
-	if (cotime1->hour < cotime2->hour)
-		return -1;
-	if (cotime1->hour > cotime2->hour)
-		return 1;
+	/* Create an array of weekdays from byday for fast lookup. */
+	elem = recur->byday;
+	while (elem) {
+		weekday = GPOINTER_TO_INT (elem->data);
+		elem = elem->next;
+		/* The week number is not used when filtering. */
+		week_num = GPOINTER_TO_INT (elem->data);
+		elem = elem->next;
 
-	if (cotime1->minute < cotime2->minute)
-		return -1;
-	if (cotime1->minute > cotime2->minute)
-		return 1;
+		recur_data->weekdays[weekday] = 1;
+	}
 
-	if (cotime1->second < cotime2->second)
-		return -1;
-	if (cotime1->second > cotime2->second)
-		return 1;
+	/* Create an array of hours from byhour for fast lookup. */
+	elem = recur->byhour;
+	while (elem) {
+		hour = GPOINTER_TO_INT (elem->data);
+		recur_data->hours[hour] = 1;
+		elem = elem->next;
+	}
 
-	return 0;
+	/* Create an array of minutes from byminutes for fast lookup. */
+	elem = recur->byminute;
+	while (elem) {
+		minute = GPOINTER_TO_INT (elem->data);
+		recur_data->minutes[minute] = 1;
+		elem = elem->next;
+	}
+
+	/* Create an array of seconds from byseconds for fast lookup. */
+	elem = recur->bysecond;
+	while (elem) {
+		second = GPOINTER_TO_INT (elem->data);
+		recur_data->seconds[second] = 1;
+		elem = elem->next;
+	}
+}
+
+
+static void
+cal_obj_sort_occurrences (GArray *occs)
+{
+	qsort (occs->data, occs->len, sizeof (CalObjTime),
+	       cal_obj_time_compare_func);
 }
 
 
 static void
-cal_obj_remove_duplicates (GArray *occs)
+cal_obj_remove_duplicates_and_invalid_dates (GArray *occs)
 {
+	static const int days_in_month[12] = {
+		31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
+	};
+
 	CalObjTime *occ, *prev_occ = NULL;
-	gint len, i, j = 0;
+	gint len, i, j = 0, year, month, days;
+	gboolean keep_occ;
 
 	len = occs->len;
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
-
-		if (!prev_occ
-		    || cal_obj_time_compare_func (occ, prev_occ) != 0) {
+		keep_occ = TRUE;
+
+		if (prev_occ && cal_obj_time_compare_func (occ,
+							   prev_occ) == 0)
+			keep_occ = FALSE;
+
+		year = occ->year;
+		month = occ->month;
+		days = days_in_month[occ->month];
+		/* If it is february and a leap year, add a day. */
+		if (month == 1 && (year % 4 == 0
+				   && (year % 100 != 0
+				       || year % 400 == 0)))
+			days++;
+		if (occ->day > days)
+			keep_occ = FALSE;
+
+		if (keep_occ) {
 			if (i != j)
 				g_array_index (occs, CalObjTime, j)
 					= g_array_index (occs, CalObjTime, i);
@@ -494,24 +914,73 @@ cal_obj_remove_duplicates (GArray *occs)
 
 
 static GArray*
-cal_obj_bysetpos_filter (GArray *occs)
+cal_obj_bysetpos_filter (CalObjRecurrence *recur,
+			 GArray	    *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ;
+	GList *elem;
+	gint len, pos;
 
-	return occs;
+	/* If BYSETPOS has not been specified, or the array is empty, just
+	   return the array. */
+	elem = recur->bysetpos;
+	if (!elem || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	/* Iterate over the indices given in bysetpos, adding the corresponding
+	   element from occs to new_occs. */
+	len = occs->len;
+	while (elem) {
+		pos = GPOINTER_TO_INT (elem->data);
+
+		/* Negative values count back from the end of the array. */
+		if (pos < 0)
+			pos += len;
+
+		if (pos >= 0 && pos < len) {
+			occ = &g_array_index (occs, CalObjTime, pos);
+			g_array_append_vals (new_occs, occ, 1);
+		}
+		elem = elem->next;
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 
 
+/* Finds the first year from the event_start, counting in multiples of the
+   recurrence interval, that intersects the given interval. It returns TRUE
+   if there is no intersection. */
 static gboolean
 cal_obj_yearly_find_start_position (CalObjTime *event_start,
 				    CalObjTime *event_end,
-				    Recurrence *recur,
+				    RecurData  *recur_data,
 				    CalObjTime *interval_start,
 				    CalObjTime *interval_end,
 				    CalObjTime *cotime)
 {
+	*cotime = *event_start;
+
+	/* Move on to the next interval, if the event starts before the
+	   given interval. */
+	if (cotime->year < interval_start->year) {
+		gint years = interval_start->year - cotime->year
+			+ recur_data->recur->interval - 1;
+		years -= years % recur_data->recur->interval;
+		/* NOTE: The day may now be invalid, e.g. 29th Feb. */
+		cotime->year += years;
+	}
 
+	if ((event_end && cotime->year > event_end->year)
+	    || (interval_end && cotime->year > interval_end->year))
+		return TRUE;
 
 	return FALSE;
 }
@@ -520,15 +989,14 @@ cal_obj_yearly_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_yearly_find_next_position (CalObjTime *cotime,
 				   CalObjTime *event_end,
-				   Recurrence *recur,
+				   RecurData  *recur_data,
 				   CalObjTime *interval_end)
 {
-	/* NOTE: The day may now be invalid, e.g. 29th Feb.
-	   Make sure we remove these eventually. */
-	cotime->year += recur->interval;
+	/* NOTE: The day may now be invalid, e.g. 29th Feb. */
+	cotime->year += recur_data->recur->interval;
 
-	if (cotime->year > event_end->year
-	    || cotime->year > interval_end->year)
+	if ((event_end && cotime->year > event_end->year)
+	    || (interval_end && cotime->year > interval_end->year))
 		return TRUE;
 
 	return FALSE;
@@ -539,12 +1007,30 @@ cal_obj_yearly_find_next_position (CalObjTime *cotime,
 static gboolean
 cal_obj_monthly_find_start_position (CalObjTime *event_start,
 				     CalObjTime *event_end,
-				     Recurrence *recur,
+				     RecurData  *recur_data,
 				     CalObjTime *interval_start,
 				     CalObjTime *interval_end,
 				     CalObjTime *cotime)
 {
+	*cotime = *event_start;
+
+	/* Move on to the next interval, if the event starts before the
+	   given interval. */
+	if (cal_obj_time_compare (cotime, interval_start, CALOBJ_MONTH) < 0) {
+		gint months = (interval_start->year - cotime->year) * 12
+			+ interval_start->month - cotime->month
+			+ recur_data->recur->interval - 1;
+		months -= months % recur_data->recur->interval;
+		/* NOTE: The day may now be invalid, e.g. 31st Sep. */
+		cal_obj_time_add_months (cotime, months);
+	}
 
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_MONTH) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_MONTH) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -553,19 +1039,17 @@ cal_obj_monthly_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_monthly_find_next_position (CalObjTime *cotime,
 				    CalObjTime *event_end,
-				    Recurrence *recur,
+				    RecurData  *recur_data,
 				    CalObjTime *interval_end)
 {
-	cotime->month += recur->interval;
-	cotime->year += cotime->month / 12;
-	cotime->month %= 12;
-
-	if (cotime->year > event_end->year
-	    || cotime->year > interval_end->year
-	    || (cotime->year == event_end->year
-		&& cotime->month > event_end->month)
-	    || (cotime->year == interval_end->year
-		&& cotime->month > interval_end->month))
+	/* NOTE: The day may now be invalid, e.g. 31st Sep. */
+	cal_obj_time_add_months (cotime, recur_data->recur->interval);
+
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_MONTH) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_MONTH) > 0)
 		return TRUE;
 
 	return FALSE;
@@ -576,12 +1060,62 @@ cal_obj_monthly_find_next_position (CalObjTime *cotime,
 static gboolean
 cal_obj_weekly_find_start_position (CalObjTime *event_start,
 				    CalObjTime *event_end,
-				    Recurrence *recur,
+				    RecurData  *recur_data,
 				    CalObjTime *interval_start,
 				    CalObjTime *interval_end,
 				    CalObjTime *cotime)
 {
+	GDate event_start_date, interval_start_date;
+	guint32 event_start_julian, interval_start_julian;
+	gint interval_start_weekday;
+	CalObjTime week_start;
+
+	if (event_end && cal_obj_time_compare (event_end, interval_start,
+					       CALOBJ_DAY) < 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (event_start, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
+
+	*cotime = *event_start;
+
+	/* Convert the event start and interval start to GDates, so we can
+	   easily find the number of days between them. */
+	g_date_clear (&event_start_date, 1);
+	g_date_set_dmy (&event_start_date, event_start->day,
+			event_start->month + 1, event_start->year);
+	g_date_clear (&interval_start_date, 1);
+	g_date_set_dmy (&interval_start_date, interval_start->day,
+			interval_start->month + 1, interval_start->year);
+
+	/* Calculate the start of the weeks corresponding to the event start
+	   and interval start. */
+	event_start_julian = g_date_julian (&event_start_date);
+	event_start_julian -= recur_data->weekday;
+
+	interval_start_julian = g_date_julian (&interval_start_date);
+	interval_start_weekday = cal_obj_time_weekday (interval_start,
+						       recur_data->recur);
+	interval_start_julian -= interval_start_weekday;
+
+	/* We want to find the first full week using the recurrence interval
+	   that intersects the given interval dates. */
+	if (event_start_julian < interval_start_julian) {
+		gint weeks = (interval_start_julian - event_start_julian) / 7;
+		weeks += recur_data->recur->interval - 1;
+		weeks -= weeks % recur_data->recur->interval;
+		cal_obj_time_add_days (cotime, weeks * 7);
+	}
 
+	week_start = *cotime;
+	cal_obj_time_subtract_days (&week_start, recur_data->weekday);
+
+	if (event_end && cal_obj_time_compare (&week_start, event_end,
+					       CALOBJ_DAY) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (&week_start, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -590,12 +1124,24 @@ cal_obj_weekly_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_weekly_find_next_position (CalObjTime *cotime,
 				   CalObjTime *event_end,
-				   Recurrence *recur,
+				   RecurData  *recur_data,
 				   CalObjTime *interval_end)
 {
-	cal_obj_time_add_days (cotime, recur->interval);
+	CalObjTime week_start;
 
+	cal_obj_time_add_days (cotime, recur_data->recur->interval * 7);
 
+	/* Return TRUE if the start of this week is after the event finishes
+	   or is after the end of the required interval. */
+	week_start = *cotime;
+	cal_obj_time_subtract_days (&week_start, recur_data->weekday);
+
+	if (event_end && cal_obj_time_compare (&week_start, event_end,
+					       CALOBJ_DAY) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (&week_start, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -604,12 +1150,48 @@ cal_obj_weekly_find_next_position (CalObjTime *cotime,
 static gboolean
 cal_obj_daily_find_start_position  (CalObjTime *event_start,
 				    CalObjTime *event_end,
-				    Recurrence *recur,
+				    RecurData  *recur_data,
 				    CalObjTime *interval_start,
 				    CalObjTime *interval_end,
 				    CalObjTime *cotime)
 {
+	GDate event_start_date, interval_start_date;
+	guint32 event_start_julian, interval_start_julian, days;
+
+	if (interval_end && cal_obj_time_compare (event_start, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
+	if (event_end && cal_obj_time_compare (event_end, interval_start,
+					       CALOBJ_DAY) < 0)
+		return TRUE;
 
+	*cotime = *event_start;
+
+	/* Convert the event start and interval start to GDates, so we can
+	   easily find the number of days between them. */
+	g_date_clear (&event_start_date, 1);
+	g_date_set_dmy (&event_start_date, event_start->day,
+			event_start->month + 1, event_start->year);
+	g_date_clear (&interval_start_date, 1);
+	g_date_set_dmy (&interval_start_date, interval_start->day,
+			interval_start->month + 1, interval_start->year);
+
+	event_start_julian = g_date_julian (&event_start_date);
+	interval_start_julian = g_date_julian (&interval_start_date);
+
+	if (event_start_julian < interval_start_julian) {
+		days = interval_start_julian - event_start_julian
+			+ recur_data->recur->interval - 1;
+		days -= days % recur_data->recur->interval;
+		cal_obj_time_add_days (cotime, days);
+	}
+
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_DAY) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -618,12 +1200,17 @@ cal_obj_daily_find_start_position  (CalObjTime *event_start,
 static gboolean
 cal_obj_daily_find_next_position  (CalObjTime *cotime,
 				   CalObjTime *event_end,
-				   Recurrence *recur,
+				   RecurData  *recur_data,
 				   CalObjTime *interval_end)
 {
+	cal_obj_time_add_days (cotime, recur_data->recur->interval);
 
-	cal_obj_time_add_days (cotime, recur->interval);
-
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_DAY) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_DAY) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -632,12 +1219,51 @@ cal_obj_daily_find_next_position  (CalObjTime *cotime,
 static gboolean
 cal_obj_hourly_find_start_position (CalObjTime *event_start,
 				    CalObjTime *event_end,
-				    Recurrence *recur,
+				    RecurData  *recur_data,
 				    CalObjTime *interval_start,
 				    CalObjTime *interval_end,
 				    CalObjTime *cotime)
 {
+	GDate event_start_date, interval_start_date;
+	guint32 event_start_julian, interval_start_julian, hours;
+
+	if (interval_end && cal_obj_time_compare (event_start, interval_end,
+						  CALOBJ_HOUR) > 0)
+		return TRUE;
+	if (event_end && cal_obj_time_compare (event_end, interval_start,
+					       CALOBJ_HOUR) < 0)
+		return TRUE;
 
+	*cotime = *event_start;
+
+	if (cal_obj_time_compare (event_start, interval_start,
+				  CALOBJ_HOUR) < 0) {
+		/* Convert the event start and interval start to GDates, so we
+		   can easily find the number of days between them. */
+		g_date_clear (&event_start_date, 1);
+		g_date_set_dmy (&event_start_date, event_start->day,
+				event_start->month + 1, event_start->year);
+		g_date_clear (&interval_start_date, 1);
+		g_date_set_dmy (&interval_start_date, interval_start->day,
+				interval_start->month + 1,
+				interval_start->year);
+
+		event_start_julian = g_date_julian (&event_start_date);
+		interval_start_julian = g_date_julian (&interval_start_date);
+
+		hours = (interval_start_julian - event_start_julian) * 24;
+		hours += interval_start->hour - event_start->hour;
+		hours += recur_data->recur->interval - 1;
+		hours -= hours % recur_data->recur->interval;
+		cal_obj_time_add_hours (cotime, hours);
+	}
+
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_HOUR) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_HOUR) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -646,10 +1272,17 @@ cal_obj_hourly_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_hourly_find_next_position (CalObjTime *cotime,
 				   CalObjTime *event_end,
-				   Recurrence *recur,
+				   RecurData  *recur_data,
 				   CalObjTime *interval_end)
 {
+	cal_obj_time_add_hours (cotime, recur_data->recur->interval);
 
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_HOUR) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_HOUR) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -658,12 +1291,53 @@ cal_obj_hourly_find_next_position (CalObjTime *cotime,
 static gboolean
 cal_obj_minutely_find_start_position (CalObjTime *event_start,
 				      CalObjTime *event_end,
-				      Recurrence *recur,
+				      RecurData  *recur_data,
 				      CalObjTime *interval_start,
 				      CalObjTime *interval_end,
 				      CalObjTime *cotime)
 {
+	GDate event_start_date, interval_start_date;
+	guint32 event_start_julian, interval_start_julian, minutes;
 
+	if (interval_end && cal_obj_time_compare (event_start, interval_end,
+						  CALOBJ_MINUTE) > 0)
+		return TRUE;
+	if (event_end && cal_obj_time_compare (event_end, interval_start,
+					       CALOBJ_MINUTE) < 0)
+		return TRUE;
+
+	*cotime = *event_start;
+
+	if (cal_obj_time_compare (event_start, interval_start,
+				  CALOBJ_MINUTE) < 0) {
+		/* Convert the event start and interval start to GDates, so we
+		   can easily find the number of days between them. */
+		g_date_clear (&event_start_date, 1);
+		g_date_set_dmy (&event_start_date, event_start->day,
+				event_start->month + 1, event_start->year);
+		g_date_clear (&interval_start_date, 1);
+		g_date_set_dmy (&interval_start_date, interval_start->day,
+				interval_start->month + 1,
+				interval_start->year);
+
+		event_start_julian = g_date_julian (&event_start_date);
+		interval_start_julian = g_date_julian (&interval_start_date);
+
+		minutes = (interval_start_julian - event_start_julian)
+			* 24 * 60;
+		minutes += (interval_start->hour - event_start->hour) * 24;
+		minutes += interval_start->minute - event_start->minute;
+		minutes += recur_data->recur->interval - 1;
+		minutes -= minutes % recur_data->recur->interval;
+		cal_obj_time_add_minutes (cotime, minutes);
+	}
+
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_MINUTE) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_MINUTE) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -672,10 +1346,17 @@ cal_obj_minutely_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_minutely_find_next_position (CalObjTime *cotime,
 				     CalObjTime *event_end,
-				     Recurrence *recur,
+				     RecurData  *recur_data,
 				     CalObjTime *interval_end)
 {
+	cal_obj_time_add_minutes (cotime, recur_data->recur->interval);
 
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_MINUTE) > 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_MINUTE) > 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -684,12 +1365,55 @@ cal_obj_minutely_find_next_position (CalObjTime *cotime,
 static gboolean
 cal_obj_secondly_find_start_position (CalObjTime *event_start,
 				      CalObjTime *event_end,
-				      Recurrence *recur,
+				      RecurData  *recur_data,
 				      CalObjTime *interval_start,
 				      CalObjTime *interval_end,
 				      CalObjTime *cotime)
 {
+	GDate event_start_date, interval_start_date;
+	guint32 event_start_julian, interval_start_julian, seconds;
+
+	if (interval_end && cal_obj_time_compare (event_start, interval_end,
+						  CALOBJ_SECOND) > 0)
+		return TRUE;
+	if (event_end && cal_obj_time_compare (event_end, interval_start,
+					       CALOBJ_SECOND) < 0)
+		return TRUE;
+
+	*cotime = *event_start;
+
+	if (cal_obj_time_compare (event_start, interval_start,
+				  CALOBJ_SECOND) < 0) {
+		/* Convert the event start and interval start to GDates, so we
+		   can easily find the number of days between them. */
+		g_date_clear (&event_start_date, 1);
+		g_date_set_dmy (&event_start_date, event_start->day,
+				event_start->month + 1, event_start->year);
+		g_date_clear (&interval_start_date, 1);
+		g_date_set_dmy (&interval_start_date, interval_start->day,
+				interval_start->month + 1,
+				interval_start->year);
+
+		event_start_julian = g_date_julian (&event_start_date);
+		interval_start_julian = g_date_julian (&interval_start_date);
+
+		seconds = (interval_start_julian - event_start_julian)
+			* 24 * 60 * 60;
+		seconds += (interval_start->hour - event_start->hour)
+			* 24 * 60;
+		seconds += (interval_start->minute - event_start->minute) * 60;
+		seconds += interval_start->second - event_start->second;
+		seconds += recur_data->recur->interval - 1;
+		seconds -= seconds % recur_data->recur->interval;
+		cal_obj_time_add_seconds (cotime, seconds);
+	}
 
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_SECOND) >= 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_SECOND) >= 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -698,10 +1422,17 @@ cal_obj_secondly_find_start_position (CalObjTime *event_start,
 static gboolean
 cal_obj_secondly_find_next_position (CalObjTime *cotime,
 				     CalObjTime *event_end,
-				     Recurrence *recur,
+				     RecurData  *recur_data,
 				     CalObjTime *interval_end)
 {
+	cal_obj_time_add_seconds (cotime, recur_data->recur->interval);
 
+	if (event_end && cal_obj_time_compare (cotime, event_end,
+					       CALOBJ_SECOND) >= 0)
+		return TRUE;
+	if (interval_end && cal_obj_time_compare (cotime, interval_end,
+						  CALOBJ_SECOND) >= 0)
+		return TRUE;
 
 	return FALSE;
 }
@@ -713,7 +1444,7 @@ cal_obj_secondly_find_next_position (CalObjTime *cotime,
 /* If the BYMONTH rule is specified it expands each occurrence in occs, by
    using each of the months in the bymonth list. */
 static GArray*
-cal_obj_bymonth_expand		(Recurrence *recur,
+cal_obj_bymonth_expand		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
@@ -723,7 +1454,7 @@ cal_obj_bymonth_expand		(Recurrence *recur,
 
 	/* If BYMONTH has not been specified, or the array is empty, just
 	   return the array. */
-	if (!recur->bymonth || occs->len == 0)
+	if (!recur_data->recur->bymonth || occs->len == 0)
 		return occs;
 
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
@@ -732,10 +1463,9 @@ cal_obj_bymonth_expand		(Recurrence *recur,
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
 
-		elem = recur->bymonth;
+		elem = recur_data->recur->bymonth;
 		while (elem) {
-			/* NOTE: The day may now be invalid, e.g. 31st Feb.
-			   Make sure we remove these eventually. */
+			/* NOTE: The day may now be invalid, e.g. 31st Feb. */
 			occ->month = GPOINTER_TO_INT (elem->data);
 			g_array_append_vals (new_occs, occ, 1);
 			elem = elem->next;
@@ -751,35 +1481,24 @@ cal_obj_bymonth_expand		(Recurrence *recur,
 /* If the BYMONTH rule is specified it filters out all occurrences in occs
    which do not match one of the months in the bymonth list. */
 static GArray*
-cal_obj_bymonth_filter		(Recurrence *recur,
+cal_obj_bymonth_filter		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
 	CalObjTime *occ;
-	guint8 months[12];
-	gint mon, len, i;
-	GList *elem;
+	gint len, i;
 
 	/* If BYMONTH has not been specified, or the array is empty, just
 	   return the array. */
-	elem = recur->bymonth;
-	if (!elem || occs->len == 0)
+	if (!recur_data->recur->bymonth || occs->len == 0)
 		return occs;
 
-	/* Create an array of months from bymonths for fast lookup. */
-	memset (&months, 0, sizeof (months));
-	while (elem) {
-		mon = GPOINTER_TO_INT (elem->data);
-		months[mon] = 1;
-		elem = elem->next;
-	}
-
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
 
 	len = occs->len;
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
-		if (months[occ->month])
+		if (recur_data->months[occ->month])
 			g_array_append_vals (new_occs, occ, 1);
 	}
 
@@ -791,18 +1510,70 @@ cal_obj_bymonth_filter		(Recurrence *recur,
 
 
 static GArray*
-cal_obj_byweekno_expand		(Recurrence *recur,
+cal_obj_byweekno_expand		(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ, year_start_cotime, year_end_cotime, cotime;
+	GList *elem;
+	gint len, i, weekno;
 
-	return occs;
+	/* If BYWEEKNO has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byweekno || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		/* Find the day that would correspond to week 1 (note that
+		   week 1 is the first week starting from the specified week
+		   start day that has 4 days in the new year). */
+		year_start_cotime = *occ;
+		cal_obj_time_find_first_week (&year_start_cotime,
+					      recur_data);
+
+		/* Find the day that would correspond to week 1 of the next
+		   year, which we use for -ve week numbers. */
+		year_end_cotime = *occ;
+		year_end_cotime.year++;
+		cal_obj_time_find_first_week (&year_end_cotime,
+					      recur_data);
+
+		/* Now iterate over the week numbers in byweekno, generating a
+		   new occurrence for each one. */
+		elem = recur_data->recur->byweekno;
+		while (elem) {
+			weekno = GPOINTER_TO_INT (elem->data);
+			/* FIXME: Skip occurrences outside the year? */
+			if (weekno > 0) {
+				cotime = year_start_cotime;
+				cal_obj_time_add_days (&cotime,
+						       (weekno - 1) * 7);
+			} else {
+				cotime = year_end_cotime;
+				cal_obj_time_subtract_days (&cotime,
+							    -weekno * 7);
+			}
+
+			g_array_append_val (new_occs, cotime);
+			elem = elem->next;
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 #if 0
 /* This isn't used at present. */
 static GArray*
-cal_obj_byweekno_filter		(Recurrence *recur,
+cal_obj_byweekno_filter		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 
@@ -812,58 +1583,415 @@ cal_obj_byweekno_filter		(Recurrence *recur,
 
 
 static GArray*
-cal_obj_byyearday_expand	(Recurrence *recur,
+cal_obj_byyearday_expand	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ, year_start_cotime, year_end_cotime, cotime;
+	GList *elem;
+	gint len, i, dayno;
 
-	return occs;
+	/* If BYYEARDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byyearday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		/* Find the day that would correspond to day 1. */
+		year_start_cotime = *occ;
+		year_start_cotime.month = 0;
+		year_start_cotime.day = 1;
+
+		/* Find the day that would correspond to day 1 of the next
+		   year, which we use for -ve day numbers. */
+		year_end_cotime = *occ;
+		year_end_cotime.year++;
+		year_end_cotime.month = 0;
+		year_end_cotime.day = 1;
+
+		/* Now iterate over the day numbers in byyearday, generating a
+		   new occurrence for each one. */
+		elem = recur_data->recur->byyearday;
+		while (elem) {
+			dayno = GPOINTER_TO_INT (elem->data);
+			if (dayno > 0) {
+				cotime = year_start_cotime;
+				cal_obj_time_add_days (&cotime, dayno - 1);
+			} else {
+				cotime = year_end_cotime;
+				cal_obj_time_subtract_days (&cotime, -dayno);
+			}
+
+			/* Skip occurrences if they fall outside the year. */
+			if (cotime.year == occ->year)
+				g_array_append_val (new_occs, cotime);
+			elem = elem->next;
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
+/* Note: occs must not contain invalid dates, e.g. 31st September. */
 static GArray*
-cal_obj_byyearday_filter	(Recurrence *recur,
+cal_obj_byyearday_filter	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ;
+	gint yearday, len, i, days_in_year;
 
-	return occs;
+	/* If BYYEARDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byyearday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+		yearday = cal_obj_time_day_of_year (occ);
+		if (recur_data->yeardays[yearday]) {
+			g_array_append_vals (new_occs, occ, 1);
+		} else {
+			days_in_year = g_date_is_leap_year (occ->year)
+				? 366 : 365;
+			if (recur_data->neg_yeardays[days_in_year + 1
+						    - yearday])
+				g_array_append_vals (new_occs, occ, 1);
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 
 static GArray*
-cal_obj_bymonthday_expand	(Recurrence *recur,
+cal_obj_bymonthday_expand	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ, month_start_cotime, month_end_cotime, cotime;
+	GList *elem;
+	gint len, i, dayno;
 
-	return occs;
+	/* If BYMONTHDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->bymonthday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		/* Find the day that would correspond to day 1. */
+		month_start_cotime = *occ;
+		month_start_cotime.day = 1;
+
+		/* Find the day that would correspond to day 1 of the next
+		   month, which we use for -ve day numbers. */
+		month_end_cotime = *occ;
+		month_end_cotime.month++;
+		month_end_cotime.day = 1;
+
+		/* Now iterate over the day numbers in bymonthday, generating a
+		   new occurrence for each one. */
+		elem = recur_data->recur->bymonthday;
+		while (elem) {
+			dayno = GPOINTER_TO_INT (elem->data);
+			if (dayno > 0) {
+				cotime = month_start_cotime;
+				cal_obj_time_add_days (&cotime, dayno - 1);
+			} else {
+				cotime = month_end_cotime;
+				cal_obj_time_subtract_days (&cotime, -dayno);
+			}
+
+			/* Skip occurrences if they fall outside the month. */
+			if (cotime.month == occ->month)
+				g_array_append_val (new_occs, cotime);
+			elem = elem->next;
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 static GArray*
-cal_obj_bymonthday_filter	(Recurrence *recur,
+cal_obj_bymonthday_filter	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ;
+	gint len, i, days_in_month;
 
-	return occs;
+	/* If BYMONTHDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->bymonthday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+		if (recur_data->monthdays[occ->day]) {
+			g_array_append_vals (new_occs, occ, 1);
+		} else {
+			days_in_month = time_days_in_month (occ->year,
+							    occ->month);
+			if (recur_data->neg_monthdays[days_in_month + 1
+						     - occ->day])
+				g_array_append_vals (new_occs, occ, 1);
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 
 static GArray*
-cal_obj_byday_expand		(Recurrence *recur,
+cal_obj_byday_expand_yearly	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ;
+	GList *elem;
+	gint len, i, weekday, week_num;
+	gint first_weekday, last_weekday, offset;
+	guint16 year;
 
-	return occs;
+	/* If BYDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		elem = recur_data->recur->byday;
+		while (elem) {
+			weekday = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+			week_num = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+
+			year = occ->year;
+			if (week_num == 0) {
+				occ->month = 0;
+				occ->day = 1;
+				first_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (weekday + 7 - first_weekday) % 7;
+				cal_obj_time_add_days (occ, offset);
+
+				while (occ->year == year) {
+					g_array_append_vals (new_occs, occ, 1);
+					cal_obj_time_add_days (occ, 7);
+				}
+
+			} else if (week_num > 0) {
+				occ->month = 0;
+				occ->day = 1;
+				first_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (weekday + 7 - first_weekday) % 7;
+				offset += (week_num - 1) * 7;
+				cal_obj_time_add_days (occ, offset);
+				if (occ->year == year)
+					g_array_append_vals (new_occs, occ, 1);
+
+			} else {
+				occ->month = 11;
+				occ->day = 31;
+				last_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (last_weekday + 7 - weekday) % 7;
+				offset += (week_num - 1) * 7;
+				cal_obj_time_subtract_days (occ, offset);
+				if (occ->year == year)
+					g_array_append_vals (new_occs, occ, 1);
+			}
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
 static GArray*
-cal_obj_byday_filter		(Recurrence *recur,
+cal_obj_byday_expand_monthly	(RecurData  *recur_data,
 				 GArray     *occs)
 {
+	GArray *new_occs;
+	CalObjTime *occ;
+	GList *elem;
+	gint len, i, weekday, week_num;
+	gint first_weekday, last_weekday, offset;
+	guint16 year;
+	guint8 month;
 
-	return occs;
+	/* If BYDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		elem = recur_data->recur->byday;
+		while (elem) {
+			weekday = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+			week_num = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+
+			year = occ->year;
+			month = occ->month;
+			if (week_num == 0) {
+				occ->day = 1;
+				first_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (weekday + 7 - first_weekday) % 7;
+				cal_obj_time_add_days (occ, offset);
+				
+				while (occ->year == year
+				       && occ->month == month) {
+					g_array_append_vals (new_occs, occ, 1);
+					cal_obj_time_add_days (occ, 7);
+				}
+				
+			} else if (week_num > 0) {
+				occ->day = 1;
+				first_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (weekday + 7 - first_weekday) % 7;
+				offset += (week_num - 1) * 7;
+				cal_obj_time_add_days (occ, offset);
+				if (occ->year == year && occ->month == month)
+					g_array_append_vals (new_occs, occ, 1);
+
+			} else {
+				occ->day = time_days_in_month (occ->year,
+							       occ->month);
+				last_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+				offset = (last_weekday + 7 - weekday) % 7;
+				offset += (week_num - 1) * 7;
+				cal_obj_time_subtract_days (occ, offset);
+				if (occ->year == year && occ->month == month)
+					g_array_append_vals (new_occs, occ, 1);
+			}
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
+}
+
+
+/* Note: occs must not contain invalid dates, e.g. 31st September. */
+static GArray*
+cal_obj_byday_expand_weekly	(RecurData  *recur_data,
+				 GArray     *occs)
+{
+	GArray *new_occs;
+	CalObjTime *occ;
+	GList *elem;
+	gint len, i, weekday, week_num;
+	gint current_weekday;
+	gint day_of_week, new_day_of_week, days_to_add;
+
+	/* If BYDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		elem = recur_data->recur->byday;
+		while (elem) {
+			weekday = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+			week_num = GPOINTER_TO_INT (elem->data);
+			elem = elem->next;
+
+			current_weekday = cal_obj_time_weekday (occ, recur_data->recur);
+			day_of_week = (current_weekday + 7
+				       - recur_data->recur->week_start_day) % 7;
+			new_day_of_week = (weekday + 7
+					   - recur_data->recur->week_start_day) % 7;
+			days_to_add = new_day_of_week - day_of_week;
+			if (days_to_add > 0)
+				cal_obj_time_add_days (occ, days_to_add);
+			else if (days_to_add < 0)
+				cal_obj_time_subtract_days (occ, -days_to_add);
+			g_array_append_vals (new_occs, occ, 1);
+		}
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
+}
+
+
+/* Note: occs must not contain invalid dates, e.g. 31st September. */
+static GArray*
+cal_obj_byday_filter		(RecurData  *recur_data,
+				 GArray     *occs)
+{
+	GArray *new_occs;
+	CalObjTime *occ;
+	gint len, i, weekday;
+
+	/* If BYDAY has not been specified, or the array is empty, just
+	   return the array. */
+	if (!recur_data->recur->byday || occs->len == 0)
+		return occs;
+
+	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+		weekday = cal_obj_time_weekday (occ, recur_data->recur);
+
+		/* See if the weekday on its own is set. */
+		if (recur_data->weekdays[weekday])
+			g_array_append_vals (new_occs, occ, 1);
+	}
+
+	g_array_free (occs, TRUE);
+
+	return new_occs;
 }
 
 
@@ -871,7 +1999,7 @@ cal_obj_byday_filter		(Recurrence *recur,
 /* If the BYHOUR rule is specified it expands each occurrence in occs, by
    using each of the hours in the byhour list. */
 static GArray*
-cal_obj_byhour_expand		(Recurrence *recur,
+cal_obj_byhour_expand		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
@@ -881,7 +2009,7 @@ cal_obj_byhour_expand		(Recurrence *recur,
 
 	/* If BYHOUR has not been specified, or the array is empty, just
 	   return the array. */
-	if (!recur->byhour || occs->len == 0)
+	if (!recur_data->recur->byhour || occs->len == 0)
 		return occs;
 
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
@@ -890,7 +2018,7 @@ cal_obj_byhour_expand		(Recurrence *recur,
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
 
-		elem = recur->byhour;
+		elem = recur_data->recur->byhour;
 		while (elem) {
 			occ->hour = GPOINTER_TO_INT (elem->data);
 			g_array_append_vals (new_occs, occ, 1);
@@ -907,35 +2035,24 @@ cal_obj_byhour_expand		(Recurrence *recur,
 /* If the BYHOUR rule is specified it filters out all occurrences in occs
    which do not match one of the hours in the byhour list. */
 static GArray*
-cal_obj_byhour_filter		(Recurrence *recur,
+cal_obj_byhour_filter		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
 	CalObjTime *occ;
-	guint8 hours[24];
-	gint hour, len, i;
-	GList *elem;
+	gint len, i;
 
-	/* If BYHOURUTE has not been specified, or the array is empty, just
+	/* If BYHOUR has not been specified, or the array is empty, just
 	   return the array. */
-	elem = recur->byhour;
-	if (!elem || occs->len == 0)
+	if (!recur_data->recur->byhour || occs->len == 0)
 		return occs;
 
-	/* Create an array of hours from byhour for fast lookup. */
-	memset (&hours, 0, sizeof (hours));
-	while (elem) {
-		hour = GPOINTER_TO_INT (elem->data);
-		hours[hour] = 1;
-		elem = elem->next;
-	}
-
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
 
 	len = occs->len;
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
-		if (hours[occ->hour])
+		if (recur_data->hours[occ->hour])
 			g_array_append_vals (new_occs, occ, 1);
 	}
 
@@ -949,7 +2066,7 @@ cal_obj_byhour_filter		(Recurrence *recur,
 /* If the BYMINUTE rule is specified it expands each occurrence in occs, by
    using each of the minutes in the byminute list. */
 static GArray*
-cal_obj_byminute_expand		(Recurrence *recur,
+cal_obj_byminute_expand		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
@@ -959,7 +2076,7 @@ cal_obj_byminute_expand		(Recurrence *recur,
 
 	/* If BYMINUTE has not been specified, or the array is empty, just
 	   return the array. */
-	if (!recur->byminute || occs->len == 0)
+	if (!recur_data->recur->byminute || occs->len == 0)
 		return occs;
 
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
@@ -968,7 +2085,7 @@ cal_obj_byminute_expand		(Recurrence *recur,
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
 
-		elem = recur->byminute;
+		elem = recur_data->recur->byminute;
 		while (elem) {
 			occ->minute = GPOINTER_TO_INT (elem->data);
 			g_array_append_vals (new_occs, occ, 1);
@@ -985,35 +2102,24 @@ cal_obj_byminute_expand		(Recurrence *recur,
 /* If the BYMINUTE rule is specified it filters out all occurrences in occs
    which do not match one of the minutes in the byminute list. */
 static GArray*
-cal_obj_byminute_filter		(Recurrence *recur,
+cal_obj_byminute_filter		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
 	CalObjTime *occ;
-	guint8 minutes[60];
-	gint min, len, i;
-	GList *elem;
+	gint len, i;
 
 	/* If BYMINUTE has not been specified, or the array is empty, just
 	   return the array. */
-	elem = recur->byminute;
-	if (!elem || occs->len == 0)
+	if (!recur_data->recur->byminute || occs->len == 0)
 		return occs;
 
-	/* Create an array of minutes from byminutes for fast lookup. */
-	memset (&minutes, 0, sizeof (minutes));
-	while (elem) {
-		min = GPOINTER_TO_INT (elem->data);
-		minutes[min] = 1;
-		elem = elem->next;
-	}
-
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
 
 	len = occs->len;
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
-		if (minutes[occ->minute])
+		if (recur_data->minutes[occ->minute])
 			g_array_append_vals (new_occs, occ, 1);
 	}
 
@@ -1027,7 +2133,7 @@ cal_obj_byminute_filter		(Recurrence *recur,
 /* If the BYSECOND rule is specified it expands each occurrence in occs, by
    using each of the seconds in the bysecond list. */
 static GArray*
-cal_obj_bysecond_expand		(Recurrence *recur,
+cal_obj_bysecond_expand		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
@@ -1037,7 +2143,7 @@ cal_obj_bysecond_expand		(Recurrence *recur,
 
 	/* If BYSECOND has not been specified, or the array is empty, just
 	   return the array. */
-	if (!recur->bysecond || occs->len == 0)
+	if (!recur_data->recur->bysecond || occs->len == 0)
 		return occs;
 
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
@@ -1046,7 +2152,7 @@ cal_obj_bysecond_expand		(Recurrence *recur,
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
 
-		elem = recur->bysecond;
+		elem = recur_data->recur->bysecond;
 		while (elem) {
 			occ->second = GPOINTER_TO_INT (elem->data);
 			g_array_append_vals (new_occs, occ, 1);
@@ -1063,35 +2169,24 @@ cal_obj_bysecond_expand		(Recurrence *recur,
 /* If the BYSECOND rule is specified it filters out all occurrences in occs
    which do not match one of the seconds in the bysecond list. */
 static GArray*
-cal_obj_bysecond_filter		(Recurrence *recur,
+cal_obj_bysecond_filter		(RecurData  *recur_data,
 				 GArray     *occs)
 {
 	GArray *new_occs;
 	CalObjTime *occ;
-	guint8 seconds[61];
-	gint sec, len, i;
-	GList *elem;
+	gint len, i;
 
 	/* If BYSECOND has not been specified, or the array is empty, just
 	   return the array. */
-	elem = recur->bysecond;
-	if (!elem || occs->len == 0)
+	if (!recur_data->recur->bysecond || occs->len == 0)
 		return occs;
 
-	/* Create an array of seconds from byseconds for fast lookup. */
-	memset (&seconds, 0, sizeof (seconds));
-	while (elem) {
-		sec = GPOINTER_TO_INT (elem->data);
-		seconds[sec] = 1;
-		elem = elem->next;
-	}
-
 	new_occs = g_array_new (FALSE, FALSE, sizeof (CalObjTime));
 
 	len = occs->len;
 	for (i = 0; i < len; i++) {
 		occ = &g_array_index (occs, CalObjTime, i);
-		if (seconds[occ->second])
+		if (recur_data->seconds[occ->second])
 			g_array_append_vals (new_occs, occ, 1);
 	}
 
@@ -1102,9 +2197,29 @@ cal_obj_bysecond_filter		(Recurrence *recur,
 
 
 
+
+
+/* Adds a positive number of months to the given CalObjTime, updating the year
+   appropriately so we end up with a valid month. Note that the day may be
+   invalid. */
 static void
-cal_obj_time_add_days (CalObjTime *cotime,
-		       gint	   days)
+cal_obj_time_add_months		(CalObjTime *cotime,
+				 gint	     months)
+{
+	guint month;
+
+	/* We use a guint to avoid overflow on the guint8. */
+	month = cotime->month + months;
+	cotime->year += month / 12;
+	cotime->month = month % 12;
+}
+
+
+/* Adds a positive number of days to the given CalObjTime, updating the month
+   and year appropriately so we end up with a valid day. */
+static void
+cal_obj_time_add_days		(CalObjTime *cotime,
+				 gint	     days)
 {
 	guint day, days_in_month;
 
@@ -1129,3 +2244,266 @@ cal_obj_time_add_days (CalObjTime *cotime,
 
 	cotime->day = (guint8) day;
 }
+
+
+/* Subtracts a positive number of days from the given CalObjTime, updating the
+   month and year appropriately so we end up with a valid day. */
+static void
+cal_obj_time_subtract_days	(CalObjTime *cotime,
+				 gint	     days)
+{
+	gint day, days_in_month;
+
+	/* We use a gint to avoid overflow on the guint8. */
+	day = (gint) cotime->day;
+	day -= days;
+
+	while (day <= 0) {
+		if (cotime->month == 0) {
+			cotime->year--;
+			cotime->month = 11;
+		} else {
+			cotime->month--;
+		}
+
+		days_in_month = time_days_in_month (cotime->year,
+						    cotime->month);
+
+		day += days_in_month;
+	}
+
+	cotime->day = (guint8) day;
+}
+
+
+/* Adds a positive number of hours to the given CalObjTime, updating the day,
+   month & year appropriately so we end up with a valid time. */
+static void
+cal_obj_time_add_hours		(CalObjTime *cotime,
+				 gint	     hours)
+{
+	guint hour;
+
+	/* We use a guint to avoid overflow on the guint8. */
+	hour = cotime->hour + hours;
+	cotime->hour = hour % 24;
+	if (hour > 24)
+		cal_obj_time_add_days (cotime, hour / 24);
+}
+
+
+/* Adds a positive number of minutes to the given CalObjTime, updating the
+   rest of the CalObjTime appropriately. */
+static void
+cal_obj_time_add_minutes	(CalObjTime *cotime,
+				 gint	     minutes)
+{
+	guint minute;
+
+	/* We use a guint to avoid overflow on the guint8. */
+	minute = cotime->minute + minutes;
+	cotime->minute = minute % 60;
+	if (minute > 60)
+		cal_obj_time_add_hours (cotime, minute / 60);
+}
+
+
+/* Adds a positive number of seconds to the given CalObjTime, updating the
+   rest of the CalObjTime appropriately. */
+static void
+cal_obj_time_add_seconds	(CalObjTime *cotime,
+				 gint	     seconds)
+{
+	guint second;
+
+	/* We use a guint to avoid overflow on the guint8. */
+	second = cotime->second + seconds;
+	cotime->second = second % 60;
+	if (second > 60)
+		cal_obj_time_add_minutes (cotime, second / 60);
+}
+
+
+/* Compares 2 CalObjTimes. Returns -1 if the cotime1 is before cotime2, 0 if
+   they are the same, or 1 if cotime1 is after cotime2. The comparison type
+   specifies which parts of the times we are interested in, e.g. if CALOBJ_DAY
+   is used we only want to know if the days are different. */
+static gint
+cal_obj_time_compare		(CalObjTime *cotime1,
+				 CalObjTime *cotime2,
+				 CalObjTimeComparison type)
+{
+	if (cotime1->year < cotime2->year)
+		return -1;
+	if (cotime1->year > cotime2->year)
+		return 1;
+
+	if (type == CALOBJ_YEAR)
+		return 0;
+
+	if (cotime1->month < cotime2->month)
+		return -1;
+	if (cotime1->month > cotime2->month)
+		return 1;
+
+	if (type == CALOBJ_MONTH)
+		return 0;
+
+	if (cotime1->day < cotime2->day)
+		return -1;
+	if (cotime1->day > cotime2->day)
+		return 1;
+
+	if (type == CALOBJ_DAY)
+		return 0;
+
+	if (cotime1->hour < cotime2->hour)
+		return -1;
+	if (cotime1->hour > cotime2->hour)
+		return 1;
+
+	if (type == CALOBJ_HOUR)
+		return 0;
+
+	if (cotime1->minute < cotime2->minute)
+		return -1;
+	if (cotime1->minute > cotime2->minute)
+		return 1;
+
+	if (type == CALOBJ_MINUTE)
+		return 0;
+
+	if (cotime1->second < cotime2->second)
+		return -1;
+	if (cotime1->second > cotime2->second)
+		return 1;
+
+	return 0;
+}
+
+
+/* This is the same as the above function, but without the comparison type.
+   It is used for qsort(). */
+static gint
+cal_obj_time_compare_func (const void *arg1,
+			   const void *arg2)
+{
+	CalObjTime *cotime1, *cotime2;
+
+	cotime1 = (CalObjTime*) arg1;
+	cotime2 = (CalObjTime*) arg2;
+
+	if (cotime1->year < cotime2->year)
+		return -1;
+	if (cotime1->year > cotime2->year)
+		return 1;
+
+	if (cotime1->month < cotime2->month)
+		return -1;
+	if (cotime1->month > cotime2->month)
+		return 1;
+
+	if (cotime1->day < cotime2->day)
+		return -1;
+	if (cotime1->day > cotime2->day)
+		return 1;
+
+	if (cotime1->hour < cotime2->hour)
+		return -1;
+	if (cotime1->hour > cotime2->hour)
+		return 1;
+
+	if (cotime1->minute < cotime2->minute)
+		return -1;
+	if (cotime1->minute > cotime2->minute)
+		return 1;
+
+	if (cotime1->second < cotime2->second)
+		return -1;
+	if (cotime1->second > cotime2->second)
+		return 1;
+
+	return 0;
+}
+
+
+/* Returns the weekday of the given CalObjTime, from 0 - 6. The week start
+   day is Monday by default, but can be set in the recurrence rule. */
+static gint
+cal_obj_time_weekday		(CalObjTime *cotime,
+				 CalObjRecurrence *recur)
+{
+	GDate date;
+	gint weekday;
+
+	g_date_clear (&date, 1);
+	g_date_set_dmy (&date, cotime->day, cotime->month + 1, cotime->year);
+
+	/* This results in a value of 0 (Monday) - 6 (Sunday). */
+	weekday = g_date_weekday (&date) - 1;
+
+	/* This calculates the offset of our day from the start of the week.
+	   We just add on a week (to avoid any possible negative values) and
+	   then subtract the specified week start day, then convert it into a
+	   value from 0-6. */
+	weekday = (weekday + 7 - recur->week_start_day) % 7;
+
+	return weekday;
+}
+
+
+/* Returns the day of the year of the given CalObjTime, from 1 - 366. */
+static gint
+cal_obj_time_day_of_year		(CalObjTime *cotime)
+{
+	GDate date;
+
+	g_date_clear (&date, 1);
+	g_date_set_dmy (&date, cotime->day, cotime->month + 1, cotime->year);
+
+	return g_date_day_of_year (&date);
+}
+
+
+/* Finds the first week in the given CalObjTime's year, using the same weekday
+   as the event start day (i.e. from the RecurData).
+   The first week of the year is the first week starting from the specified
+   week start day that has 4 days in the new year. It may be in the previous
+   year. */
+static void
+cal_obj_time_find_first_week	(CalObjTime *cotime,
+				 RecurData  *recur_data)
+{
+	GDate date;
+	gint weekday, week_start_day, offset;
+
+	/* Find out the weekday of the 1st of the year. */
+	g_date_clear (&date, 1);
+	g_date_set_dmy (&date, 1, 1, cotime->year);
+
+	/* This results in a value of 0 (Monday) - 6 (Sunday). */
+	weekday = g_date_weekday (&date) - 1;
+
+	/* Calculate the first day of the year that starts a new week. */
+	week_start_day = recur_data->recur->week_start_day;
+	offset = (week_start_day + 7 - weekday) % 7;
+
+	/* Now see if we have to move backwards 1 week, i.e. if the week
+	   starts on or after Jan 5th (since the previous week has 4 days in
+	   this year and so will be the first week of the year). */
+	if (offset >= 4)
+		offset -= 7;
+
+	/* Now move to the required day. */
+	offset += (recur_data->weekday + 7 - week_start_day) % 7;
+
+	/* Now move the cotime to the appropriate day. */
+	cotime->month = 0;
+	cotime->day = 1;
+	if (offset > 0)
+		cal_obj_time_add_days (cotime, offset);
+	else
+		cal_obj_time_subtract_days (cotime, offset);
+}
+
+
diff --git a/calendar/cal-util/cal-recur.h b/calendar/cal-util/cal-recur.h
index 340b897417..6069ff5f75 100644
--- a/calendar/cal-util/cal-recur.h
+++ b/calendar/cal-util/cal-recur.h
@@ -21,7 +21,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  */
 
-#ifndef CAL_RECURL_H
+#ifndef CAL_RECUR_H
 #define CAL_RECUR_H
 
 #include <libgnome/gnome-defs.h>
@@ -34,31 +34,49 @@ BEGIN_GNOME_DECLS
    the ones in calobj.h don't support all of iCalendar. Hopefully Seth will
    update those soon and these can be removed. */
 
-enum RecurType {
-	RECUR_YEARLY,
-	RECUR_MONTHLY,
-	RECUR_WEEKLY,
-	RECUR_DAILY,
-	RECUR_HOURLY,
-	RECUR_MINUTELY,
-	RECUR_SECONDLY,
-};
+typedef enum {
+	CAL_RECUR_YEARLY,
+	CAL_RECUR_MONTHLY,
+	CAL_RECUR_WEEKLY,
+	CAL_RECUR_DAILY,
+	CAL_RECUR_HOURLY,
+	CAL_RECUR_MINUTELY,
+	CAL_RECUR_SECONDLY
+} CalObjRecurType;
 
 typedef struct {
-	enum RecurType type;
+	CalObjRecurType	type;
 
 	int            interval;
 
-	int            weekday;
+	/* Specifies the end of the recurrence. No occurrences are generated
+	   after this date. If it is 0, the event recurs forever. */
+	time_t         enddate;
 
-	int	       month_pos;
+	/* WKST property - the week start day: 0 = Monday to 6 = Sunday. */
+	gint	       week_start_day;
 
-	int	       month_day;
 
+	/* NOTE: I've used GList's here, but it doesn't matter if we use
+	   other data structures like arrays. The code should be easy to
+	   change. So long as it is easy to see if the modifier is set. */
 
 	/* For BYMONTH modifier. A list of GINT_TO_POINTERs, 0-11. */
 	GList	      *bymonth;
 
+	/* For BYWEEKNO modifier. A list of GINT_TO_POINTERs, [+-]1-53. */
+	GList	      *byweekno;
+
+	/* For BYYEARDAY modifier. A list of GINT_TO_POINTERs, [+-]1-366. */
+	GList	      *byyearday;
+
+	/* For BYMONTHDAY modifier. A list of GINT_TO_POINTERs, [+-]1-31. */
+	GList	      *bymonthday;
+
+	/* For BYDAY modifier. A list of GINT_TO_POINTERs, in pairs.
+	   The first of each pair is the weekday, 0 = Monday to 6 = Sunday.
+	   The second of each pair is the week number [+-]0-53. */
+	GList	      *byday;
 
 	/* For BYHOUR modifier. A list of GINT_TO_POINTERs, 0-23. */
 	GList	      *byhour;
@@ -69,7 +87,10 @@ typedef struct {
 	/* For BYSECOND modifier. A list of GINT_TO_POINTERs, 0-60. */
 	GList	      *bysecond;
 
-} Recurrence;
+	/* For BYSETPOS modifier. A list of GINT_TO_POINTERs, +ve or -ve. */
+	GList	      *bysetpos;
+} CalObjRecurrence;
+
 
 
 
@@ -86,17 +107,12 @@ struct _CalObjTime {
 
 
 
-/* Returns an unsorted array of time_t's resulting from expanding the
-   recurrence within the given interval. Each iCalendar event can have any
-   number of recurrence rules specifying occurrences of the event, as well as
-   any number of recurrence rules specifying exceptions. */
-GArray*
-cal_obj_expand_recurrence		(CalObjTime	*event_start,
-					 CalObjTime	*event_end,
-					 Recurrence	*recur,
+GArray* cal_obj_expand_recurrence	(CalObjTime	*event_start,
+					 CalObjRecurrence *recur,
 					 CalObjTime	*interval_start,
 					 CalObjTime	*interval_end);
 
+
 END_GNOME_DECLS
 
 #endif
diff --git a/calendar/cal-util/test-recur.c b/calendar/cal-util/test-recur.c
new file mode 100644
index 0000000000..fd3059113e
--- /dev/null
+++ b/calendar/cal-util/test-recur.c
@@ -0,0 +1,114 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
+
+/* 
+ * Author : 
+ *  Damon Chaplin <damon@helixcode.com>
+ *
+ * Copyright 2000, Helix Code, Inc.
+ *
+ * This program is free software; you can redistribute it and/or 
+ * modify it under the terms of the GNU General Public License as 
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+
+/*
+ * This tests the recurrence rule expansion functions.
+ */
+
+#include <config.h>
+#include <string.h>
+#include <time.h>
+#include <glib.h>
+#include "cal-recur.h"
+
+static void set_time (CalObjTime *cotime, gint year, gint month, gint day,
+		      gint hour, gint minute, gint second);
+static void display_occs (GArray *occs);
+
+#define LIST_ADD(list, num) \
+	list = g_list_prepend (list, GINT_TO_POINTER (num));
+
+int
+main (int argc, char *argv[])
+{
+	CalObjTime event_start, interval_start, interval_end;
+	CalObjRecurrence recur;
+	GArray *occs;
+
+	set_time (&event_start,    2000, 0, 1, 0, 0, 0);
+
+	/* We set the interval to a wide range so we just test the event. */
+	set_time (&interval_start, 1900, 0, 1, 0, 0, 0);
+	set_time (&interval_end,   2100, 0, 1, 0, 0, 0);
+
+	memset (&recur, 0, sizeof (recur));
+	recur.type = CAL_RECUR_YEARLY;
+	recur.interval = 1;
+
+	LIST_ADD (recur.byweekno, 3)
+	LIST_ADD (recur.byweekno, 9)
+	LIST_ADD (recur.byweekno, 24)
+
+	LIST_ADD (recur.byday, 0)
+	LIST_ADD (recur.byday, 3)
+	LIST_ADD (recur.byday, 0)
+	LIST_ADD (recur.byday, 5)
+
+	occs = cal_obj_expand_recurrence (&event_start, &recur,
+					  &interval_start, &interval_end);
+
+	display_occs (occs);
+	g_array_free (occs, TRUE);
+
+	return 0;
+}
+
+
+static void
+set_time (CalObjTime *cotime, gint year, gint month, gint day,
+	  gint hour, gint minute, gint second)
+{
+	cotime->year	= year;
+	cotime->month	= month;
+	cotime->day	= day;
+	cotime->hour	= hour;
+	cotime->minute	= minute;
+	cotime->second	= second;
+}
+
+
+static void
+display_occs (GArray *occs)
+{
+	CalObjTime *occ;
+	gint len, i;
+	struct tm t;
+
+	len = occs->len;
+	for (i = 0; i < len; i++) {
+		occ = &g_array_index (occs, CalObjTime, i);
+
+		t.tm_sec	= occ->second;
+		t.tm_min	= occ->minute;
+		t.tm_hour	= occ->hour;
+		t.tm_mday	= occ->day;
+		t.tm_mon	= occ->month;
+		t.tm_year	= occ->year - 1900;
+		t.tm_isdst	= -1;
+
+		mktime (&t);
+
+		g_print ("%s", asctime (&t));
+	}
+}