# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1412373967 -7200
# Node ID fef95bc3063a3cbfa345e5e4dfba41160575f73a
# Parent  bfb1e0c934714588e87d51f115f20b076d2fea2a
Added some recurrence rule processing plus tests.

diff -r bfb1e0c93471 -r fef95bc3063a tests/qualifiers.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/qualifiers.py	Sat Oct 04 00:06:07 2014 +0200
@@ -0,0 +1,305 @@
+#!/usr/bin/env python
+
+from vRecurrence import *
+
+def show(l):
+    for x in l:
+        print x
+    print
+
+qualifiers = [
+    ("YEARLY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 11, 2)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((2003, 12, 24))
+print len(l) == 7, len(l)
+print l[0] == (1997, 11, 2), l[0]
+print l[-1] == (2003, 11, 2), l[-1]
+print
+
+qualifiers = [
+    ("YEARLY", {"interval" : 2}),
+    ("BYMONTH", {"values" : [1]}),
+    ("BYDAY", {"values" : [6]}),
+    ("BYHOUR", {"values" : [8, 9]}),
+    ("BYMINUTE", {"values" : [30]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 1, 5, 8, 30, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((2003, 12, 24, 0, 0, 0))
+print len(l) == 34, len(l)
+print l[0] == (1997, 1, 4, 8, 30, 0), l[0]
+print l[-1] == (2003, 1, 25, 9, 30, 0), l[-1]
+print
+
+qualifiers = [
+    ("DAILY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24), 10)
+print len(l) == 10, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 9, 11, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("DAILY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0))
+print len(l) == 113, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 12, 23, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("DAILY", {"interval" : 2})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0))
+print len(l) == 57, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 12, 23, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0))
+print len(l) == 17, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 12, 23, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("DAILY", {"interval" : 10})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0), 5)
+print len(l) == 5, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 10, 12, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("YEARLY", {"interval" : 1}),
+    ("BYMONTH", {"values" : [1]}),
+    ("BYDAY", {"values" : [1, 2, 3, 4, 5, 6, 7]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1998, 1, 1, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((2000, 1, 31, 14, 0, 0))
+print len(l) == 93, len(l)
+print l[0] == (1998, 1, 1, 9, 0, 0), l[0]
+print l[-1] == (2000, 1, 31, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("DAILY", {"interval" : 1}),
+    ("BYMONTH", {"values" : [1]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1998, 1, 1, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((2000, 1, 31, 14, 0, 0))
+print len(l) == 93, len(l)
+print l[0] == (1998, 1, 1, 9, 0, 0), l[0]
+print l[-1] == (2000, 1, 31, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0), 10)
+print len(l) == 10, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 11, 4, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 1})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0))
+print len(l) == 17, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 12, 23, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 2})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1998, 2, 20, 0, 0, 0))
+print len(l) == 13, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1998, 2, 17, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 1}),
+    ("BYDAY", {"values" : [2, 4]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 10, 7, 9, 0, 0))
+print len(l) == 10, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 10, 2, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 1}),
+    ("BYDAY", {"values" : [2, 4]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 2, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0), 10)
+print len(l) == 10, len(l)
+print l[0] == (1997, 9, 2, 9, 0, 0), l[0]
+print l[-1] == (1997, 10, 2, 9, 0, 0), l[-1]
+print
+
+qualifiers = [
+    ("WEEKLY", {"interval" : 2}),
+    ("BYDAY", {"values" : [1, 3, 5]})
+    ]
+
+l = order_qualifiers(qualifiers)
+show(l)
+dt = (1997, 9, 1, 9, 0, 0)
+l = get_datetime_structure(dt)
+show(l)
+l = combine_datetime_with_qualifiers(dt, qualifiers)
+show(l)
+
+s = process(l)
+l = s.materialise((1997, 12, 24, 0, 0, 0))
+print len(l) == 25, len(l)
+print l[0] == (1997, 9, 1, 9, 0, 0), l[0]
+print l[-1] == (1997, 12, 22, 9, 0, 0), l[-1]
+print
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r bfb1e0c93471 -r fef95bc3063a vRecurrence.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/vRecurrence.py	Sat Oct 04 00:06:07 2014 +0200
@@ -0,0 +1,364 @@
+#!/usr/bin/env python
+
+"""
+Recurrence rule calculation.
+
+Copyright (C) 2014 Paul Boddie <paul@boddie.org.uk>
+
+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 3 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, see <http://www.gnu.org/licenses/>.
+
+----
+
+References:
+
+RFC 5545: Internet Calendaring and Scheduling Core Object Specification
+          (iCalendar)
+          http://tools.ietf.org/html/rfc5545
+
+----
+
+FREQ defines the selection resolution.
+DTSTART defines the start of the selection.
+INTERVAL defines the step of the selection.
+COUNT defines a number of instances; UNTIL defines a limit to the selection.
+
+BY... qualifiers select instances within each outer selection instance according
+to the recurrence of instances of the next highest resolution. For example,
+BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated,
+all weeks are selected within the selection of the next highest explicitly
+specified resolution, whether this is months or years.
+
+BYSETPOS in conjunction with BY... qualifiers permit the selection of specific
+instances.
+
+Within the FREQ resolution, BY... qualifiers refine selected instances.
+
+Outside the FREQ resolution, BY... qualifiers select instances at the resolution
+concerned.
+
+Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing
+resolution (or decreasing scope).
+"""
+
+from datetime import date, datetime, timedelta
+import operator
+
+# Frequency levels, specified by FREQ in iCalendar.
+
+freq_levels = (
+    "SECONDLY",
+    "MINUTELY",
+    "HOURLY",
+    "DAILY",
+    "WEEKLY",
+    "MONTHLY",
+    "YEARLY"
+    )
+
+# Enumeration levels, employed by BY... qualifiers.
+
+enum_levels = (
+    ("BYSECOND",),
+    ("BYMINUTE",),
+    ("BYHOUR",),
+    ("BYDAY", "BYMONTHDAY", "BYYEARDAY"),
+    ("BYWEEKNO",),
+    ("BYMONTH",)
+    )
+
+special_enum_levels = ("BYDAY", "BYMONTHDAY", "BYYEARDAY")
+
+# Map from levels to lengths of datetime tuples.
+
+lengths = [6, 5, 4, 3, 3, 2, 1]
+positions = [l-1 for l in lengths]
+
+# Map from qualifiers to interval units. Here, weeks are defined as 7 days.
+
+units = {"WEEKLY" : 7}
+
+# Map from tuple positions to base values at each resolution.
+
+bases = [0, 1, 1, 0, 0, 0]
+
+def basevalue(resolution):
+    return bases[positions[resolution]]
+
+# Make dictionaries mapping qualifiers to levels.
+
+freq = dict([(level, i) for (i, level) in enumerate(freq_levels)])
+enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) for level in levels])
+
+# Functions for structuring the recurrences.
+
+def get_next(it):
+    try:
+        return it.next()
+    except StopIteration:
+        return None
+
+def order_qualifiers(qualifiers):
+
+    "Return the 'qualifiers' in order of increasing resolution."
+
+    l = []
+
+    for qualifier, args in qualifiers:
+        if enum.has_key(qualifier):
+            level = enum[qualifier]
+            if qualifier in special_enum_levels:
+                args["interval"] = 1
+                selector = PatternFilter
+            else:
+                selector = Enum
+        else:
+            level = freq[qualifier]
+            selector = Pattern
+
+        pos = positions[level]
+        l.append(selector(pos, args, qualifier))
+
+    l.sort(key=lambda x: x.pos)
+    return l
+
+def get_datetime_structure(datetime):
+
+    "Return the structure of 'datetime' for recurrence production."
+
+    l = []
+    for pos, value in enumerate(datetime):
+        l.append(Enum(pos, {"values" : [value]}, "DT"))
+    return l
+
+def combine_datetime_with_qualifiers(datetime, qualifiers):
+
+    """
+    Combine 'datetime' with 'qualifiers' to produce a structure for recurrence
+    production.
+    """
+
+    iter_dt = iter(get_datetime_structure(datetime))
+    iter_q = iter(order_qualifiers(qualifiers))
+
+    l = []
+
+    from_dt = get_next(iter_dt)
+    from_q = get_next(iter_q)
+
+    have_q = False
+    context = []
+
+    # Consume from both lists, merging entries.
+
+    while from_dt and from_q:
+        _pos = from_dt.pos
+        pos = from_q.pos
+
+        # Datetime value at wider resolution.
+
+        if _pos < pos:
+            if have_q:
+                l.append(from_dt)
+            else:
+                context.append(from_dt.args["values"][0])
+            from_dt = get_next(iter_dt)
+
+        # Qualifier at wider or same resolution as datetime value.
+
+        else:
+            if not have_q:
+                if isinstance(from_q, Enum) and pos > 0:
+                    repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT")
+                    repeat.context = tuple(context[:-1])
+                    l.append(repeat)
+                else:
+                    from_q.context = tuple(context)
+                have_q = True
+
+            # Either introduce the qualifier first.
+
+            if _pos > pos:
+                l.append(from_q)
+
+            # Or combine the qualifier and value details.
+
+            else:
+                l.append(combine_value_with_qualifier(from_dt, from_q))
+                from_dt = get_next(iter_dt)
+
+            from_q = get_next(iter_q)
+
+    # Complete the list.
+
+    while from_dt:
+        l.append(from_dt)
+        from_dt = get_next(iter_dt)
+
+    while from_q:
+        if not have_q:
+            if isinstance(from_q, Enum) and pos > 0:
+                repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT")
+                repeat.context = tuple(context[:-1])
+                l.append(repeat)
+            else:
+                from_q.context = tuple(context)
+            have_q = True
+        l.append(from_q)
+        from_q = get_next(iter_q)
+
+    return l
+
+def combine_value_with_qualifier(from_dt, from_q):
+
+    """
+    Combine value information supplied by 'from_dt' (a datetime) and 'from_q'
+    (a qualifier), imposing the datetime value information on any qualifiers.
+    """
+
+    if not from_q.args.has_key("values") and from_dt.args.has_key("values"):
+        from_q.args["values"] = from_dt.args["values"]
+    return from_q
+
+# Datetime arithmetic.
+
+def combine(t1, t2):
+    return tuple(map(lambda x, y: x or y, t1, t2))
+
+def scale(interval, pos):
+    return (0,) * pos + (interval,)
+
+def get_seconds(t):
+
+    "Convert the sub-day part of 't' into seconds."
+
+    t = t + (0,) * (6 - len(t))
+    return (t[3] * 60 + t[4]) * 60 + t[5]
+
+def update(t, step):
+
+    "Update 't' by 'step' at the resolution of 'step'."
+
+    i = len(step)
+
+    # Years only.
+
+    if i == 1:
+        return (t[0] + step[0],) + tuple(t[1:])
+
+    # Years and months.
+
+    elif i == 2:
+        month = t[1] + step[1]
+        return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:])
+
+    # Dates and datetimes.
+
+    else:
+        updated_for_months = update(t, step[:2])
+
+        # Dates only.
+
+        if i == 3:
+            d = datetime(*updated_for_months)
+            s = timedelta(step[2])
+
+        # Datetimes.
+
+        else:
+            d = datetime(*updated_for_months)
+            s = timedelta(step[2], get_seconds(step))
+
+        return (d + s).timetuple()[:len(t)]
+
+# Classes for producing instances from recurrence structures.
+
+class Selector:
+    def __init__(self, pos, args, qualifier, selecting=None):
+        self.pos = pos
+        self.args = args
+        self.qualifier = qualifier
+        self.context = ()
+        self.selecting = selecting
+
+    def __repr__(self):
+        return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context)
+
+    def materialise(self, end, count=None):
+        counter = count and [0, count]
+        return self.materialise_items(self.context, end, counter)
+
+    def materialise_item(self, current, next, counter):
+        if self.selecting:
+            return self.selecting.materialise_items(current, next, counter)
+        elif counter is None or counter[0] < counter[1]:
+            if counter is not None:
+                counter[0] += 1
+            return [current]
+        else:
+            return []
+
+class Pattern(Selector):
+    def materialise_items(self, context, end, counter):
+        start = self.args["values"][0]
+        interval = self.args.get("interval", 1) * units.get(self.qualifier, 1)
+        step = scale(interval, self.pos)
+        unit_interval = units.get(self.qualifier, 1)
+        unit_step = scale(unit_interval, self.pos)
+        current = combine(context, scale(start, self.pos))
+        results = []
+        while current < end and (counter is None or counter[0] < counter[1]):
+            next = update(current, step)
+            current_end = update(current, unit_step)
+            results += self.materialise_item(current, min(current_end, end), counter)
+            current = next
+        return results
+
+class PatternFilter(Selector):
+    def materialise_items(self, context, end, counter):
+        start = bases[self.pos]
+        step = scale(1, self.pos)
+        current = combine(context, scale(start, self.pos))
+        results = []
+        while current < end and (counter is None or counter[0] < counter[1]):
+            next = update(current, step)
+            results += self.materialise_item(current, min(next, end), counter)
+            current = next
+        return results
+
+    def materialise_item(self, current, next, counter):
+        values = self.args["values"]
+        if self.qualifier == "BYDAY":
+            if datetime(*current).isoweekday() in values:
+                return Selector.materialise_item(self, current, next, counter)
+        return []
+
+class Enum(Selector):
+    def materialise_items(self, context, end, counter):
+        step = scale(1, self.pos)
+        results = []
+        for value in self.args["values"]:
+            current = combine(context, scale(value, self.pos))
+            if current < end and (counter is None or counter[0] < counter[1]):
+                next = update(current, step)
+                results += self.materialise_item(current, min(next, end), counter)
+        return results
+
+def process(selectors):
+    current = selectors[0]
+    for selector in selectors[1:]:
+        current.selecting = selector
+        current = selector
+    return selectors[0]
+
+# vim: tabstop=4 expandtab shiftwidth=4