[ANN] ICal occurrence API

Hello all,

at long long last I have finally finished the ICal recurrence rule engine.  
I had to travel to Haskell in back to figure out a way to do it I liked.

Features:
  - To my knowledge this is the most compliant implementation of Recurrence
rules
  - Full support for Exclusion dates and exclusion rules (!)
  - Minimal dependency on external libraries

If you look at the implementation you will notice it uses LazyList's to do
it's work, which may make it seem a bit complicated.  But this allows me to
trivially add additional list mutations after-the-fact.  For example,
exclusion rules (i.e. all the logic of recurrence rules, but "differenced"
to the rules to generate exceptions) were actually added in about 15
minutes.  I know of no other implementations that have them at all.

The other advantage of the LazyList approach is that no more dates are
calculated then needed (well, actually one extra per rule may be if needed
for the stop test), but the set is none-the-less infinite.

The can be downloaded via Monticello as part of the iCalendar project with:

MCHttpRepository
    location: 'http://www.squeaksource.com/ical'
    user: ''
    password: ''



Thanks, and let me know if you see any problems with it.
Jason

_________________________________________________________________
More photos, more messages, more storage—get 2GB with Windows Live Hotmail.
http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_2G_0507

<JJ (Jason)>
Features:
  - To my knowledge this is the most compliant implementation of Recurrence
rules
  - Full support for Exclusion dates and exclusion rules (!)
</JJ (Jason)>

The next release of Chronos will have full support for recurrence rules
based on the iCal rule model--including exclusion dates and exclusion rules.

The implementation is based on a recurrence rule algebra, so that recurrence
rules can be specified using algegraic expressions, which are then evaluated
according to a recurrence rule algebra.

Example:

