Calendars and recurring events

[Dave Swegen]

I'm about to write a calendar, which I hope will eventually support
events. Now I know how I'm going to go about most of the task, but the
one aspect that has me stumped is recurring events.

I'd like the user to be able to specify "repeat once a year", "repeat
until ddmmyyyy", "repeat every two weeks", "repeat first Monday of the
month" etc etc.

The only way I can think of doing it is by having an Event class, which
contains the details of the recurrence. As Events are created they are
placed into a list (or possibly a dbm keyed using a unique Event id).

My problem is that any time I want a view of events (say a one month
view), the program is going to have to traverse the whole list, and ask
if that event is due to be repeated for every day in that view. For one
month that would be ~30 traversals of the list, which seems disgusting in
its innefficiency. It might be possible to mitigate it somewhat by
cacheing results into a second hash (using the date as the key), but
that only seems like a small improvement.

And of course precalculating everything just seems incredibly wasteful
(not to mention questions such as how far into the future do you
calculate these things?).

I would really appreciate suggestions on how to go about organising the
data, and how to make recurring events work. I know this is a solved
problem, but I've been unable to find any solutions.

Cheers
	Dave