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.

Premium

This may help: #86199 – One

Thanks. If I had just searched for "recurring" instead of "recurring dates" I would've found a whole bunch of questions. – Premium

Answer 1

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

Dickdicken

Thanks. I thought iCalendar seemed like overkill, but perhaps it's the simplest solution after all. – Premium

Answer 2

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.

Withers

Yes, I'd think that you'd need a federated set of data structures, since the ways to express the recurrences are so different. And then you'd want an interface that you could query to find if a certain day or days matched any of the recurrences. In answer to your question, the dates will be used to book tele/video/web-conferences, some of which coincide with national holidays, hence the "second Monday in October" business. – Premium

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)).

Luckless