1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from bisect import bisect_left, bisect_right, insort_left 23 from datetime import date, datetime, timedelta 24 from imiptools.dates import format_datetime, get_datetime, \ 25 get_datetime_attributes, \ 26 get_recurrence_start, get_recurrence_start_point, \ 27 get_start_of_day, \ 28 get_tzid, \ 29 to_timezone, to_utc_datetime 30 31 class Period: 32 33 "A basic period abstraction." 34 35 def __init__(self, start, end, tzid=None, origin=None): 36 37 """ 38 Initialise a period with the given 'start' and 'end', having a 39 contextual 'tzid', if specified, and an indicated 'origin'. 40 41 All metadata from the start and end points are derived from the supplied 42 dates/datetimes. 43 """ 44 45 self.start = isinstance(start, date) and start or get_datetime(start) 46 self.end = isinstance(end, date) and end or get_datetime(end) 47 self.tzid = tzid 48 self.origin = origin 49 50 def as_tuple(self): 51 return self.start, self.end, self.tzid, self.origin 52 53 def __hash__(self): 54 return hash((self.get_start(), self.get_end())) 55 56 def __cmp__(self, other): 57 58 """ 59 Return a comparison result against 'other' using points in time, 60 employing the time zone context to convert dates. 61 """ 62 63 if isinstance(other, Period): 64 return cmp( 65 (self.get_start_point(), self.get_end_point()), 66 (other.get_start_point(), other.get_end_point()) 67 ) 68 else: 69 return 1 70 71 def get_key(self): 72 return self.get_start(), self.get_end() 73 74 def __repr__(self): 75 return "Period(%r)" % (self.as_tuple(),) 76 77 # Datetime metadata methods. 78 79 def get_start(self): 80 return self.start 81 82 def get_end(self): 83 return self.end 84 85 def get_tzid(self): 86 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 87 88 def get_start_attr(self): 89 return get_datetime_attributes(self.start, self.tzid) 90 91 def get_end_attr(self): 92 return get_datetime_attributes(self.end, self.tzid) 93 94 def get_start_item(self): 95 return self.get_start(), self.get_start_attr() 96 97 def get_end_item(self): 98 return self.get_end(), self.get_end_attr() 99 100 def get_start_point(self): 101 return to_utc_datetime(self.get_start(), self.get_tzid()) 102 103 def get_end_point(self): 104 return to_utc_datetime(self.get_end(), self.get_tzid()) 105 106 class FreeBusyPeriod(Period): 107 108 "A free/busy record abstraction." 109 110 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, tzid=None): 111 112 """ 113 Initialise a free/busy period with the given 'start' and 'end' limits, 114 with an optional 'tzid', plus any 'uid', 'transp', 'recurrenceid', 115 'summary' and 'organiser' details. 116 """ 117 118 Period.__init__(self, start, end, tzid) 119 self.uid = uid 120 self.transp = transp 121 self.recurrenceid = recurrenceid 122 self.summary = summary 123 self.organiser = organiser 124 125 def as_tuple(self, strings_only=False): 126 127 """ 128 Return the initialisation parameter tuple, converting false value 129 parameters to strings if 'strings_only' is set to a true value. 130 """ 131 132 null = lambda x: (strings_only and [""] or [x])[0] 133 return ( 134 format_datetime(self.get_start_point()), 135 format_datetime(self.get_end_point()), 136 self.uid or null(self.uid), 137 self.transp or strings_only and "OPAQUE" or None, 138 self.recurrenceid or null(self.recurrenceid), 139 self.summary or null(self.summary), 140 self.organiser or null(self.organiser) 141 ) 142 143 def __cmp__(self, other): 144 145 """ 146 Compare this object to 'other', employing the uid if the periods 147 involved are the same. 148 """ 149 150 result = Period.__cmp__(self, other) 151 if result == 0 and isinstance(other, FreeBusyPeriod): 152 return cmp(self.uid, other.uid) 153 else: 154 return result 155 156 def get_key(self): 157 return self.uid, self.recurrenceid, self.get_start() 158 159 def __repr__(self): 160 return "FreeBusyPeriod(%r)" % (self.as_tuple(),) 161 162 class RecurringPeriod(Period): 163 164 """ 165 A period with iCalendar metadata attributes and origin information from an 166 object. 167 """ 168 169 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 170 Period.__init__(self, start, end, tzid, origin) 171 self.start_attr = start_attr 172 self.end_attr = end_attr 173 174 def get_start_attr(self): 175 return self.start_attr 176 177 def get_end_attr(self): 178 return self.end_attr 179 180 def as_tuple(self): 181 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 182 183 def __repr__(self): 184 return "RecurringPeriod(%r)" % (self.as_tuple(),) 185 186 # Period and event recurrence logic. 187 188 def is_replaced(period, recurrenceids, tzid): 189 190 """ 191 Return whether 'period' refers to one of the 'recurrenceids', interpreted 192 using 'tzid' if necessary. The 'recurrenceids' should be normalised to UTC 193 datetimes according to time zone information provided by their objects. 194 """ 195 196 for s in recurrenceids: 197 if is_affected(period, s, tzid): 198 return s 199 return None 200 201 def is_affected(period, recurrenceid, tzid): 202 203 """ 204 Return whether 'period' refers to 'recurrenceid', interpreted using 'tzid' 205 if necessary. The 'recurrenceid' should be normalised to UTC datetimes 206 according to time zone information provided by their objects. Otherwise, 207 'tzid' is used to convert any date or floating datetime representation to a 208 point in time. 209 """ 210 211 if not recurrenceid: 212 return None 213 d = get_recurrence_start(recurrenceid) 214 dt = get_recurrence_start_point(recurrenceid, tzid) 215 if period.get_start() == d or period.get_start_point() == dt: 216 return recurrenceid 217 return None 218 219 # Time and period management. 220 221 def can_schedule(freebusy, periods, uid, recurrenceid): 222 223 """ 224 Return whether the 'freebusy' list can accommodate the given 'periods' 225 employing the specified 'uid' and 'recurrenceid'. 226 """ 227 228 for conflict in have_conflict(freebusy, periods, True): 229 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 230 return False 231 232 return True 233 234 def have_conflict(freebusy, periods, get_conflicts=False): 235 236 """ 237 Return whether any period in 'freebusy' overlaps with the given 'periods', 238 returning a collection of such overlapping periods if 'get_conflicts' is 239 set to a true value. 240 """ 241 242 conflicts = set() 243 for p in periods: 244 overlapping = period_overlaps(freebusy, p, get_conflicts) 245 if overlapping: 246 if get_conflicts: 247 conflicts.update(overlapping) 248 else: 249 return True 250 251 if get_conflicts: 252 return conflicts 253 else: 254 return False 255 256 def insert_period(freebusy, period): 257 258 "Insert into 'freebusy' the given 'period'." 259 260 insort_left(freebusy, period) 261 262 def remove_period(freebusy, uid, recurrenceid=None): 263 264 """ 265 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 266 (which if omitted causes the "parent" object's periods to be referenced). 267 """ 268 269 removed = False 270 i = 0 271 while i < len(freebusy): 272 fb = freebusy[i] 273 if fb.uid == uid and fb.recurrenceid == recurrenceid: 274 del freebusy[i] 275 removed = True 276 else: 277 i += 1 278 279 return removed 280 281 def remove_additional_periods(freebusy, uid, recurrenceids=None): 282 283 """ 284 Remove from 'freebusy' all periods associated with 'uid' having a 285 recurrence identifier indicating an additional or modified period. 286 287 If 'recurrenceids' is specified, remove all periods associated with 'uid' 288 that do not have a recurrence identifier in the given list. 289 """ 290 291 i = 0 292 while i < len(freebusy): 293 fb = freebusy[i] 294 if fb.uid == uid and fb.recurrenceid and ( 295 recurrenceids is None or 296 recurrenceids is not None and fb.recurrenceid not in recurrenceids 297 ): 298 del freebusy[i] 299 else: 300 i += 1 301 302 def remove_affected_period(freebusy, uid, start): 303 304 """ 305 Remove from 'freebusy' a period associated with 'uid' that provides an 306 occurrence starting at the given 'start' (provided by a recurrence 307 identifier, converted to a datetime). A recurrence identifier is used to 308 provide an alternative time period whilst also acting as a reference to the 309 originally-defined occurrence. 310 """ 311 312 search = Period(start, start) 313 found = bisect_left(freebusy, search) 314 315 while found < len(freebusy): 316 fb = freebusy[found] 317 318 # Stop looking if the start no longer matches the recurrence identifier. 319 320 if fb.get_start_point() != search.get_start_point(): 321 return 322 323 # If the period belongs to the parent object, remove it and return. 324 325 if not fb.recurrenceid and uid == fb.uid: 326 del freebusy[found] 327 break 328 329 # Otherwise, keep looking for a matching period. 330 331 found += 1 332 333 def get_overlapping(freebusy, period): 334 335 """ 336 Return the entries in 'freebusy' providing periods overlapping with 337 'period'. 338 """ 339 340 # Find the range of periods potentially overlapping the period in the 341 # free/busy collection. 342 343 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) 344 startpoints = freebusy[:last] 345 346 # Find the range of periods potentially overlapping the period in a version 347 # of the free/busy collection sorted according to end datetimes. 348 349 endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints] 350 endpoints.sort() 351 first = bisect_left(endpoints, (period.get_start_point(),)) 352 endpoints = endpoints[first:] 353 354 overlapping = set() 355 356 for end, start, fb in endpoints: 357 if end > period.get_start_point() and start < period.get_end_point(): 358 overlapping.add(fb) 359 360 overlapping = list(overlapping) 361 overlapping.sort() 362 return overlapping 363 364 def period_overlaps(freebusy, period, get_periods=False): 365 366 """ 367 Return whether any period in 'freebusy' overlaps with the given 'period', 368 returning a collection of overlapping periods if 'get_periods' is set to a 369 true value. 370 """ 371 372 overlapping = get_overlapping(freebusy, period) 373 374 if get_periods: 375 return overlapping 376 else: 377 return len(overlapping) != 0 378 379 def remove_overlapping(freebusy, period): 380 381 "Remove from 'freebusy' all periods overlapping with 'period'." 382 383 overlapping = get_overlapping(freebusy, period) 384 385 if overlapping: 386 for fb in overlapping: 387 freebusy.remove(fb) 388 389 def replace_overlapping(freebusy, period, replacements): 390 391 """ 392 Replace existing periods in 'freebusy' within the given 'period', using the 393 given 'replacements'. 394 """ 395 396 remove_overlapping(freebusy, period) 397 for replacement in replacements: 398 insert_period(freebusy, replacement) 399 400 # Period layout. 401 402 def get_scale(periods, tzid): 403 404 """ 405 Return an ordered time scale from the given list of 'periods'. 406 407 The given 'tzid' is used to make sure that the times are defined according 408 to the chosen time zone. 409 410 The returned scale is a mapping from time to (starting, ending) tuples, 411 where starting and ending are collections of periods. 412 """ 413 414 scale = {} 415 416 for p in periods: 417 418 # Add a point and this event to the starting list. 419 420 start = to_timezone(p.get_start(), tzid) 421 if not scale.has_key(start): 422 scale[start] = [], [] 423 scale[start][0].append(p) 424 425 # Add a point and this event to the ending list. 426 427 end = to_timezone(p.get_end(), tzid) 428 if not scale.has_key(end): 429 scale[end] = [], [] 430 scale[end][1].append(p) 431 432 return scale 433 434 class Point: 435 436 "A qualified point in time." 437 438 PRINCIPAL, REPEATED = 0, 1 439 440 def __init__(self, point, indicator=None): 441 self.point = point 442 self.indicator = indicator or self.PRINCIPAL 443 444 def __hash__(self): 445 return hash((self.point, self.indicator)) 446 447 def __cmp__(self, other): 448 if isinstance(other, Point): 449 return cmp((self.point, self.indicator), (other.point, other.indicator)) 450 elif isinstance(other, datetime): 451 return cmp(self.point, other) 452 else: 453 return 1 454 455 def __eq__(self, other): 456 return self.__cmp__(other) == 0 457 458 def __ne__(self, other): 459 return not self == other 460 461 def __lt__(self, other): 462 return self.__cmp__(other) < 0 463 464 def __le__(self, other): 465 return self.__cmp__(other) <= 0 466 467 def __gt__(self, other): 468 return not self <= other 469 470 def __ge__(self, other): 471 return not self < other 472 473 def __repr__(self): 474 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 475 476 def get_slots(scale): 477 478 """ 479 Return an ordered list of time slots from the given 'scale'. 480 481 Each slot is a tuple containing details of a point in time for the start of 482 the slot, together with a list of parallel event periods. 483 484 Each point in time is described as a Point representing the actual point in 485 time together with an indicator of the nature of the point in time (as a 486 principal point in a time scale or as a repeated point used to terminate 487 events occurring for an instant in time). 488 """ 489 490 slots = [] 491 active = [] 492 493 points = scale.items() 494 points.sort() 495 496 for point, (starting, ending) in points: 497 ending = set(ending) 498 instants = ending.intersection(starting) 499 500 # Discard all active events ending at or before this start time. 501 # Free up the position in the active list. 502 503 for t in ending.difference(instants): 504 i = active.index(t) 505 active[i] = None 506 507 # For each event starting at the current point, fill any newly-vacated 508 # position or add to the end of the active list. 509 510 for t in starting: 511 try: 512 i = active.index(None) 513 active[i] = t 514 except ValueError: 515 active.append(t) 516 517 # Discard vacant positions from the end of the active list. 518 519 while active and active[-1] is None: 520 active.pop() 521 522 # Add an entry for the time point before "instants". 523 524 slots.append((Point(point), active[:])) 525 526 # Discard events ending at the same time as they began. 527 528 if instants: 529 for t in instants: 530 i = active.index(t) 531 active[i] = None 532 533 # Discard vacant positions from the end of the active list. 534 535 while active and active[-1] is None: 536 active.pop() 537 538 # Add another entry for the time point after "instants". 539 540 slots.append((Point(point, Point.REPEATED), active[:])) 541 542 return slots 543 544 def add_day_start_points(slots, tzid): 545 546 """ 547 Introduce into the 'slots' any day start points required by multi-day 548 periods. The 'tzid' is required to make sure that appropriate time zones 549 are chosen and not necessarily those provided by the existing time points. 550 """ 551 552 new_slots = [] 553 current_date = None 554 previously_active = [] 555 556 for point, active in slots: 557 start_of_day = get_start_of_day(point.point, tzid) 558 this_date = point.point.date() 559 560 # For each new day, add a slot for the start of the day where periods 561 # are active and where no such slot already exists. 562 563 if this_date != current_date: 564 565 # Fill in days where events remain active. 566 567 if current_date: 568 current_date += timedelta(1) 569 while current_date < this_date: 570 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 571 current_date += timedelta(1) 572 else: 573 current_date = this_date 574 575 # Add any continuing periods. 576 577 if point.point != start_of_day: 578 new_slots.append((Point(start_of_day), previously_active)) 579 580 # Add the currently active periods at this point in time. 581 582 previously_active = active 583 584 for t in new_slots: 585 insort_left(slots, t) 586 587 def add_slots(slots, points): 588 589 """ 590 Introduce into the 'slots' entries for those in 'points' that are not 591 already present, propagating active periods from time points preceding 592 those added. 593 """ 594 595 new_slots = [] 596 597 for point in points: 598 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 599 if i < len(slots) and slots[i][0] == point: 600 continue 601 602 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 603 604 for t in new_slots: 605 insort_left(slots, t) 606 607 def partition_by_day(slots): 608 609 """ 610 Return a mapping from dates to time points provided by 'slots'. 611 """ 612 613 d = {} 614 615 for point, value in slots: 616 day = point.point.date() 617 if not d.has_key(day): 618 d[day] = [] 619 d[day].append((point, value)) 620 621 return d 622 623 def add_empty_days(days, tzid): 624 625 "Add empty days to 'days' between busy days." 626 627 last_day = None 628 all_days = days.keys() 629 all_days.sort() 630 631 for day in all_days: 632 if last_day: 633 empty_day = last_day + timedelta(1) 634 while empty_day < day: 635 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 636 empty_day += timedelta(1) 637 last_day = day 638 639 def get_spans(slots): 640 641 "Inspect the given 'slots', returning a mapping of period keys to spans." 642 643 points = [point for point, active in slots] 644 spans = {} 645 646 for _point, active in slots: 647 for p in active: 648 if p: 649 key = p.get_key() 650 start_slot = bisect_left(points, p.get_start()) 651 end_slot = bisect_left(points, p.get_end()) 652 spans[key] = end_slot - start_slot 653 654 return spans 655 656 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 657 658 """ 659 Update the free/busy details with the given 'periods', 'transp' setting, 660 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 661 """ 662 663 remove_period(freebusy, uid, recurrenceid) 664 665 for p in periods: 666 insert_period(freebusy, FreeBusyPeriod(p.get_start(), p.get_end(), uid, transp, recurrenceid, summary, organiser, p.get_tzid())) 667 668 # vim: tabstop=4 expandtab shiftwidth=4