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 Comparable: 32 33 "A date/datetime wrapper that allows comparisons with other types." 34 35 def __init__(self, dt): 36 self.dt = dt 37 38 def __cmp__(self, other): 39 dt = None 40 odt = None 41 42 # Find any dates/datetimes. 43 44 if isinstance(self.dt, date): 45 dt = self.dt 46 if isinstance(other, date): 47 odt = other 48 elif isinstance(other, Comparable): 49 if isinstance(other.dt, date): 50 odt = other.dt 51 else: 52 other = other.dt 53 54 if dt and odt: 55 return cmp(dt, odt) 56 elif dt: 57 return other.__rcmp__(dt) 58 elif odt: 59 return self.dt.__cmp__(odt) 60 else: 61 return self.dt.__cmp__(other) 62 63 class PointInTime: 64 65 "A base class for special values." 66 67 pass 68 69 class StartOfTime(PointInTime): 70 71 "A special value that compares earlier than other values." 72 73 def __cmp__(self, other): 74 if isinstance(other, StartOfTime): 75 return 0 76 else: 77 return -1 78 79 def __rcmp__(self, other): 80 return -self.__cmp__(other) 81 82 def __nonzero__(self): 83 return False 84 85 class EndOfTime(PointInTime): 86 87 "A special value that compares later than other values." 88 89 def __cmp__(self, other): 90 if isinstance(other, EndOfTime): 91 return 0 92 else: 93 return 1 94 95 def __rcmp__(self, other): 96 return -self.__cmp__(other) 97 98 def __nonzero__(self): 99 return False 100 101 class PeriodBase: 102 103 "A basic period abstraction." 104 105 def as_tuple(self): 106 return self.start, self.end 107 108 def __hash__(self): 109 return hash((self.get_start(), self.get_end())) 110 111 def __cmp__(self, other): 112 113 "Return a comparison result against 'other' using points in time." 114 115 if isinstance(other, PeriodBase): 116 return cmp( 117 (Comparable(self.get_start_point() or StartOfTime()), Comparable(self.get_end_point() or EndOfTime())), 118 (Comparable(other.get_start_point() or StartOfTime()), Comparable(other.get_end_point() or EndOfTime())) 119 ) 120 else: 121 return 1 122 123 def overlaps(self, other): 124 return Comparable(self.get_end_point()) > Comparable(other.get_start_point()) and \ 125 Comparable(self.get_start_point()) < Comparable(other.get_end_point()) 126 127 def get_key(self): 128 return self.get_start(), self.get_end() 129 130 # Datetime and metadata methods. 131 132 def get_start(self): 133 return self.start 134 135 def get_end(self): 136 return self.end 137 138 def get_start_attr(self): 139 return get_datetime_attributes(self.start, self.tzid) 140 141 def get_end_attr(self): 142 return get_datetime_attributes(self.end, self.tzid) 143 144 def get_start_item(self): 145 return self.get_start(), self.get_start_attr() 146 147 def get_end_item(self): 148 return self.get_end(), self.get_end_attr() 149 150 def get_start_point(self): 151 return self.start 152 153 def get_end_point(self): 154 return self.end 155 156 def get_duration(self): 157 return self.get_end_point() - self.get_start_point() 158 159 class Period(PeriodBase): 160 161 "A simple period abstraction." 162 163 def __init__(self, start, end, tzid=None, origin=None): 164 165 """ 166 Initialise a period with the given 'start' and 'end', having a 167 contextual 'tzid', if specified, and an indicated 'origin'. 168 169 All metadata from the start and end points are derived from the supplied 170 dates/datetimes. 171 """ 172 173 self.start = isinstance(start, date) and start or isinstance(start, PointInTime) and start or get_datetime(start) or StartOfTime() 174 self.end = isinstance(end, date) and end or isinstance(end, PointInTime) and end or get_datetime(end) or EndOfTime() 175 self.tzid = tzid 176 self.origin = origin 177 178 def as_tuple(self): 179 return self.start, self.end, self.tzid, self.origin 180 181 def __repr__(self): 182 return "Period%r" % (self.as_tuple(),) 183 184 # Datetime and metadata methods. 185 186 def get_tzid(self): 187 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 188 189 def get_start_point(self): 190 start = self.get_start() 191 return isinstance(start, PointInTime) and start or to_utc_datetime(start, self.get_tzid()) 192 193 def get_end_point(self): 194 end = self.get_end() 195 return isinstance(end, PointInTime) and end or to_utc_datetime(end, self.get_tzid()) 196 197 # Period and event recurrence logic. 198 199 def is_replaced(self, recurrenceids): 200 201 """ 202 Return whether this period refers to one of the 'recurrenceids'. 203 The 'recurrenceids' should be normalised to UTC datetimes according to 204 time zone information provided by their objects or be floating dates or 205 datetimes requiring conversion using contextual time zone information. 206 """ 207 208 for recurrenceid in recurrenceids: 209 if self.is_affected(recurrenceid): 210 return recurrenceid 211 return None 212 213 def is_affected(self, recurrenceid): 214 215 """ 216 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 217 should be normalised to UTC datetimes according to time zone information 218 provided by their objects. Otherwise, this period's contextual time zone 219 information is used to convert any date or floating datetime 220 representation to a point in time. 221 """ 222 223 if not recurrenceid: 224 return None 225 d = get_recurrence_start(recurrenceid) 226 dt = get_recurrence_start_point(recurrenceid, self.tzid) 227 if self.get_start() == d or self.get_start_point() == dt: 228 return recurrenceid 229 return None 230 231 class FreeBusyPeriod(PeriodBase): 232 233 "A free/busy record abstraction." 234 235 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None): 236 237 """ 238 Initialise a free/busy period with the given 'start' and 'end' points, 239 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 240 details. 241 242 An additional 'expires' parameter can be used to indicate an expiry 243 datetime in conjunction with free/busy offers made when countering 244 event proposals. 245 """ 246 247 self.start = isinstance(start, datetime) and start or get_datetime(start) 248 self.end = isinstance(end, datetime) and end or get_datetime(end) 249 self.uid = uid 250 self.transp = transp 251 self.recurrenceid = recurrenceid 252 self.summary = summary 253 self.organiser = organiser 254 self.expires = expires 255 256 def as_tuple(self, strings_only=False): 257 258 """ 259 Return the initialisation parameter tuple, converting false value 260 parameters to strings if 'strings_only' is set to a true value. 261 """ 262 263 null = lambda x: (strings_only and [""] or [x])[0] 264 return ( 265 strings_only and format_datetime(self.get_start_point()) or self.start, 266 strings_only and format_datetime(self.get_end_point()) or self.end, 267 self.uid or null(self.uid), 268 self.transp or strings_only and "OPAQUE" or None, 269 self.recurrenceid or null(self.recurrenceid), 270 self.summary or null(self.summary), 271 self.organiser or null(self.organiser), 272 self.expires or null(self.expires) 273 ) 274 275 def __cmp__(self, other): 276 277 """ 278 Compare this object to 'other', employing the uid if the periods 279 involved are the same. 280 """ 281 282 result = PeriodBase.__cmp__(self, other) 283 if result == 0 and isinstance(other, FreeBusyPeriod): 284 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 285 else: 286 return result 287 288 def get_key(self): 289 return self.uid, self.recurrenceid, self.get_start() 290 291 def __repr__(self): 292 return "FreeBusyPeriod%r" % (self.as_tuple(),) 293 294 # Period and event recurrence logic. 295 296 def is_replaced(self, recurrences): 297 298 """ 299 Return whether this period refers to one of the 'recurrences'. 300 The 'recurrences' must be UTC datetimes corresponding to the start of 301 the period described by a recurrence. 302 """ 303 304 for recurrence in recurrences: 305 if self.is_affected(recurrence): 306 return True 307 return False 308 309 def is_affected(self, recurrence): 310 311 """ 312 Return whether this period refers to 'recurrence'. The 'recurrence' must 313 be a UTC datetime corresponding to the start of the period described by 314 a recurrence. 315 """ 316 317 return recurrence and self.get_start_point() == recurrence 318 319 class RecurringPeriod(Period): 320 321 """ 322 A period with iCalendar metadata attributes and origin information from an 323 object. 324 """ 325 326 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 327 Period.__init__(self, start, end, tzid, origin) 328 self.start_attr = start_attr 329 self.end_attr = end_attr 330 331 def get_start_attr(self): 332 return self.start_attr 333 334 def get_end_attr(self): 335 return self.end_attr 336 337 def as_tuple(self): 338 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 339 340 def __repr__(self): 341 return "RecurringPeriod%r" % (self.as_tuple(),) 342 343 # Time and period management. 344 345 def can_schedule(freebusy, periods, uid, recurrenceid): 346 347 """ 348 Return whether the 'freebusy' list can accommodate the given 'periods' 349 employing the specified 'uid' and 'recurrenceid'. 350 """ 351 352 for conflict in have_conflict(freebusy, periods, True): 353 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 354 return False 355 356 return True 357 358 def have_conflict(freebusy, periods, get_conflicts=False): 359 360 """ 361 Return whether any period in 'freebusy' overlaps with the given 'periods', 362 returning a collection of such overlapping periods if 'get_conflicts' is 363 set to a true value. 364 """ 365 366 conflicts = set() 367 for p in periods: 368 overlapping = period_overlaps(freebusy, p, get_conflicts) 369 if overlapping: 370 if get_conflicts: 371 conflicts.update(overlapping) 372 else: 373 return True 374 375 if get_conflicts: 376 return conflicts 377 else: 378 return False 379 380 def insert_period(freebusy, period): 381 382 "Insert into 'freebusy' the given 'period'." 383 384 i = bisect_left(freebusy, period) 385 if i == len(freebusy): 386 freebusy.append(period) 387 elif freebusy[i] != period: 388 freebusy.insert(i, period) 389 390 def remove_period(freebusy, uid, recurrenceid=None): 391 392 """ 393 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 394 (which if omitted causes the "parent" object's periods to be referenced). 395 """ 396 397 removed = False 398 i = 0 399 while i < len(freebusy): 400 fb = freebusy[i] 401 if fb.uid == uid and fb.recurrenceid == recurrenceid: 402 del freebusy[i] 403 removed = True 404 else: 405 i += 1 406 407 return removed 408 409 def remove_additional_periods(freebusy, uid, recurrenceids=None): 410 411 """ 412 Remove from 'freebusy' all periods associated with 'uid' having a 413 recurrence identifier indicating an additional or modified period. 414 415 If 'recurrenceids' is specified, remove all periods associated with 'uid' 416 that do not have a recurrence identifier in the given list. 417 """ 418 419 i = 0 420 while i < len(freebusy): 421 fb = freebusy[i] 422 if fb.uid == uid and fb.recurrenceid and ( 423 recurrenceids is None or 424 recurrenceids is not None and fb.recurrenceid not in recurrenceids 425 ): 426 del freebusy[i] 427 else: 428 i += 1 429 430 def remove_affected_period(freebusy, uid, start): 431 432 """ 433 Remove from 'freebusy' a period associated with 'uid' that provides an 434 occurrence starting at the given 'start' (provided by a recurrence 435 identifier, converted to a datetime). A recurrence identifier is used to 436 provide an alternative time period whilst also acting as a reference to the 437 originally-defined occurrence. 438 """ 439 440 search = Period(start, start) 441 found = bisect_left(freebusy, search) 442 443 while found < len(freebusy): 444 fb = freebusy[found] 445 446 # Stop looking if the start no longer matches the recurrence identifier. 447 448 if fb.get_start_point() != search.get_start_point(): 449 return 450 451 # If the period belongs to the parent object, remove it and return. 452 453 if not fb.recurrenceid and uid == fb.uid: 454 del freebusy[found] 455 break 456 457 # Otherwise, keep looking for a matching period. 458 459 found += 1 460 461 def periods_from(freebusy, period): 462 463 "Return the entries in 'freebusy' at or after 'period'." 464 465 first = bisect_left(freebusy, period) 466 return freebusy[first:] 467 468 def periods_until(freebusy, period): 469 470 "Return the entries in 'freebusy' before 'period'." 471 472 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) 473 return freebusy[:last] 474 475 def get_overlapping(freebusy, period): 476 477 """ 478 Return the entries in 'freebusy' providing periods overlapping with 479 'period'. 480 """ 481 482 # Find the range of periods potentially overlapping the period in the 483 # free/busy collection. 484 485 startpoints = periods_until(freebusy, period) 486 487 # Find the range of periods potentially overlapping the period in a version 488 # of the free/busy collection sorted according to end datetimes. 489 490 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 491 endpoints.sort() 492 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 493 endpoints = endpoints[first:] 494 495 overlapping = set() 496 497 for p, fb in endpoints: 498 if fb.overlaps(period): 499 overlapping.add(fb) 500 501 overlapping = list(overlapping) 502 overlapping.sort() 503 return overlapping 504 505 def period_overlaps(freebusy, period, get_periods=False): 506 507 """ 508 Return whether any period in 'freebusy' overlaps with the given 'period', 509 returning a collection of overlapping periods if 'get_periods' is set to a 510 true value. 511 """ 512 513 overlapping = get_overlapping(freebusy, period) 514 515 if get_periods: 516 return overlapping 517 else: 518 return len(overlapping) != 0 519 520 def remove_overlapping(freebusy, period): 521 522 "Remove from 'freebusy' all periods overlapping with 'period'." 523 524 overlapping = get_overlapping(freebusy, period) 525 526 if overlapping: 527 for fb in overlapping: 528 freebusy.remove(fb) 529 530 def replace_overlapping(freebusy, period, replacements): 531 532 """ 533 Replace existing periods in 'freebusy' within the given 'period', using the 534 given 'replacements'. 535 """ 536 537 remove_overlapping(freebusy, period) 538 for replacement in replacements: 539 insert_period(freebusy, replacement) 540 541 def coalesce_freebusy(freebusy): 542 543 "Coalesce the periods in 'freebusy'." 544 545 if not freebusy: 546 return freebusy 547 548 fb = [] 549 start = freebusy[0].get_start_point() 550 end = freebusy[0].get_end_point() 551 552 for period in freebusy[1:]: 553 if period.get_start_point() > end: 554 fb.append(FreeBusyPeriod(start, end)) 555 start = period.get_start_point() 556 end = period.get_end_point() 557 else: 558 end = max(end, period.get_end_point()) 559 560 fb.append(FreeBusyPeriod(start, end)) 561 return fb 562 563 def invert_freebusy(freebusy): 564 565 "Return the free periods from 'freebusy'." 566 567 if not freebusy: 568 return None 569 570 fb = coalesce_freebusy(freebusy) 571 free = [] 572 start = fb[0].get_end_point() 573 574 for period in fb[1:]: 575 free.append(FreeBusyPeriod(start, period.get_start_point())) 576 start = period.get_end_point() 577 578 return free 579 580 # Period layout. 581 582 def get_scale(periods, tzid, view_period=None): 583 584 """ 585 Return an ordered time scale from the given list of 'periods'. 586 587 The given 'tzid' is used to make sure that the times are defined according 588 to the chosen time zone. 589 590 An optional 'view_period' is used to constrain the scale to the given 591 period. 592 593 The returned scale is a mapping from time to (starting, ending) tuples, 594 where starting and ending are collections of periods. 595 """ 596 597 scale = {} 598 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 599 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 600 601 for p in periods: 602 603 # Add a point and this event to the starting list. 604 605 start = to_timezone(p.get_start(), tzid) 606 start = view_start and max(start, view_start) or start 607 if not scale.has_key(start): 608 scale[start] = [], [] 609 scale[start][0].append(p) 610 611 # Add a point and this event to the ending list. 612 613 end = to_timezone(p.get_end(), tzid) 614 end = view_end and min(end, view_end) or end 615 if not scale.has_key(end): 616 scale[end] = [], [] 617 scale[end][1].append(p) 618 619 return scale 620 621 class Point: 622 623 "A qualified point in time." 624 625 PRINCIPAL, REPEATED = 0, 1 626 627 def __init__(self, point, indicator=None): 628 self.point = point 629 self.indicator = indicator or self.PRINCIPAL 630 631 def __hash__(self): 632 return hash((self.point, self.indicator)) 633 634 def __cmp__(self, other): 635 if isinstance(other, Point): 636 return cmp((self.point, self.indicator), (other.point, other.indicator)) 637 elif isinstance(other, datetime): 638 return cmp(self.point, other) 639 else: 640 return 1 641 642 def __eq__(self, other): 643 return self.__cmp__(other) == 0 644 645 def __ne__(self, other): 646 return not self == other 647 648 def __lt__(self, other): 649 return self.__cmp__(other) < 0 650 651 def __le__(self, other): 652 return self.__cmp__(other) <= 0 653 654 def __gt__(self, other): 655 return not self <= other 656 657 def __ge__(self, other): 658 return not self < other 659 660 def __repr__(self): 661 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 662 663 def get_slots(scale): 664 665 """ 666 Return an ordered list of time slots from the given 'scale'. 667 668 Each slot is a tuple containing details of a point in time for the start of 669 the slot, together with a list of parallel event periods. 670 671 Each point in time is described as a Point representing the actual point in 672 time together with an indicator of the nature of the point in time (as a 673 principal point in a time scale or as a repeated point used to terminate 674 events occurring for an instant in time). 675 """ 676 677 slots = [] 678 active = [] 679 680 points = scale.items() 681 points.sort() 682 683 for point, (starting, ending) in points: 684 ending = set(ending) 685 instants = ending.intersection(starting) 686 687 # Discard all active events ending at or before this start time. 688 # Free up the position in the active list. 689 690 for t in ending.difference(instants): 691 i = active.index(t) 692 active[i] = None 693 694 # For each event starting at the current point, fill any newly-vacated 695 # position or add to the end of the active list. 696 697 for t in starting: 698 try: 699 i = active.index(None) 700 active[i] = t 701 except ValueError: 702 active.append(t) 703 704 # Discard vacant positions from the end of the active list. 705 706 while active and active[-1] is None: 707 active.pop() 708 709 # Add an entry for the time point before "instants". 710 711 slots.append((Point(point), active[:])) 712 713 # Discard events ending at the same time as they began. 714 715 if instants: 716 for t in instants: 717 i = active.index(t) 718 active[i] = None 719 720 # Discard vacant positions from the end of the active list. 721 722 while active and active[-1] is None: 723 active.pop() 724 725 # Add another entry for the time point after "instants". 726 727 slots.append((Point(point, Point.REPEATED), active[:])) 728 729 return slots 730 731 def add_day_start_points(slots, tzid): 732 733 """ 734 Introduce into the 'slots' any day start points required by multi-day 735 periods. The 'tzid' is required to make sure that appropriate time zones 736 are chosen and not necessarily those provided by the existing time points. 737 """ 738 739 new_slots = [] 740 current_date = None 741 previously_active = [] 742 743 for point, active in slots: 744 start_of_day = get_start_of_day(point.point, tzid) 745 this_date = point.point.date() 746 747 # For each new day, add a slot for the start of the day where periods 748 # are active and where no such slot already exists. 749 750 if this_date != current_date: 751 752 # Fill in days where events remain active. 753 754 if current_date: 755 current_date += timedelta(1) 756 while current_date < this_date: 757 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 758 current_date += timedelta(1) 759 else: 760 current_date = this_date 761 762 # Add any continuing periods. 763 764 if point.point != start_of_day: 765 new_slots.append((Point(start_of_day), previously_active)) 766 767 # Add the currently active periods at this point in time. 768 769 previously_active = active 770 771 for t in new_slots: 772 insort_left(slots, t) 773 774 def add_slots(slots, points): 775 776 """ 777 Introduce into the 'slots' entries for those in 'points' that are not 778 already present, propagating active periods from time points preceding 779 those added. 780 """ 781 782 new_slots = [] 783 784 for point in points: 785 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 786 if i < len(slots) and slots[i][0] == point: 787 continue 788 789 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 790 791 for t in new_slots: 792 insort_left(slots, t) 793 794 def partition_by_day(slots): 795 796 """ 797 Return a mapping from dates to time points provided by 'slots'. 798 """ 799 800 d = {} 801 802 for point, value in slots: 803 day = point.point.date() 804 if not d.has_key(day): 805 d[day] = [] 806 d[day].append((point, value)) 807 808 return d 809 810 def add_empty_days(days, tzid, start=None, end=None): 811 812 """ 813 Add empty days to 'days' between busy days, and optionally from the given 814 'start' day and until the given 'end' day. 815 """ 816 817 last_day = start - timedelta(1) 818 all_days = days.keys() 819 all_days.sort() 820 821 for day in all_days: 822 if last_day: 823 empty_day = last_day + timedelta(1) 824 while empty_day < day: 825 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 826 empty_day += timedelta(1) 827 last_day = day 828 829 if end: 830 empty_day = last_day + timedelta(1) 831 while empty_day < end: 832 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 833 empty_day += timedelta(1) 834 835 def get_spans(slots): 836 837 "Inspect the given 'slots', returning a mapping of period keys to spans." 838 839 points = [point for point, active in slots] 840 spans = {} 841 842 for _point, active in slots: 843 for p in active: 844 if p: 845 key = p.get_key() 846 start_slot = bisect_left(points, p.get_start()) 847 end_slot = bisect_left(points, p.get_end()) 848 spans[key] = end_slot - start_slot 849 850 return spans 851 852 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 853 854 """ 855 Update the free/busy details with the given 'periods', 'transp' setting, 856 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 857 858 An optional 'expires' datetime string indicates the expiry time of any 859 free/busy offer. 860 """ 861 862 remove_period(freebusy, uid, recurrenceid) 863 864 for p in periods: 865 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 866 867 # vim: tabstop=4 expandtab shiftwidth=4