What's a good data structure for periodic or recurring dates?

Question

Is there a published data structure for storing periodic or recurring dates? Something that can handle:

1. The pump need recycling every five days.
2. Payday is every second Friday.
3. Thanksgiving Day is the second Monday in October (US: the fourth Thursday in November).
4. Valentine's Day is every February 14th.
5. Solstice is (usually) every June 21st and December 21st.
6. Easter is the Sunday after the first full moon on or after the day of the vernal equinox (okay, this one's a bit of a stretch).

I reckon cron's internal data structure can handle #1, #4, #5 (two rules), and maybe #2, but I haven't had a look at it. MS Outlook and other calendars seem to be able to handle the first five, but I don't have that source code lying around.

Answer 1

With all these variations in the way you specify the recurrence, I would shy away from one single data structure implementation to accommodate all 5 scenarios.

Instead, I would (and have for a previous project) build simple structures that address each type of recurrence. You could wrap them all up so that it feels like a single data structure, but under the hood they could do whatever they like. By implementing an interface, I was able to treat each type of recurrence similarly so it felt like a one-size-fits-all data structure. I could ask any instance for all the dates of recurrence within a certain time frame, and that did the trick.

I'd also want to know more about how these dates need to be used before settling on a specific implementation.

Answer 2

Use a iCalendar implementation library, like these ones: ruby, java, php, python, .net and java, and then add support for calculating special dates.

Answer 3

If you want to hands-on create a data structure, I'd recommend a hash table (where the holidays or event are keys with the new date occurrence as a value), if there are multiplicities of each occurrence you could hash the value that finds a section in a linked list, which then has a list of all the occurrences (this would make finding as well as insertion run in O(1)).