1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/vRecurrence.py Sat Oct 04 00:06:07 2014 +0200
1.3 @@ -0,0 +1,364 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +Recurrence rule calculation.
1.8 +
1.9 +Copyright (C) 2014 Paul Boddie <paul@boddie.org.uk>
1.10 +
1.11 +This program is free software; you can redistribute it and/or modify it under
1.12 +the terms of the GNU General Public License as published by the Free Software
1.13 +Foundation; either version 3 of the License, or (at your option) any later
1.14 +version.
1.15 +
1.16 +This program is distributed in the hope that it will be useful, but WITHOUT
1.17 +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.18 +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.19 +details.
1.20 +
1.21 +You should have received a copy of the GNU General Public License along with
1.22 +this program. If not, see <http://www.gnu.org/licenses/>.
1.23 +
1.24 +----
1.25 +
1.26 +References:
1.27 +
1.28 +RFC 5545: Internet Calendaring and Scheduling Core Object Specification
1.29 + (iCalendar)
1.30 + http://tools.ietf.org/html/rfc5545
1.31 +
1.32 +----
1.33 +
1.34 +FREQ defines the selection resolution.
1.35 +DTSTART defines the start of the selection.
1.36 +INTERVAL defines the step of the selection.
1.37 +COUNT defines a number of instances; UNTIL defines a limit to the selection.
1.38 +
1.39 +BY... qualifiers select instances within each outer selection instance according
1.40 +to the recurrence of instances of the next highest resolution. For example,
1.41 +BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated,
1.42 +all weeks are selected within the selection of the next highest explicitly
1.43 +specified resolution, whether this is months or years.
1.44 +
1.45 +BYSETPOS in conjunction with BY... qualifiers permit the selection of specific
1.46 +instances.
1.47 +
1.48 +Within the FREQ resolution, BY... qualifiers refine selected instances.
1.49 +
1.50 +Outside the FREQ resolution, BY... qualifiers select instances at the resolution
1.51 +concerned.
1.52 +
1.53 +Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing
1.54 +resolution (or decreasing scope).
1.55 +"""
1.56 +
1.57 +from datetime import date, datetime, timedelta
1.58 +import operator
1.59 +
1.60 +# Frequency levels, specified by FREQ in iCalendar.
1.61 +
1.62 +freq_levels = (
1.63 + "SECONDLY",
1.64 + "MINUTELY",
1.65 + "HOURLY",
1.66 + "DAILY",
1.67 + "WEEKLY",
1.68 + "MONTHLY",
1.69 + "YEARLY"
1.70 + )
1.71 +
1.72 +# Enumeration levels, employed by BY... qualifiers.
1.73 +
1.74 +enum_levels = (
1.75 + ("BYSECOND",),
1.76 + ("BYMINUTE",),
1.77 + ("BYHOUR",),
1.78 + ("BYDAY", "BYMONTHDAY", "BYYEARDAY"),
1.79 + ("BYWEEKNO",),
1.80 + ("BYMONTH",)
1.81 + )
1.82 +
1.83 +special_enum_levels = ("BYDAY", "BYMONTHDAY", "BYYEARDAY")
1.84 +
1.85 +# Map from levels to lengths of datetime tuples.
1.86 +
1.87 +lengths = [6, 5, 4, 3, 3, 2, 1]
1.88 +positions = [l-1 for l in lengths]
1.89 +
1.90 +# Map from qualifiers to interval units. Here, weeks are defined as 7 days.
1.91 +
1.92 +units = {"WEEKLY" : 7}
1.93 +
1.94 +# Map from tuple positions to base values at each resolution.
1.95 +
1.96 +bases = [0, 1, 1, 0, 0, 0]
1.97 +
1.98 +def basevalue(resolution):
1.99 + return bases[positions[resolution]]
1.100 +
1.101 +# Make dictionaries mapping qualifiers to levels.
1.102 +
1.103 +freq = dict([(level, i) for (i, level) in enumerate(freq_levels)])
1.104 +enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) for level in levels])
1.105 +
1.106 +# Functions for structuring the recurrences.
1.107 +
1.108 +def get_next(it):
1.109 + try:
1.110 + return it.next()
1.111 + except StopIteration:
1.112 + return None
1.113 +
1.114 +def order_qualifiers(qualifiers):
1.115 +
1.116 + "Return the 'qualifiers' in order of increasing resolution."
1.117 +
1.118 + l = []
1.119 +
1.120 + for qualifier, args in qualifiers:
1.121 + if enum.has_key(qualifier):
1.122 + level = enum[qualifier]
1.123 + if qualifier in special_enum_levels:
1.124 + args["interval"] = 1
1.125 + selector = PatternFilter
1.126 + else:
1.127 + selector = Enum
1.128 + else:
1.129 + level = freq[qualifier]
1.130 + selector = Pattern
1.131 +
1.132 + pos = positions[level]
1.133 + l.append(selector(pos, args, qualifier))
1.134 +
1.135 + l.sort(key=lambda x: x.pos)
1.136 + return l
1.137 +
1.138 +def get_datetime_structure(datetime):
1.139 +
1.140 + "Return the structure of 'datetime' for recurrence production."
1.141 +
1.142 + l = []
1.143 + for pos, value in enumerate(datetime):
1.144 + l.append(Enum(pos, {"values" : [value]}, "DT"))
1.145 + return l
1.146 +
1.147 +def combine_datetime_with_qualifiers(datetime, qualifiers):
1.148 +
1.149 + """
1.150 + Combine 'datetime' with 'qualifiers' to produce a structure for recurrence
1.151 + production.
1.152 + """
1.153 +
1.154 + iter_dt = iter(get_datetime_structure(datetime))
1.155 + iter_q = iter(order_qualifiers(qualifiers))
1.156 +
1.157 + l = []
1.158 +
1.159 + from_dt = get_next(iter_dt)
1.160 + from_q = get_next(iter_q)
1.161 +
1.162 + have_q = False
1.163 + context = []
1.164 +
1.165 + # Consume from both lists, merging entries.
1.166 +
1.167 + while from_dt and from_q:
1.168 + _pos = from_dt.pos
1.169 + pos = from_q.pos
1.170 +
1.171 + # Datetime value at wider resolution.
1.172 +
1.173 + if _pos < pos:
1.174 + if have_q:
1.175 + l.append(from_dt)
1.176 + else:
1.177 + context.append(from_dt.args["values"][0])
1.178 + from_dt = get_next(iter_dt)
1.179 +
1.180 + # Qualifier at wider or same resolution as datetime value.
1.181 +
1.182 + else:
1.183 + if not have_q:
1.184 + if isinstance(from_q, Enum) and pos > 0:
1.185 + repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT")
1.186 + repeat.context = tuple(context[:-1])
1.187 + l.append(repeat)
1.188 + else:
1.189 + from_q.context = tuple(context)
1.190 + have_q = True
1.191 +
1.192 + # Either introduce the qualifier first.
1.193 +
1.194 + if _pos > pos:
1.195 + l.append(from_q)
1.196 +
1.197 + # Or combine the qualifier and value details.
1.198 +
1.199 + else:
1.200 + l.append(combine_value_with_qualifier(from_dt, from_q))
1.201 + from_dt = get_next(iter_dt)
1.202 +
1.203 + from_q = get_next(iter_q)
1.204 +
1.205 + # Complete the list.
1.206 +
1.207 + while from_dt:
1.208 + l.append(from_dt)
1.209 + from_dt = get_next(iter_dt)
1.210 +
1.211 + while from_q:
1.212 + if not have_q:
1.213 + if isinstance(from_q, Enum) and pos > 0:
1.214 + repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT")
1.215 + repeat.context = tuple(context[:-1])
1.216 + l.append(repeat)
1.217 + else:
1.218 + from_q.context = tuple(context)
1.219 + have_q = True
1.220 + l.append(from_q)
1.221 + from_q = get_next(iter_q)
1.222 +
1.223 + return l
1.224 +
1.225 +def combine_value_with_qualifier(from_dt, from_q):
1.226 +
1.227 + """
1.228 + Combine value information supplied by 'from_dt' (a datetime) and 'from_q'
1.229 + (a qualifier), imposing the datetime value information on any qualifiers.
1.230 + """
1.231 +
1.232 + if not from_q.args.has_key("values") and from_dt.args.has_key("values"):
1.233 + from_q.args["values"] = from_dt.args["values"]
1.234 + return from_q
1.235 +
1.236 +# Datetime arithmetic.
1.237 +
1.238 +def combine(t1, t2):
1.239 + return tuple(map(lambda x, y: x or y, t1, t2))
1.240 +
1.241 +def scale(interval, pos):
1.242 + return (0,) * pos + (interval,)
1.243 +
1.244 +def get_seconds(t):
1.245 +
1.246 + "Convert the sub-day part of 't' into seconds."
1.247 +
1.248 + t = t + (0,) * (6 - len(t))
1.249 + return (t[3] * 60 + t[4]) * 60 + t[5]
1.250 +
1.251 +def update(t, step):
1.252 +
1.253 + "Update 't' by 'step' at the resolution of 'step'."
1.254 +
1.255 + i = len(step)
1.256 +
1.257 + # Years only.
1.258 +
1.259 + if i == 1:
1.260 + return (t[0] + step[0],) + tuple(t[1:])
1.261 +
1.262 + # Years and months.
1.263 +
1.264 + elif i == 2:
1.265 + month = t[1] + step[1]
1.266 + return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:])
1.267 +
1.268 + # Dates and datetimes.
1.269 +
1.270 + else:
1.271 + updated_for_months = update(t, step[:2])
1.272 +
1.273 + # Dates only.
1.274 +
1.275 + if i == 3:
1.276 + d = datetime(*updated_for_months)
1.277 + s = timedelta(step[2])
1.278 +
1.279 + # Datetimes.
1.280 +
1.281 + else:
1.282 + d = datetime(*updated_for_months)
1.283 + s = timedelta(step[2], get_seconds(step))
1.284 +
1.285 + return (d + s).timetuple()[:len(t)]
1.286 +
1.287 +# Classes for producing instances from recurrence structures.
1.288 +
1.289 +class Selector:
1.290 + def __init__(self, pos, args, qualifier, selecting=None):
1.291 + self.pos = pos
1.292 + self.args = args
1.293 + self.qualifier = qualifier
1.294 + self.context = ()
1.295 + self.selecting = selecting
1.296 +
1.297 + def __repr__(self):
1.298 + return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context)
1.299 +
1.300 + def materialise(self, end, count=None):
1.301 + counter = count and [0, count]
1.302 + return self.materialise_items(self.context, end, counter)
1.303 +
1.304 + def materialise_item(self, current, next, counter):
1.305 + if self.selecting:
1.306 + return self.selecting.materialise_items(current, next, counter)
1.307 + elif counter is None or counter[0] < counter[1]:
1.308 + if counter is not None:
1.309 + counter[0] += 1
1.310 + return [current]
1.311 + else:
1.312 + return []
1.313 +
1.314 +class Pattern(Selector):
1.315 + def materialise_items(self, context, end, counter):
1.316 + start = self.args["values"][0]
1.317 + interval = self.args.get("interval", 1) * units.get(self.qualifier, 1)
1.318 + step = scale(interval, self.pos)
1.319 + unit_interval = units.get(self.qualifier, 1)
1.320 + unit_step = scale(unit_interval, self.pos)
1.321 + current = combine(context, scale(start, self.pos))
1.322 + results = []
1.323 + while current < end and (counter is None or counter[0] < counter[1]):
1.324 + next = update(current, step)
1.325 + current_end = update(current, unit_step)
1.326 + results += self.materialise_item(current, min(current_end, end), counter)
1.327 + current = next
1.328 + return results
1.329 +
1.330 +class PatternFilter(Selector):
1.331 + def materialise_items(self, context, end, counter):
1.332 + start = bases[self.pos]
1.333 + step = scale(1, self.pos)
1.334 + current = combine(context, scale(start, self.pos))
1.335 + results = []
1.336 + while current < end and (counter is None or counter[0] < counter[1]):
1.337 + next = update(current, step)
1.338 + results += self.materialise_item(current, min(next, end), counter)
1.339 + current = next
1.340 + return results
1.341 +
1.342 + def materialise_item(self, current, next, counter):
1.343 + values = self.args["values"]
1.344 + if self.qualifier == "BYDAY":
1.345 + if datetime(*current).isoweekday() in values:
1.346 + return Selector.materialise_item(self, current, next, counter)
1.347 + return []
1.348 +
1.349 +class Enum(Selector):
1.350 + def materialise_items(self, context, end, counter):
1.351 + step = scale(1, self.pos)
1.352 + results = []
1.353 + for value in self.args["values"]:
1.354 + current = combine(context, scale(value, self.pos))
1.355 + if current < end and (counter is None or counter[0] < counter[1]):
1.356 + next = update(current, step)
1.357 + results += self.materialise_item(current, min(next, end), counter)
1.358 + return results
1.359 +
1.360 +def process(selectors):
1.361 + current = selectors[0]
1.362 + for selector in selectors[1:]:
1.363 + current.selecting = selector
1.364 + current = selector
1.365 + return selectors[0]
1.366 +
1.367 +# vim: tabstop=4 expandtab shiftwidth=4