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