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): 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 The returned scale is a mapping from time to (starting, ending) tuples, 585 where starting and ending are collections of periods. 586 """ 587 588 scale = {} 589 590 for p in periods: 591 592 # Add a point and this event to the starting list. 593 594 start = to_timezone(p.get_start(), tzid) 595 if not scale.has_key(start): 596 scale[start] = [], [] 597 scale[start][0].append(p) 598 599 # Add a point and this event to the ending list. 600 601 end = to_timezone(p.get_end(), tzid) 602 if not scale.has_key(end): 603 scale[end] = [], [] 604 scale[end][1].append(p) 605 606 return scale 607 608 class Point: 609 610 "A qualified point in time." 611 612 PRINCIPAL, REPEATED = 0, 1 613 614 def __init__(self, point, indicator=None): 615 self.point = point 616 self.indicator = indicator or self.PRINCIPAL 617 618 def __hash__(self): 619 return hash((self.point, self.indicator)) 620 621 def __cmp__(self, other): 622 if isinstance(other, Point): 623 return cmp((self.point, self.indicator), (other.point, other.indicator)) 624 elif isinstance(other, datetime): 625 return cmp(self.point, other) 626 else: 627 return 1 628 629 def __eq__(self, other): 630 return self.__cmp__(other) == 0 631 632 def __ne__(self, other): 633 return not self == other 634 635 def __lt__(self, other): 636 return self.__cmp__(other) < 0 637 638 def __le__(self, other): 639 return self.__cmp__(other) <= 0 640 641 def __gt__(self, other): 642 return not self <= other 643 644 def __ge__(self, other): 645 return not self < other 646 647 def __repr__(self): 648 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 649 650 def get_slots(scale): 651 652 """ 653 Return an ordered list of time slots from the given 'scale'. 654 655 Each slot is a tuple containing details of a point in time for the start of 656 the slot, together with a list of parallel event periods. 657 658 Each point in time is described as a Point representing the actual point in 659 time together with an indicator of the nature of the point in time (as a 660 principal point in a time scale or as a repeated point used to terminate 661 events occurring for an instant in time). 662 """ 663 664 slots = [] 665 active = [] 666 667 points = scale.items() 668 points.sort() 669 670 for point, (starting, ending) in points: 671 ending = set(ending) 672 instants = ending.intersection(starting) 673 674 # Discard all active events ending at or before this start time. 675 # Free up the position in the active list. 676 677 for t in ending.difference(instants): 678 i = active.index(t) 679 active[i] = None 680 681 # For each event starting at the current point, fill any newly-vacated 682 # position or add to the end of the active list. 683 684 for t in starting: 685 try: 686 i = active.index(None) 687 active[i] = t 688 except ValueError: 689 active.append(t) 690 691 # Discard vacant positions from the end of the active list. 692 693 while active and active[-1] is None: 694 active.pop() 695 696 # Add an entry for the time point before "instants". 697 698 slots.append((Point(point), active[:])) 699 700 # Discard events ending at the same time as they began. 701 702 if instants: 703 for t in instants: 704 i = active.index(t) 705 active[i] = None 706 707 # Discard vacant positions from the end of the active list. 708 709 while active and active[-1] is None: 710 active.pop() 711 712 # Add another entry for the time point after "instants". 713 714 slots.append((Point(point, Point.REPEATED), active[:])) 715 716 return slots 717 718 def add_day_start_points(slots, tzid): 719 720 """ 721 Introduce into the 'slots' any day start points required by multi-day 722 periods. The 'tzid' is required to make sure that appropriate time zones 723 are chosen and not necessarily those provided by the existing time points. 724 """ 725 726 new_slots = [] 727 current_date = None 728 previously_active = [] 729 730 for point, active in slots: 731 start_of_day = get_start_of_day(point.point, tzid) 732 this_date = point.point.date() 733 734 # For each new day, add a slot for the start of the day where periods 735 # are active and where no such slot already exists. 736 737 if this_date != current_date: 738 739 # Fill in days where events remain active. 740 741 if current_date: 742 current_date += timedelta(1) 743 while current_date < this_date: 744 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 745 current_date += timedelta(1) 746 else: 747 current_date = this_date 748 749 # Add any continuing periods. 750 751 if point.point != start_of_day: 752 new_slots.append((Point(start_of_day), previously_active)) 753 754 # Add the currently active periods at this point in time. 755 756 previously_active = active 757 758 for t in new_slots: 759 insort_left(slots, t) 760 761 def add_slots(slots, points): 762 763 """ 764 Introduce into the 'slots' entries for those in 'points' that are not 765 already present, propagating active periods from time points preceding 766 those added. 767 """ 768 769 new_slots = [] 770 771 for point in points: 772 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 773 if i < len(slots) and slots[i][0] == point: 774 continue 775 776 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 777 778 for t in new_slots: 779 insort_left(slots, t) 780 781 def partition_by_day(slots): 782 783 """ 784 Return a mapping from dates to time points provided by 'slots'. 785 """ 786 787 d = {} 788 789 for point, value in slots: 790 day = point.point.date() 791 if not d.has_key(day): 792 d[day] = [] 793 d[day].append((point, value)) 794 795 return d 796 797 def add_empty_days(days, tzid): 798 799 "Add empty days to 'days' between busy days." 800 801 last_day = None 802 all_days = days.keys() 803 all_days.sort() 804 805 for day in all_days: 806 if last_day: 807 empty_day = last_day + timedelta(1) 808 while empty_day < day: 809 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 810 empty_day += timedelta(1) 811 last_day = day 812 813 def get_spans(slots): 814 815 "Inspect the given 'slots', returning a mapping of period keys to spans." 816 817 points = [point for point, active in slots] 818 spans = {} 819 820 for _point, active in slots: 821 for p in active: 822 if p: 823 key = p.get_key() 824 start_slot = bisect_left(points, p.get_start()) 825 end_slot = bisect_left(points, p.get_end()) 826 spans[key] = end_slot - start_slot 827 828 return spans 829 830 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 831 832 """ 833 Update the free/busy details with the given 'periods', 'transp' setting, 834 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 835 836 An optional 'expires' datetime string indicates the expiry time of any 837 free/busy offer. 838 """ 839 840 remove_period(freebusy, uid, recurrenceid) 841 842 for p in periods: 843 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 844 845 # vim: tabstop=4 expandtab shiftwidth=4