(RecurrenceSet from: (2007 month: #February day: 9))
        add:
                (RecurrenceRule
                        delta: 1 years count: 10
                        temporalExpression: ((WeekOfMonth week: 0) &
(#Sunday asDayOfWeek | #Saturday asDayOfWeek) not)
                        occurrenceIndices: #(0)); "Chronos uses 0 as the
ordinal of the last value or element."
        do: [:each | Transcript cr; show: each % #rfc2822]

The iCal expression that specifies the same thing:

  DTSTART;TZID=America/Los_Angeles:2007-02-09
  RRULE:FREQ=YEARLY;COUNT=10;BYDAY=-1MO,-1TU,-1WE,-1TH,-1FR;BYSETPOS=-1

The output:

Wed, 28 Feb 2007
Fri, 29 Feb 2008
Fri, 27 Feb 2009
Fri, 26 Feb 2010
Mon, 28 Feb 2011
Wed, 29 Feb 2012
Thu, 28 Feb 2013
Fri, 28 Feb 2014
Fri, 27 Feb 2015
Mon, 29 Feb 2016

--Alan

Interesting, I had no idea you were doing this.  And thanks for stealing my
thunder! :)  After you publish it, someone will have to compare the
different versions (speed, memory, ease of use, etc).

_________________________________________________________________
Make every IM count. Download Messenger and join the i’m Initiative now.
It’s free. http://im.live.com/messenger/im/home/?source=TAGHM_MAY07

<JJ (Jason)>Interesting, I had no idea you were doing this.  And thanks for
stealing my thunder! :)  After you publish it, someone will have to compare
the different versions (speed, memory, ease of use, etc).</JJ (Jason)>

I fully intend to have a look at your code--after I've completed my
implementation.  However, I don't plan on implementing a parser for
iCal--the only goal is to be able to specify/represent (and fully and
correctly implement) the iCal rule model.  Actually, the Chronos recurrence
rule model goes beyond what can be specified using the iCal rule
model/notation.  Using an algebra enables support for logical negation and
disjunction, among other things (consider what Chalten does with its
TimeLineFilter, for example.)

I'm also working on full support for business date arithmetic. I intend to
meet or exceed the capabilities offered by jFin
(http://jfin.org/date_adjustment) or ObjectLab
(http://objectlabkit.sourceforge.net/), and to use the data provided by
FinancialCalendar.com (http://financialcalendar.com/).

As for "thunder stealing," that goes with the territory when two or more
projects are in the same functional domain.  My goal is to implement the
world's best date/time library in any language--and I've been working hard
at it since October 2004.  I feel I've already achieved parity with anything
else out there.  Now it's time to go to the next level.

But, since my main motivation for making Chronos the best date/time library
in the world is to help promote Smalltalk, I actually welcome any and all
contributions by others to that goal.  And based on the description, your
iCal engine certainly seems to be a worthy contribution.

Working together, we can leave Smalltalk's competition in the dust.  And
inspire those working on Smalltalk projects in domains other than
dates/times to do the same.

Go Smalltalk!

--Alan

It will be very nice if you guys merge your work together. When I ported
iCal to VisualWorks I noticed that Chronos is already a prerequisite of
iCal and a duplication is therefore not nice to see and just calls to be
resolved into a merge :)

Best regards
Janko

Alan Lovejoy wrote:
--
Janko Mivšek
AIDA/Web
Smalltalk Web Application Server
http://www.aidaweb.si

I didn't either.  The iCalendar package made by Philippe does all that, it
just didn't do anything with the recurrence rules once made.

>  Actually, the Chronos recurrence
>rule model goes beyond what can be specified using the iCal rule
>model/notation.  Using an algebra enables support for logical negation and
>disjunction, among other things (consider what Chalten does with its
>TimeLineFilter, for example.)

That sounds cool.  I went for the Recurrence rule standard which is ugly,
ambiguous and, though my test coverage didn't point anything out, I think
even self-contradicting.

I don't know anything about recurrence rule algebra but it sounds good. :)

>I'm also working on full support for business date arithmetic. I intend to
>meet or exceed the capabilities offered by jFin
>(http://jfin.org/date_adjustment) or ObjectLab
>(http://objectlabkit.sourceforge.net/), and to use the data provided by
>FinancialCalendar.com (http://financialcalendar.com/).

Very cool.

>As for "thunder stealing," that goes with the territory when two or more
>projects are in the same functional domain.  My goal is to implement the
>world's best date/time library in any language--and I've been working hard
>at it since October 2004.  I feel I've already achieved parity with
>anything
>else out there.  Now it's time to go to the next level.

I wasn't mad or anything.  Just joking because of the timing of it. :)  But
yes, now that you point it out, it would make more sense that the recurrence
calculation code be with a time library, whether you use anything of mine or
not.  I learned a lot in the doing.

>But, since my main motivation for making Chronos the best date/time library
>in the world is to help promote Smalltalk, I actually welcome any and all
>contributions by others to that goal.  And based on the description, your
>iCal engine certainly seems to be a worthy contribution.

Thanks.  I don't know how much of my stuff will be usable for you.  I got
the approach from Haskell.  Basically the strategy is that the frequency
creates an infinite list of "periods" which are the same thing as a TimeSpan
but with a different interface.  All constraints (e.g. BYDAY) are applied to
the period stream they get, and they generate the next period stream from
it.  Once you get through all the constraints you should have the dates.

>Working together, we can leave Smalltalk's competition in the dust.  And
>inspire those working on Smalltalk projects in domains other than
>dates/times to do the same.
>
>Go Smalltalk!
>
>--Alan

That is what I want as well. :)

_________________________________________________________________
PC Magazine’s 2007 editors’ choice for best Web mail—award-winning Windows
Live Hotmail.
http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_pcmag_0507

<JJ (Jason)>I went for the Recurrence rule standard which is ugly, ambiguous
and, though my test coverage didn't point anything out, I think even
self-contradicting.</JJ (Jason)>

Yes.  And others have said the same thing.  One of the things I want to
check is your interpretation of iCal versus mine.  And versus that of
others.

One of the issues I'm dealing with is to ensure that the Chronos rule model
can represent any of the possible interpretations of an iCal ruleset, so
that the ambiguity issue will be the sole responsibility of the iCal parser.

And of course, I have to ensure that recurrence rules using non-Gregorian
calendars also work correctly--something iCal currently doesn't address.

<JJ (Jason)>I learned a lot in the doing.</JJ (Jason)>

I'm sure you did.  So did I.  Chronos itself, and recurrence rules in
particular, have proved to be far more complex and challenging than I had
anticipated before I really got into them.  The date/time functional domain
is not easy, not trivial, not simple, and cannot be adequately handled (let
alone comprehensively handled) with only a handful of classes and methods.
Collections and Streams are easy by comparison.


<JJ (Jason)>I don't know how much of my stuff will be usable for you.</JJ
(Jason)>

I am intrigued by your approach using LazyLists.  Since Chronos' recurrence
rules are implemented as executable syntax trees, it should be possible to
use them to emit ("compile") rules into your rule engine.

--Alan

<Janko Miv¹ek>
        It will be very nice if you guys merge your work together. When I
        ported iCal to VisualWorks I noticed that Chronos is already a
        prerequisite of iCal and a duplication is therefore not nice to see
        and just calls to be resolved into a merge :)
</Janko Miv¹ek>

Yes.  Cooperation/collaboration are always preferrable to conflict.

United we stand.  Divided we fall.

--Alan

My interpretation is actually from
http://www.kanzaki.com/docs/ical/rrule.html.  I made a test case for every
example they have.  This revealed (at least their interpretation of) how the
various situations are interpreted.

The sole rule that I did not honor was that they seem to start the frequency
from the boundary of dtstart (e.g. DTSTART:2007-05-23 would start at
2007-01-01 for yearly frequency, 2007-05-01 for monthly, etc.) and simply
drop all dates before dtstart in the set they return.

What I do is make the first period a "rest of" period (e.g. in the above
example my periods would be {Period start: 2007-05-23 end: 2007-12-31.
Period start: 2008-01-01 end: 2008-12-31...} for yearly).

There is only one test from that site that this difference shows up:  they
pick the 3rd in the set from MO, WE, FR (as I recall) and the dtstart starts
on the Monday, but there have already been a Wednesday and Friday in the
month before it.  So the example picks the dtstart while I pick the Monday
after.  I haven't tried to comply with this yet because I am thinking it
maybe a conflict that will cause the other tests to return the wrong date.

>I'm sure you did.  So did I.  Chronos itself, and recurrence rules in
>particular, have proved to be far more complex and challenging than I had
>anticipated before I really got into them.  The date/time functional domain
>is not easy, not trivial, not simple, and cannot be adequately handled (let
>alone comprehensively handled) with only a handful of classes and methods.
>Collections and Streams are easy by comparison.

Yea, that system is really impressive.  You can probably get a P.H.D. in
time now if you don't have one already. :)

>I am intrigued by your approach using LazyLists.  Since Chronos' recurrence
>rules are implemented as executable syntax trees, it should be possible to
>use them to emit ("compile") rules into your rule engine.
>
>--Alan

Yea, the LazyLists are just a simple way to delay computation while still
appearing as a (more or less) normal Smalltalk collection class.  I wanted
to handle the fact that any unbounded (i.e. no COUNT or UNTIL clause) set
was infinite, while also handling the fact that the common use case is going
to only want a small section of the dates (e.g. the most common will
probably be calendar GUI's printing the current month).

The engine currently makes all it's decisions based on the instVars of it's
frequency class, but I welcome any ideas you have for integration if you
think you can use my work.

_________________________________________________________________
Make every IM count. Download Messenger and join the i’m Initiative now.
It’s free. http://im.live.com/messenger/im/home/?source=TAGHM_MAY07

Jason,

I spent the the last hour rooting around in the latest version of the
iCalendar package from SqueakSource.  I see lots of code for parsing and
representing iCal recurrence rules, but can't find any code that
actually attempts to generate the set of occurrences specified by the rules.

Am I missing something?

--Alan

2007/12/30, Alan L. Lovejoy <[hidden email]>:
> Jason,
>
> I spent the the last hour rooting around in the latest version of the
> iCalendar package from SqueakSource.  I see lots of code for parsing and
> representing iCal recurrence rules,

Yes, for quite some time that was the only thing the package did
because computing the occurrences is a bit tricky.

> but can't find any code that
> actually attempts to generate the set of occurrences specified by the rules.
>
> Am I missing something?

If you load one of the later jbj versions you should get the code
described by Jason, see the added tests in ICEventTests for example
#testOccurencesWithExclusionDate.

Cheers
Philippe

Philippe Marschall wrote:

2007/12/30, Alan L. Lovejoy [hidden email]:
  

Jason,

I spent the the last hour rooting around in the latest version of the
iCalendar package from SqueakSource.  I see lots of code for parsing and
representing iCal recurrence rules,
    

Yes, for quite some time that was the only thing the package did
because computing the occurrences is a bit tricky.

  

but can't find any code that
actually attempts to generate the set of occurrences specified by the rules.

Am I missing something?
    

If you load one of the later jbj versions you should get the code
described by Jason, see the added tests in ICEventTests for example
#testOccurencesWithExclusionDate.

Cheers
Philippe
  

I didn't see any "jbj" versions yesterday.  And today, both the "Versions" tab and the "Latest" tab report "No matching public versions available".

???

2007/12/31, Alan L. Lovejoy <[hidden email]>:
Sorry I can not reproduce this. It shows me several jbj versions in
non-filtered and filtered [1] mode. In the latest tab I
see ICal-jbj.67.mcz.

[1] http://img175.imageshack.us/img175/8395/jbjversionsiv6.png

Cheers
Philippe

Where are you looking for the package?  It's on Squeak source.  Do a
search in the projects for icalendar.  It is named "iCalendar,
vCalendar and vCard" and has pmm as admin.

Here is the Monticello HTTP connect info for the project:

MCHttpRepository
    location: 'http://www.squeaksource.com/ical'
    user: ''
    password: ''

Let me know if you still have any problems.

Thanks,
Jason

On Dec 31, 2007 9:55 PM, Philippe Marschall
<[hidden email]> wrote: