paul@48 | 1 | #!/usr/bin/env python |
paul@48 | 2 | |
paul@146 | 3 | """ |
paul@146 | 4 | Managing and presenting periods of time. |
paul@146 | 5 | |
paul@1230 | 6 | Copyright (C) 2014, 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk> |
paul@146 | 7 | |
paul@146 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@146 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@146 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@146 | 11 | version. |
paul@146 | 12 | |
paul@146 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@146 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@146 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@146 | 16 | details. |
paul@146 | 17 | |
paul@146 | 18 | You should have received a copy of the GNU General Public License along with |
paul@146 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@146 | 20 | """ |
paul@146 | 21 | |
paul@1230 | 22 | from bisect import bisect_left, insort_left |
paul@529 | 23 | from datetime import date, datetime, timedelta |
paul@939 | 24 | from imiptools.dates import check_permitted_values, correct_datetime, \ |
paul@1268 | 25 | format_datetime, get_datetime, \ |
paul@563 | 26 | get_datetime_attributes, \ |
paul@563 | 27 | get_recurrence_start, get_recurrence_start_point, \ |
paul@563 | 28 | get_start_of_day, \ |
paul@563 | 29 | get_tzid, \ |
paul@563 | 30 | to_timezone, to_utc_datetime |
paul@1370 | 31 | from vRecurrence import get_parameters, get_rule |
paul@48 | 32 | |
paul@924 | 33 | def ifnone(x, y): |
paul@924 | 34 | if x is None: return y |
paul@924 | 35 | else: return x |
paul@924 | 36 | |
paul@1251 | 37 | def start_point(obj): |
paul@1251 | 38 | return Comparable(ifnone(obj.get_start_point(), StartOfTime())) |
paul@1251 | 39 | |
paul@1251 | 40 | def end_point(obj): |
paul@1251 | 41 | return Comparable(ifnone(obj.get_end_point(), EndOfTime())) |
paul@1251 | 42 | |
paul@874 | 43 | class Comparable: |
paul@874 | 44 | |
paul@874 | 45 | "A date/datetime wrapper that allows comparisons with other types." |
paul@874 | 46 | |
paul@874 | 47 | def __init__(self, dt): |
paul@874 | 48 | self.dt = dt |
paul@874 | 49 | |
paul@874 | 50 | def __cmp__(self, other): |
paul@874 | 51 | dt = None |
paul@874 | 52 | odt = None |
paul@874 | 53 | |
paul@874 | 54 | # Find any dates/datetimes. |
paul@874 | 55 | |
paul@874 | 56 | if isinstance(self.dt, date): |
paul@874 | 57 | dt = self.dt |
paul@874 | 58 | if isinstance(other, date): |
paul@874 | 59 | odt = other |
paul@874 | 60 | elif isinstance(other, Comparable): |
paul@874 | 61 | if isinstance(other.dt, date): |
paul@874 | 62 | odt = other.dt |
paul@874 | 63 | else: |
paul@874 | 64 | other = other.dt |
paul@874 | 65 | |
paul@874 | 66 | if dt and odt: |
paul@874 | 67 | return cmp(dt, odt) |
paul@874 | 68 | elif dt: |
paul@874 | 69 | return other.__rcmp__(dt) |
paul@874 | 70 | elif odt: |
paul@874 | 71 | return self.dt.__cmp__(odt) |
paul@874 | 72 | else: |
paul@874 | 73 | return self.dt.__cmp__(other) |
paul@874 | 74 | |
paul@874 | 75 | class PointInTime: |
paul@874 | 76 | |
paul@874 | 77 | "A base class for special values." |
paul@874 | 78 | |
paul@874 | 79 | pass |
paul@874 | 80 | |
paul@874 | 81 | class StartOfTime(PointInTime): |
paul@874 | 82 | |
paul@874 | 83 | "A special value that compares earlier than other values." |
paul@874 | 84 | |
paul@874 | 85 | def __cmp__(self, other): |
paul@874 | 86 | if isinstance(other, StartOfTime): |
paul@874 | 87 | return 0 |
paul@874 | 88 | else: |
paul@874 | 89 | return -1 |
paul@874 | 90 | |
paul@874 | 91 | def __rcmp__(self, other): |
paul@874 | 92 | return -self.__cmp__(other) |
paul@874 | 93 | |
paul@887 | 94 | def __nonzero__(self): |
paul@887 | 95 | return False |
paul@887 | 96 | |
paul@944 | 97 | def __hash__(self): |
paul@944 | 98 | return 0 |
paul@944 | 99 | |
paul@874 | 100 | class EndOfTime(PointInTime): |
paul@874 | 101 | |
paul@874 | 102 | "A special value that compares later than other values." |
paul@874 | 103 | |
paul@874 | 104 | def __cmp__(self, other): |
paul@874 | 105 | if isinstance(other, EndOfTime): |
paul@874 | 106 | return 0 |
paul@874 | 107 | else: |
paul@874 | 108 | return 1 |
paul@874 | 109 | |
paul@874 | 110 | def __rcmp__(self, other): |
paul@874 | 111 | return -self.__cmp__(other) |
paul@874 | 112 | |
paul@887 | 113 | def __nonzero__(self): |
paul@887 | 114 | return False |
paul@887 | 115 | |
paul@944 | 116 | def __hash__(self): |
paul@944 | 117 | return 0 |
paul@944 | 118 | |
paul@944 | 119 | class Endless: |
paul@944 | 120 | |
paul@944 | 121 | "A special value indicating an endless period." |
paul@944 | 122 | |
paul@944 | 123 | def __cmp__(self, other): |
paul@944 | 124 | if isinstance(other, Endless): |
paul@944 | 125 | return 0 |
paul@944 | 126 | else: |
paul@944 | 127 | return 1 |
paul@944 | 128 | |
paul@944 | 129 | def __rcmp__(self, other): |
paul@944 | 130 | return -self.__cmp__(other) |
paul@944 | 131 | |
paul@944 | 132 | def __nonzero__(self): |
paul@944 | 133 | return True |
paul@944 | 134 | |
paul@646 | 135 | class PeriodBase: |
paul@458 | 136 | |
paul@458 | 137 | "A basic period abstraction." |
paul@458 | 138 | |
paul@944 | 139 | def __init__(self, start, end): |
paul@1171 | 140 | |
paul@1171 | 141 | """ |
paul@1171 | 142 | Define a period according to 'start' and 'end' which may be special |
paul@1171 | 143 | start/end of time values or iCalendar-format datetime strings. |
paul@1171 | 144 | """ |
paul@1171 | 145 | |
paul@944 | 146 | if isinstance(start, (date, PointInTime)): |
paul@944 | 147 | self.start = start |
paul@944 | 148 | else: |
paul@944 | 149 | self.start = get_datetime(start) or StartOfTime() |
paul@1171 | 150 | |
paul@944 | 151 | if isinstance(end, (date, PointInTime)): |
paul@944 | 152 | self.end = end |
paul@944 | 153 | else: |
paul@944 | 154 | self.end = get_datetime(end) or EndOfTime() |
paul@944 | 155 | |
paul@646 | 156 | def as_tuple(self): |
paul@646 | 157 | return self.start, self.end |
paul@646 | 158 | |
paul@646 | 159 | def __hash__(self): |
paul@646 | 160 | return hash((self.get_start(), self.get_end())) |
paul@646 | 161 | |
paul@646 | 162 | def __cmp__(self, other): |
paul@646 | 163 | |
paul@646 | 164 | "Return a comparison result against 'other' using points in time." |
paul@646 | 165 | |
paul@646 | 166 | if isinstance(other, PeriodBase): |
paul@646 | 167 | return cmp( |
paul@1251 | 168 | (start_point(self), end_point(self)), |
paul@1251 | 169 | (start_point(other), end_point(other)) |
paul@646 | 170 | ) |
paul@646 | 171 | else: |
paul@646 | 172 | return 1 |
paul@646 | 173 | |
paul@874 | 174 | def overlaps(self, other): |
paul@1251 | 175 | return end_point(self) > start_point(other) and \ |
paul@1251 | 176 | start_point(self) < end_point(other) |
paul@874 | 177 | |
paul@941 | 178 | def within(self, other): |
paul@1251 | 179 | return start_point(self) >= start_point(other) and \ |
paul@1251 | 180 | end_point(self) <= end_point(other) |
paul@941 | 181 | |
paul@1365 | 182 | def wraps(self, other): |
paul@1365 | 183 | return start_point(self) <= start_point(other) and \ |
paul@1365 | 184 | end_point(self) >= end_point(other) |
paul@1365 | 185 | |
paul@944 | 186 | def common(self, other): |
paul@1251 | 187 | start = max(start_point(self), start_point(other)) |
paul@1251 | 188 | end = min(end_point(self), end_point(other)) |
paul@944 | 189 | if start <= end: |
paul@944 | 190 | return self.make_corrected(start.dt, end.dt) |
paul@944 | 191 | else: |
paul@944 | 192 | return None |
paul@944 | 193 | |
paul@646 | 194 | def get_key(self): |
paul@646 | 195 | return self.get_start(), self.get_end() |
paul@646 | 196 | |
paul@646 | 197 | # Datetime and metadata methods. |
paul@646 | 198 | |
paul@646 | 199 | def get_start(self): |
paul@646 | 200 | return self.start |
paul@646 | 201 | |
paul@646 | 202 | def get_end(self): |
paul@646 | 203 | return self.end |
paul@646 | 204 | |
paul@646 | 205 | def get_start_attr(self): |
paul@646 | 206 | return get_datetime_attributes(self.start, self.tzid) |
paul@646 | 207 | |
paul@646 | 208 | def get_end_attr(self): |
paul@646 | 209 | return get_datetime_attributes(self.end, self.tzid) |
paul@646 | 210 | |
paul@646 | 211 | def get_start_item(self): |
paul@646 | 212 | return self.get_start(), self.get_start_attr() |
paul@646 | 213 | |
paul@646 | 214 | def get_end_item(self): |
paul@646 | 215 | return self.get_end(), self.get_end_attr() |
paul@646 | 216 | |
paul@646 | 217 | def get_start_point(self): |
paul@646 | 218 | return self.start |
paul@646 | 219 | |
paul@646 | 220 | def get_end_point(self): |
paul@646 | 221 | return self.end |
paul@646 | 222 | |
paul@659 | 223 | def get_duration(self): |
paul@944 | 224 | start = self.get_start_point() |
paul@944 | 225 | end = self.get_end_point() |
paul@944 | 226 | if start and end: |
paul@944 | 227 | return end - start |
paul@944 | 228 | else: |
paul@944 | 229 | return Endless() |
paul@659 | 230 | |
paul@646 | 231 | class Period(PeriodBase): |
paul@646 | 232 | |
paul@646 | 233 | "A simple period abstraction." |
paul@646 | 234 | |
paul@541 | 235 | def __init__(self, start, end, tzid=None, origin=None): |
paul@541 | 236 | |
paul@541 | 237 | """ |
paul@541 | 238 | Initialise a period with the given 'start' and 'end', having a |
paul@541 | 239 | contextual 'tzid', if specified, and an indicated 'origin'. |
paul@620 | 240 | |
paul@620 | 241 | All metadata from the start and end points are derived from the supplied |
paul@620 | 242 | dates/datetimes. |
paul@541 | 243 | """ |
paul@541 | 244 | |
paul@944 | 245 | PeriodBase.__init__(self, start, end) |
paul@541 | 246 | self.tzid = tzid |
paul@528 | 247 | self.origin = origin |
paul@458 | 248 | |
paul@458 | 249 | def as_tuple(self): |
paul@541 | 250 | return self.start, self.end, self.tzid, self.origin |
paul@458 | 251 | |
paul@458 | 252 | def __repr__(self): |
paul@630 | 253 | return "Period%r" % (self.as_tuple(),) |
paul@458 | 254 | |
paul@646 | 255 | # Datetime and metadata methods. |
paul@528 | 256 | |
paul@541 | 257 | def get_tzid(self): |
paul@620 | 258 | return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid |
paul@620 | 259 | |
paul@557 | 260 | def get_start_point(self): |
paul@874 | 261 | start = self.get_start() |
paul@924 | 262 | if isinstance(start, PointInTime): return start |
paul@924 | 263 | else: return to_utc_datetime(start, self.get_tzid()) |
paul@557 | 264 | |
paul@557 | 265 | def get_end_point(self): |
paul@874 | 266 | end = self.get_end() |
paul@924 | 267 | if isinstance(end, PointInTime): return end |
paul@924 | 268 | else: return to_utc_datetime(end, self.get_tzid()) |
paul@557 | 269 | |
paul@633 | 270 | # Period and event recurrence logic. |
paul@633 | 271 | |
paul@633 | 272 | def is_replaced(self, recurrenceids): |
paul@633 | 273 | |
paul@633 | 274 | """ |
paul@633 | 275 | Return whether this period refers to one of the 'recurrenceids'. |
paul@633 | 276 | The 'recurrenceids' should be normalised to UTC datetimes according to |
paul@633 | 277 | time zone information provided by their objects or be floating dates or |
paul@633 | 278 | datetimes requiring conversion using contextual time zone information. |
paul@633 | 279 | """ |
paul@633 | 280 | |
paul@633 | 281 | for recurrenceid in recurrenceids: |
paul@647 | 282 | if self.is_affected(recurrenceid): |
paul@633 | 283 | return recurrenceid |
paul@633 | 284 | return None |
paul@633 | 285 | |
paul@633 | 286 | def is_affected(self, recurrenceid): |
paul@633 | 287 | |
paul@633 | 288 | """ |
paul@633 | 289 | Return whether this period refers to 'recurrenceid'. The 'recurrenceid' |
paul@633 | 290 | should be normalised to UTC datetimes according to time zone information |
paul@633 | 291 | provided by their objects. Otherwise, this period's contextual time zone |
paul@633 | 292 | information is used to convert any date or floating datetime |
paul@633 | 293 | representation to a point in time. |
paul@633 | 294 | """ |
paul@633 | 295 | |
paul@633 | 296 | if not recurrenceid: |
paul@633 | 297 | return None |
paul@633 | 298 | d = get_recurrence_start(recurrenceid) |
paul@633 | 299 | dt = get_recurrence_start_point(recurrenceid, self.tzid) |
paul@1126 | 300 | |
paul@1126 | 301 | # Compare the start to dates only, using the normalised start datetime |
paul@1126 | 302 | # for comparisons with the start point. |
paul@1126 | 303 | |
paul@1126 | 304 | if not isinstance(d, datetime) and self.get_start() == d or self.get_start_point() == dt: |
paul@633 | 305 | return recurrenceid |
paul@1126 | 306 | |
paul@633 | 307 | return None |
paul@633 | 308 | |
paul@1268 | 309 | def get_recurrenceid(self): |
paul@1268 | 310 | |
paul@1273 | 311 | """ |
paul@1273 | 312 | Return a recurrence identifier to identify this period. This identifier |
paul@1273 | 313 | employs the UTC time zone to avoid ambiguity. |
paul@1273 | 314 | """ |
paul@1268 | 315 | |
paul@1268 | 316 | return format_datetime(to_utc_datetime(self.get_start())) |
paul@1268 | 317 | |
paul@1268 | 318 | def get_recurrenceid_item(self): |
paul@1268 | 319 | |
paul@1273 | 320 | """ |
paul@1273 | 321 | Return datetime plus attributes for a recurrence identifier. These |
paul@1273 | 322 | details can be used to encode the recurrence identifier for output. |
paul@1273 | 323 | """ |
paul@1268 | 324 | |
paul@1268 | 325 | return self.get_start(), get_datetime_attributes(self.get_start()) |
paul@1268 | 326 | |
paul@939 | 327 | # Value correction methods. |
paul@939 | 328 | |
paul@941 | 329 | def with_duration(self, duration): |
paul@939 | 330 | |
paul@941 | 331 | """ |
paul@941 | 332 | Return a version of this period with the same start point but with the |
paul@941 | 333 | given 'duration'. |
paul@941 | 334 | """ |
paul@941 | 335 | |
paul@941 | 336 | return self.make_corrected(self.get_start(), self.get_start() + duration) |
paul@941 | 337 | |
paul@941 | 338 | def check_permitted(self, permitted_values): |
paul@941 | 339 | |
paul@941 | 340 | "Check the period against the given 'permitted_values'." |
paul@939 | 341 | |
paul@939 | 342 | start = self.get_start() |
paul@939 | 343 | end = self.get_end() |
paul@939 | 344 | start_errors = check_permitted_values(start, permitted_values) |
paul@939 | 345 | end_errors = check_permitted_values(end, permitted_values) |
paul@939 | 346 | |
paul@939 | 347 | if not (start_errors or end_errors): |
paul@941 | 348 | return None |
paul@941 | 349 | |
paul@941 | 350 | return start_errors, end_errors |
paul@941 | 351 | |
paul@941 | 352 | def get_corrected(self, permitted_values): |
paul@941 | 353 | |
paul@941 | 354 | "Return a corrected version of this period." |
paul@941 | 355 | |
paul@941 | 356 | errors = self.check_permitted(permitted_values) |
paul@941 | 357 | |
paul@941 | 358 | if not errors: |
paul@939 | 359 | return self |
paul@939 | 360 | |
paul@941 | 361 | start_errors, end_errors = errors |
paul@941 | 362 | |
paul@952 | 363 | start = self.get_start() |
paul@952 | 364 | end = self.get_end() |
paul@952 | 365 | |
paul@939 | 366 | if start_errors: |
paul@939 | 367 | start = correct_datetime(start, permitted_values) |
paul@939 | 368 | if end_errors: |
paul@939 | 369 | end = correct_datetime(end, permitted_values) |
paul@939 | 370 | |
paul@939 | 371 | return self.make_corrected(start, end) |
paul@939 | 372 | |
paul@939 | 373 | def make_corrected(self, start, end): |
paul@939 | 374 | return self.__class__(start, end, self.tzid, self.origin) |
paul@939 | 375 | |
paul@543 | 376 | class RecurringPeriod(Period): |
paul@543 | 377 | |
paul@620 | 378 | """ |
paul@620 | 379 | A period with iCalendar metadata attributes and origin information from an |
paul@620 | 380 | object. |
paul@620 | 381 | """ |
paul@543 | 382 | |
paul@543 | 383 | def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): |
paul@543 | 384 | Period.__init__(self, start, end, tzid, origin) |
paul@543 | 385 | self.start_attr = start_attr |
paul@1268 | 386 | self.end_attr = end_attr or start_attr |
paul@543 | 387 | |
paul@620 | 388 | def get_start_attr(self): |
paul@1268 | 389 | return self.start_attr or {} |
paul@543 | 390 | |
paul@620 | 391 | def get_end_attr(self): |
paul@1268 | 392 | return self.end_attr or {} |
paul@543 | 393 | |
paul@543 | 394 | def as_tuple(self): |
paul@543 | 395 | return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr |
paul@543 | 396 | |
paul@543 | 397 | def __repr__(self): |
paul@630 | 398 | return "RecurringPeriod%r" % (self.as_tuple(),) |
paul@543 | 399 | |
paul@939 | 400 | def make_corrected(self, start, end): |
paul@939 | 401 | return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) |
paul@939 | 402 | |
paul@1370 | 403 | def make_rule_period(start, duration, attr, tzid): |
paul@1370 | 404 | |
paul@1370 | 405 | """ |
paul@1370 | 406 | Make a period for the rule period starting at 'start' with the given |
paul@1370 | 407 | 'duration' employing the given datetime 'attr' and 'tzid'. |
paul@1370 | 408 | """ |
paul@1370 | 409 | |
paul@1370 | 410 | # Determine the resolution of the period. |
paul@1370 | 411 | |
paul@1370 | 412 | create = len(start) == 3 and date or datetime |
paul@1370 | 413 | start = to_timezone(create(*start), tzid) |
paul@1370 | 414 | end = start + duration |
paul@1370 | 415 | |
paul@1370 | 416 | # Create the period with accompanying metadata based on the main |
paul@1370 | 417 | # period and event details. |
paul@1370 | 418 | |
paul@1370 | 419 | return RecurringPeriod(start, end, tzid, "RRULE", attr) |
paul@1370 | 420 | |
paul@1370 | 421 | class RulePeriodCollection: |
paul@1370 | 422 | |
paul@1370 | 423 | "A collection of rule periods." |
paul@1370 | 424 | |
paul@1370 | 425 | def __init__(self, rrule, main_period, tzid, end, inclusive=False): |
paul@1370 | 426 | |
paul@1370 | 427 | """ |
paul@1370 | 428 | Initialise a period collection for the given 'rrule', employing the |
paul@1370 | 429 | 'main_period' and 'tzid'. |
paul@1370 | 430 | |
paul@1370 | 431 | The specified 'end' datetime indicates the end of the window for which |
paul@1370 | 432 | periods shall be computed. |
paul@1370 | 433 | |
paul@1370 | 434 | If 'inclusive' is set to a true value, any period occurring at the 'end' |
paul@1370 | 435 | will be included. |
paul@1370 | 436 | """ |
paul@1370 | 437 | |
paul@1370 | 438 | self.rrule = rrule |
paul@1370 | 439 | self.main_period = main_period |
paul@1370 | 440 | self.tzid = tzid |
paul@1370 | 441 | |
paul@1370 | 442 | parameters = rrule and get_parameters(rrule) |
paul@1370 | 443 | until = parameters.get("UNTIL") |
paul@1370 | 444 | |
paul@1370 | 445 | # Any UNTIL qualifier changes the nature of the end of the collection. |
paul@1370 | 446 | |
paul@1370 | 447 | if until: |
paul@1370 | 448 | attr = main_period.get_start_attr() |
paul@1370 | 449 | until_dt = to_timezone(get_datetime(until, attr), tzid) |
paul@1370 | 450 | self.end = end and min(until_dt, end) or until_dt |
paul@1370 | 451 | self.inclusive = True |
paul@1370 | 452 | else: |
paul@1370 | 453 | self.end = end |
paul@1370 | 454 | self.inclusive = inclusive |
paul@1370 | 455 | |
paul@1370 | 456 | def __iter__(self): |
paul@1370 | 457 | |
paul@1370 | 458 | """ |
paul@1370 | 459 | Obtain period instances, starting from the main period. Since counting |
paul@1370 | 460 | must start from the first period, filtering from a start date must be |
paul@1370 | 461 | done after the instances have been obtained. |
paul@1370 | 462 | """ |
paul@1370 | 463 | |
paul@1370 | 464 | start = self.main_period.get_start() |
paul@1370 | 465 | selector = get_rule(start, self.rrule) |
paul@1370 | 466 | |
paul@1370 | 467 | return RulePeriodIterator(self.main_period, self.tzid, |
paul@1370 | 468 | selector.select(start, self.end, self.inclusive)) |
paul@1370 | 469 | |
paul@1370 | 470 | class RulePeriodIterator: |
paul@1370 | 471 | |
paul@1370 | 472 | "An iterator over rule periods." |
paul@1370 | 473 | |
paul@1370 | 474 | def __init__(self, main_period, tzid, iterator): |
paul@1374 | 475 | self.main_period = main_period |
paul@1370 | 476 | self.attr = main_period.get_start_attr() |
paul@1370 | 477 | self.duration = main_period.get_duration() |
paul@1370 | 478 | self.tzid = tzid |
paul@1370 | 479 | self.iterator = iterator |
paul@1370 | 480 | |
paul@1370 | 481 | def next(self): |
paul@1370 | 482 | recurrence_start = self.iterator.next() |
paul@1374 | 483 | period = make_rule_period(recurrence_start, self.duration, self.attr, self.tzid) |
paul@1374 | 484 | |
paul@1374 | 485 | # Use the main period where it occurs. |
paul@1374 | 486 | |
paul@1374 | 487 | return period == self.main_period and self.main_period or period |
paul@1370 | 488 | |
paul@1370 | 489 | class MergingIterator: |
paul@1370 | 490 | |
paul@1370 | 491 | "An iterator merging ordered collections." |
paul@1370 | 492 | |
paul@1370 | 493 | def __init__(self, iterators): |
paul@1370 | 494 | |
paul@1370 | 495 | "Initialise an iterator merging 'iterators'." |
paul@1370 | 496 | |
paul@1370 | 497 | self.current = [] |
paul@1370 | 498 | |
paul@1370 | 499 | # Populate an ordered collection of (value, iterator) pairs by obtaining |
paul@1370 | 500 | # the first value from each iterator. |
paul@1370 | 501 | |
paul@1370 | 502 | for iterator in iterators: |
paul@1370 | 503 | t = self.get_next(iterator) |
paul@1370 | 504 | if t: |
paul@1370 | 505 | self.current.append(t) |
paul@1370 | 506 | |
paul@1370 | 507 | self.current.sort() |
paul@1370 | 508 | |
paul@1370 | 509 | def __iter__(self): |
paul@1370 | 510 | return self |
paul@1370 | 511 | |
paul@1370 | 512 | def get_next(self, iterator): |
paul@1370 | 513 | |
paul@1370 | 514 | """ |
paul@1370 | 515 | Return a (value, iterator) pair for 'iterator' or None if the iterator |
paul@1370 | 516 | has been exhausted. |
paul@1370 | 517 | """ |
paul@1370 | 518 | |
paul@1370 | 519 | try: |
paul@1370 | 520 | return (iterator.next(), iterator) |
paul@1370 | 521 | except StopIteration: |
paul@1370 | 522 | return None |
paul@1370 | 523 | |
paul@1370 | 524 | def next(self): |
paul@1370 | 525 | |
paul@1370 | 526 | """ |
paul@1370 | 527 | Return the next value in an ordered sequence, choosing it from one of |
paul@1370 | 528 | the available iterators. |
paul@1370 | 529 | """ |
paul@1370 | 530 | |
paul@1370 | 531 | if not self.current: |
paul@1370 | 532 | raise StopIteration |
paul@1370 | 533 | |
paul@1370 | 534 | # Obtain the current value and remove the (value, iterator) pair, |
paul@1370 | 535 | # pending insertion of a new pair for the iterator. |
paul@1370 | 536 | |
paul@1370 | 537 | current, iterator = self.current[0] |
paul@1370 | 538 | del self.current[0] |
paul@1370 | 539 | |
paul@1370 | 540 | # Get the next value, if any and insert the value and iterator into the |
paul@1370 | 541 | # ordered collection. |
paul@1370 | 542 | |
paul@1370 | 543 | t = self.get_next(iterator) |
paul@1370 | 544 | if t: |
paul@1370 | 545 | insort_left(self.current, t) |
paul@1370 | 546 | |
paul@1370 | 547 | return current |
paul@1370 | 548 | |
paul@1189 | 549 | def get_overlapping(first, second): |
paul@1189 | 550 | |
paul@1189 | 551 | """ |
paul@1189 | 552 | Return the entries in the sorted 'first' collection that are overlapping |
paul@1189 | 553 | with the given sorted 'second' collection. |
paul@1189 | 554 | """ |
paul@1189 | 555 | |
paul@1189 | 556 | if not first or not second: |
paul@1189 | 557 | return [] |
paul@1189 | 558 | |
paul@1189 | 559 | # Examine each period in the second collection, attempting to match periods |
paul@1189 | 560 | # in the first collection. |
paul@1189 | 561 | |
paul@1189 | 562 | overlapping = set() |
paul@1189 | 563 | |
paul@1189 | 564 | for p2 in second: |
paul@1189 | 565 | last_point = p2.get_end_point() |
paul@1189 | 566 | |
paul@1189 | 567 | # Examine the first collection up to the point where no matches will |
paul@1189 | 568 | # occur. |
paul@1189 | 569 | |
paul@1189 | 570 | for p1 in first: |
paul@1189 | 571 | if p1.get_start_point() > last_point: |
paul@1189 | 572 | break |
paul@1189 | 573 | elif p1.overlaps(p2): |
paul@1189 | 574 | overlapping.add(p1) |
paul@1189 | 575 | |
paul@1189 | 576 | overlapping = list(overlapping) |
paul@1189 | 577 | overlapping.sort() |
paul@1189 | 578 | return overlapping |
paul@1189 | 579 | |
paul@1310 | 580 | def get_overlapping_members(periods): |
paul@1310 | 581 | |
paul@1310 | 582 | "Return members of the 'periods' collection that overlap with others." |
paul@1310 | 583 | |
paul@1310 | 584 | if not periods: |
paul@1310 | 585 | return [] |
paul@1310 | 586 | |
paul@1310 | 587 | l = periods[:] |
paul@1310 | 588 | l.sort() |
paul@1310 | 589 | |
paul@1310 | 590 | overlapping = [] |
paul@1310 | 591 | |
paul@1310 | 592 | last = l[0] |
paul@1310 | 593 | last_added = None |
paul@1310 | 594 | |
paul@1310 | 595 | for p in l[1:]: |
paul@1310 | 596 | if p.get_start_point() < last.get_end_point(): |
paul@1310 | 597 | if last_added != last: |
paul@1310 | 598 | overlapping.append(last) |
paul@1310 | 599 | overlapping.append(p) |
paul@1310 | 600 | last_added = p |
paul@1310 | 601 | last = p |
paul@1310 | 602 | |
paul@1310 | 603 | return overlapping |
paul@1310 | 604 | |
paul@529 | 605 | # Period layout. |
paul@204 | 606 | |
paul@884 | 607 | def get_scale(periods, tzid, view_period=None): |
paul@113 | 608 | |
paul@113 | 609 | """ |
paul@925 | 610 | Return a time scale from the given list of 'periods'. |
paul@153 | 611 | |
paul@162 | 612 | The given 'tzid' is used to make sure that the times are defined according |
paul@162 | 613 | to the chosen time zone. |
paul@162 | 614 | |
paul@884 | 615 | An optional 'view_period' is used to constrain the scale to the given |
paul@884 | 616 | period. |
paul@884 | 617 | |
paul@162 | 618 | The returned scale is a mapping from time to (starting, ending) tuples, |
paul@458 | 619 | where starting and ending are collections of periods. |
paul@113 | 620 | """ |
paul@113 | 621 | |
paul@113 | 622 | scale = {} |
paul@884 | 623 | view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None |
paul@884 | 624 | view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None |
paul@113 | 625 | |
paul@458 | 626 | for p in periods: |
paul@113 | 627 | |
paul@113 | 628 | # Add a point and this event to the starting list. |
paul@113 | 629 | |
paul@536 | 630 | start = to_timezone(p.get_start(), tzid) |
paul@884 | 631 | start = view_start and max(start, view_start) or start |
paul@536 | 632 | if not scale.has_key(start): |
paul@536 | 633 | scale[start] = [], [] |
paul@536 | 634 | scale[start][0].append(p) |
paul@113 | 635 | |
paul@113 | 636 | # Add a point and this event to the ending list. |
paul@113 | 637 | |
paul@536 | 638 | end = to_timezone(p.get_end(), tzid) |
paul@931 | 639 | end = view_end and min(end, view_end) or end |
paul@931 | 640 | if not scale.has_key(end): |
paul@931 | 641 | scale[end] = [], [] |
paul@931 | 642 | scale[end][1].append(p) |
paul@113 | 643 | |
paul@113 | 644 | return scale |
paul@113 | 645 | |
paul@455 | 646 | class Point: |
paul@455 | 647 | |
paul@455 | 648 | "A qualified point in time." |
paul@455 | 649 | |
paul@455 | 650 | PRINCIPAL, REPEATED = 0, 1 |
paul@455 | 651 | |
paul@455 | 652 | def __init__(self, point, indicator=None): |
paul@455 | 653 | self.point = point |
paul@455 | 654 | self.indicator = indicator or self.PRINCIPAL |
paul@455 | 655 | |
paul@455 | 656 | def __hash__(self): |
paul@455 | 657 | return hash((self.point, self.indicator)) |
paul@455 | 658 | |
paul@455 | 659 | def __cmp__(self, other): |
paul@455 | 660 | if isinstance(other, Point): |
paul@455 | 661 | return cmp((self.point, self.indicator), (other.point, other.indicator)) |
paul@455 | 662 | elif isinstance(other, datetime): |
paul@455 | 663 | return cmp(self.point, other) |
paul@455 | 664 | else: |
paul@455 | 665 | return 1 |
paul@455 | 666 | |
paul@455 | 667 | def __eq__(self, other): |
paul@455 | 668 | return self.__cmp__(other) == 0 |
paul@455 | 669 | |
paul@455 | 670 | def __ne__(self, other): |
paul@455 | 671 | return not self == other |
paul@455 | 672 | |
paul@455 | 673 | def __lt__(self, other): |
paul@455 | 674 | return self.__cmp__(other) < 0 |
paul@455 | 675 | |
paul@455 | 676 | def __le__(self, other): |
paul@455 | 677 | return self.__cmp__(other) <= 0 |
paul@455 | 678 | |
paul@455 | 679 | def __gt__(self, other): |
paul@455 | 680 | return not self <= other |
paul@455 | 681 | |
paul@455 | 682 | def __ge__(self, other): |
paul@455 | 683 | return not self < other |
paul@455 | 684 | |
paul@455 | 685 | def __repr__(self): |
paul@455 | 686 | return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") |
paul@452 | 687 | |
paul@162 | 688 | def get_slots(scale): |
paul@113 | 689 | |
paul@113 | 690 | """ |
paul@162 | 691 | Return an ordered list of time slots from the given 'scale'. |
paul@113 | 692 | |
paul@452 | 693 | Each slot is a tuple containing details of a point in time for the start of |
paul@458 | 694 | the slot, together with a list of parallel event periods. |
paul@452 | 695 | |
paul@455 | 696 | Each point in time is described as a Point representing the actual point in |
paul@455 | 697 | time together with an indicator of the nature of the point in time (as a |
paul@455 | 698 | principal point in a time scale or as a repeated point used to terminate |
paul@455 | 699 | events occurring for an instant in time). |
paul@113 | 700 | """ |
paul@113 | 701 | |
paul@113 | 702 | slots = [] |
paul@113 | 703 | active = [] |
paul@113 | 704 | |
paul@162 | 705 | points = scale.items() |
paul@162 | 706 | points.sort() |
paul@162 | 707 | |
paul@162 | 708 | for point, (starting, ending) in points: |
paul@449 | 709 | ending = set(ending) |
paul@449 | 710 | instants = ending.intersection(starting) |
paul@113 | 711 | |
paul@113 | 712 | # Discard all active events ending at or before this start time. |
paul@161 | 713 | # Free up the position in the active list. |
paul@113 | 714 | |
paul@449 | 715 | for t in ending.difference(instants): |
paul@113 | 716 | i = active.index(t) |
paul@113 | 717 | active[i] = None |
paul@113 | 718 | |
paul@161 | 719 | # For each event starting at the current point, fill any newly-vacated |
paul@161 | 720 | # position or add to the end of the active list. |
paul@161 | 721 | |
paul@113 | 722 | for t in starting: |
paul@113 | 723 | try: |
paul@113 | 724 | i = active.index(None) |
paul@113 | 725 | active[i] = t |
paul@113 | 726 | except ValueError: |
paul@113 | 727 | active.append(t) |
paul@113 | 728 | |
paul@161 | 729 | # Discard vacant positions from the end of the active list. |
paul@161 | 730 | |
paul@113 | 731 | while active and active[-1] is None: |
paul@113 | 732 | active.pop() |
paul@113 | 733 | |
paul@452 | 734 | # Add an entry for the time point before "instants". |
paul@452 | 735 | |
paul@455 | 736 | slots.append((Point(point), active[:])) |
paul@113 | 737 | |
paul@449 | 738 | # Discard events ending at the same time as they began. |
paul@449 | 739 | |
paul@449 | 740 | if instants: |
paul@449 | 741 | for t in instants: |
paul@449 | 742 | i = active.index(t) |
paul@449 | 743 | active[i] = None |
paul@449 | 744 | |
paul@449 | 745 | # Discard vacant positions from the end of the active list. |
paul@449 | 746 | |
paul@449 | 747 | while active and active[-1] is None: |
paul@449 | 748 | active.pop() |
paul@449 | 749 | |
paul@452 | 750 | # Add another entry for the time point after "instants". |
paul@449 | 751 | |
paul@455 | 752 | slots.append((Point(point, Point.REPEATED), active[:])) |
paul@449 | 753 | |
paul@113 | 754 | return slots |
paul@113 | 755 | |
paul@244 | 756 | def add_day_start_points(slots, tzid): |
paul@153 | 757 | |
paul@153 | 758 | """ |
paul@162 | 759 | Introduce into the 'slots' any day start points required by multi-day |
paul@244 | 760 | periods. The 'tzid' is required to make sure that appropriate time zones |
paul@244 | 761 | are chosen and not necessarily those provided by the existing time points. |
paul@153 | 762 | """ |
paul@153 | 763 | |
paul@162 | 764 | new_slots = [] |
paul@153 | 765 | current_date = None |
paul@200 | 766 | previously_active = [] |
paul@153 | 767 | |
paul@455 | 768 | for point, active in slots: |
paul@455 | 769 | start_of_day = get_start_of_day(point.point, tzid) |
paul@455 | 770 | this_date = point.point.date() |
paul@153 | 771 | |
paul@198 | 772 | # For each new day, add a slot for the start of the day where periods |
paul@198 | 773 | # are active and where no such slot already exists. |
paul@153 | 774 | |
paul@153 | 775 | if this_date != current_date: |
paul@414 | 776 | |
paul@414 | 777 | # Fill in days where events remain active. |
paul@414 | 778 | |
paul@414 | 779 | if current_date: |
paul@414 | 780 | current_date += timedelta(1) |
paul@414 | 781 | while current_date < this_date: |
paul@455 | 782 | new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) |
paul@414 | 783 | current_date += timedelta(1) |
paul@414 | 784 | else: |
paul@414 | 785 | current_date = this_date |
paul@153 | 786 | |
paul@153 | 787 | # Add any continuing periods. |
paul@153 | 788 | |
paul@455 | 789 | if point.point != start_of_day: |
paul@455 | 790 | new_slots.append((Point(start_of_day), previously_active)) |
paul@153 | 791 | |
paul@153 | 792 | # Add the currently active periods at this point in time. |
paul@153 | 793 | |
paul@153 | 794 | previously_active = active |
paul@153 | 795 | |
paul@162 | 796 | for t in new_slots: |
paul@162 | 797 | insort_left(slots, t) |
paul@162 | 798 | |
paul@931 | 799 | def remove_end_slot(slots, view_period): |
paul@931 | 800 | |
paul@931 | 801 | """ |
paul@931 | 802 | Remove from 'slots' any slot situated at the end of the given 'view_period'. |
paul@931 | 803 | """ |
paul@931 | 804 | |
paul@931 | 805 | end = view_period.get_end_point() |
paul@931 | 806 | if not end or not slots: |
paul@931 | 807 | return |
paul@931 | 808 | i = bisect_left(slots, (Point(end), None)) |
paul@931 | 809 | if i < len(slots): |
paul@931 | 810 | del slots[i:] |
paul@931 | 811 | |
paul@162 | 812 | def add_slots(slots, points): |
paul@162 | 813 | |
paul@162 | 814 | """ |
paul@162 | 815 | Introduce into the 'slots' entries for those in 'points' that are not |
paul@170 | 816 | already present, propagating active periods from time points preceding |
paul@170 | 817 | those added. |
paul@162 | 818 | """ |
paul@162 | 819 | |
paul@162 | 820 | new_slots = [] |
paul@162 | 821 | |
paul@162 | 822 | for point in points: |
paul@452 | 823 | i = bisect_left(slots, (point,)) # slots is [(point, active)...] |
paul@162 | 824 | if i < len(slots) and slots[i][0] == point: |
paul@162 | 825 | continue |
paul@162 | 826 | |
paul@170 | 827 | new_slots.append((point, i > 0 and slots[i-1][1] or [])) |
paul@162 | 828 | |
paul@162 | 829 | for t in new_slots: |
paul@162 | 830 | insort_left(slots, t) |
paul@162 | 831 | |
paul@162 | 832 | def partition_by_day(slots): |
paul@162 | 833 | |
paul@162 | 834 | """ |
paul@162 | 835 | Return a mapping from dates to time points provided by 'slots'. |
paul@162 | 836 | """ |
paul@162 | 837 | |
paul@162 | 838 | d = {} |
paul@162 | 839 | |
paul@455 | 840 | for point, value in slots: |
paul@455 | 841 | day = point.point.date() |
paul@162 | 842 | if not d.has_key(day): |
paul@162 | 843 | d[day] = [] |
paul@455 | 844 | d[day].append((point, value)) |
paul@162 | 845 | |
paul@162 | 846 | return d |
paul@153 | 847 | |
paul@876 | 848 | def add_empty_days(days, tzid, start=None, end=None): |
paul@279 | 849 | |
paul@876 | 850 | """ |
paul@876 | 851 | Add empty days to 'days' between busy days, and optionally from the given |
paul@876 | 852 | 'start' day and until the given 'end' day. |
paul@876 | 853 | """ |
paul@279 | 854 | |
paul@888 | 855 | last_day = start - timedelta(1) |
paul@279 | 856 | all_days = days.keys() |
paul@279 | 857 | all_days.sort() |
paul@279 | 858 | |
paul@279 | 859 | for day in all_days: |
paul@279 | 860 | if last_day: |
paul@279 | 861 | empty_day = last_day + timedelta(1) |
paul@279 | 862 | while empty_day < day: |
paul@455 | 863 | days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] |
paul@279 | 864 | empty_day += timedelta(1) |
paul@876 | 865 | last_day = day |
paul@876 | 866 | |
paul@876 | 867 | if end: |
paul@876 | 868 | empty_day = last_day + timedelta(1) |
paul@876 | 869 | while empty_day < end: |
paul@876 | 870 | days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] |
paul@876 | 871 | empty_day += timedelta(1) |
paul@279 | 872 | |
paul@114 | 873 | def get_spans(slots): |
paul@114 | 874 | |
paul@533 | 875 | "Inspect the given 'slots', returning a mapping of period keys to spans." |
paul@114 | 876 | |
paul@455 | 877 | points = [point for point, active in slots] |
paul@114 | 878 | spans = {} |
paul@114 | 879 | |
paul@449 | 880 | for _point, active in slots: |
paul@458 | 881 | for p in active: |
paul@458 | 882 | if p: |
paul@458 | 883 | key = p.get_key() |
paul@529 | 884 | start_slot = bisect_left(points, p.get_start()) |
paul@529 | 885 | end_slot = bisect_left(points, p.get_end()) |
paul@185 | 886 | spans[key] = end_slot - start_slot |
paul@114 | 887 | |
paul@114 | 888 | return spans |
paul@114 | 889 | |
paul@48 | 890 | # vim: tabstop=4 expandtab shiftwidth=4 |