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