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_datetime, 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 if to_datetime(end, tzid) < to_datetime(until, tzid): 446 self.end = end 447 else: 448 self.end = until 449 self.inclusive = True 450 else: 451 self.end = end 452 self.inclusive = inclusive 453 454 def __iter__(self): 455 456 """ 457 Obtain period instances, starting from the main period. Since counting 458 must start from the first period, filtering from a start date must be 459 done after the instances have been obtained. 460 """ 461 462 start = self.main_period.get_start() 463 464 return RulePeriodIterator(self.main_period, self.tzid, 465 self.selector.select(start, self.end, self.inclusive)) 466 467 class RulePeriodIterator: 468 469 "An iterator over rule periods." 470 471 def __init__(self, main_period, tzid, iterator): 472 self.main_period = main_period 473 self.attr = main_period.get_start_attr() 474 self.duration = main_period.get_duration() 475 self.tzid = tzid 476 self.iterator = iterator 477 478 def next(self): 479 recurrence_start = self.iterator.next() 480 period = make_rule_period(recurrence_start, self.duration, self.attr, self.tzid) 481 482 # Use the main period where it occurs. 483 484 return period == self.main_period and self.main_period or period 485 486 class MergingIterator: 487 488 "An iterator merging ordered collections." 489 490 def __init__(self, iterators): 491 492 "Initialise an iterator merging 'iterators'." 493 494 self.current = [] 495 496 # Populate an ordered collection of (value, iterator) pairs by obtaining 497 # the first value from each iterator. 498 499 for iterator in iterators: 500 t = self.get_next(iterator) 501 if t: 502 self.current.append(t) 503 504 self.current.sort() 505 506 def __iter__(self): 507 return self 508 509 def get_next(self, iterator): 510 511 """ 512 Return a (value, iterator) pair for 'iterator' or None if the iterator 513 has been exhausted. 514 """ 515 516 try: 517 return (iterator.next(), iterator) 518 except StopIteration: 519 return None 520 521 def next(self): 522 523 """ 524 Return the next value in an ordered sequence, choosing it from one of 525 the available iterators. 526 """ 527 528 if not self.current: 529 raise StopIteration 530 531 # Obtain the current value and remove the (value, iterator) pair, 532 # pending insertion of a new pair for the iterator. 533 534 current, iterator = self.current[0] 535 del self.current[0] 536 537 # Get the next value, if any and insert the value and iterator into the 538 # ordered collection. 539 540 t = self.get_next(iterator) 541 if t: 542 insort_left(self.current, t) 543 544 return current 545 546 def get_overlapping(first, second): 547 548 """ 549 Return the entries in the sorted 'first' collection that are overlapping 550 with the given sorted 'second' collection. 551 """ 552 553 if not first or not second: 554 return [] 555 556 # Examine each period in the second collection, attempting to match periods 557 # in the first collection. 558 559 overlapping = set() 560 561 for p2 in second: 562 last_point = p2.get_end_point() 563 564 # Examine the first collection up to the point where no matches will 565 # occur. 566 567 for p1 in first: 568 if p1.get_start_point() > last_point: 569 break 570 elif p1.overlaps(p2): 571 overlapping.add(p1) 572 573 overlapping = list(overlapping) 574 overlapping.sort() 575 return overlapping 576 577 def get_overlapping_members(periods): 578 579 "Return members of the 'periods' collection that overlap with others." 580 581 if not periods: 582 return [] 583 584 l = periods[:] 585 l.sort() 586 587 overlapping = [] 588 589 last = l[0] 590 last_added = None 591 592 for p in l[1:]: 593 if p.get_start_point() < last.get_end_point(): 594 if last_added != last: 595 overlapping.append(last) 596 overlapping.append(p) 597 last_added = p 598 last = p 599 600 return overlapping 601 602 # Period layout. 603 604 def get_scale(periods, tzid, view_period=None): 605 606 """ 607 Return a time scale from the given list of 'periods'. 608 609 The given 'tzid' is used to make sure that the times are defined according 610 to the chosen time zone. 611 612 An optional 'view_period' is used to constrain the scale to the given 613 period. 614 615 The returned scale is a mapping from time to (starting, ending) tuples, 616 where starting and ending are collections of periods. 617 """ 618 619 scale = {} 620 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 621 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 622 623 for p in periods: 624 625 # Add a point and this event to the starting list. 626 627 start = to_timezone(p.get_start(), tzid) 628 start = view_start and max(start, view_start) or start 629 if not scale.has_key(start): 630 scale[start] = [], [] 631 scale[start][0].append(p) 632 633 # Add a point and this event to the ending list. 634 635 end = to_timezone(p.get_end(), tzid) 636 end = view_end and min(end, view_end) or end 637 if not scale.has_key(end): 638 scale[end] = [], [] 639 scale[end][1].append(p) 640 641 return scale 642 643 class Point: 644 645 "A qualified point in time." 646 647 PRINCIPAL, REPEATED = 0, 1 648 649 def __init__(self, point, indicator=None): 650 self.point = point 651 self.indicator = indicator or self.PRINCIPAL 652 653 def __hash__(self): 654 return hash((self.point, self.indicator)) 655 656 def __cmp__(self, other): 657 if isinstance(other, Point): 658 return cmp((self.point, self.indicator), (other.point, other.indicator)) 659 elif isinstance(other, datetime): 660 return cmp(self.point, other) 661 else: 662 return 1 663 664 def __eq__(self, other): 665 return self.__cmp__(other) == 0 666 667 def __ne__(self, other): 668 return not self == other 669 670 def __lt__(self, other): 671 return self.__cmp__(other) < 0 672 673 def __le__(self, other): 674 return self.__cmp__(other) <= 0 675 676 def __gt__(self, other): 677 return not self <= other 678 679 def __ge__(self, other): 680 return not self < other 681 682 def __repr__(self): 683 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 684 685 def get_slots(scale): 686 687 """ 688 Return an ordered list of time slots from the given 'scale'. 689 690 Each slot is a tuple containing details of a point in time for the start of 691 the slot, together with a list of parallel event periods. 692 693 Each point in time is described as a Point representing the actual point in 694 time together with an indicator of the nature of the point in time (as a 695 principal point in a time scale or as a repeated point used to terminate 696 events occurring for an instant in time). 697 """ 698 699 slots = [] 700 active = [] 701 702 points = scale.items() 703 points.sort() 704 705 for point, (starting, ending) in points: 706 ending = set(ending) 707 instants = ending.intersection(starting) 708 709 # Discard all active events ending at or before this start time. 710 # Free up the position in the active list. 711 712 for t in ending.difference(instants): 713 i = active.index(t) 714 active[i] = None 715 716 # For each event starting at the current point, fill any newly-vacated 717 # position or add to the end of the active list. 718 719 for t in starting: 720 try: 721 i = active.index(None) 722 active[i] = t 723 except ValueError: 724 active.append(t) 725 726 # Discard vacant positions from the end of the active list. 727 728 while active and active[-1] is None: 729 active.pop() 730 731 # Add an entry for the time point before "instants". 732 733 slots.append((Point(point), active[:])) 734 735 # Discard events ending at the same time as they began. 736 737 if instants: 738 for t in instants: 739 i = active.index(t) 740 active[i] = None 741 742 # Discard vacant positions from the end of the active list. 743 744 while active and active[-1] is None: 745 active.pop() 746 747 # Add another entry for the time point after "instants". 748 749 slots.append((Point(point, Point.REPEATED), active[:])) 750 751 return slots 752 753 def add_day_start_points(slots, tzid): 754 755 """ 756 Introduce into the 'slots' any day start points required by multi-day 757 periods. The 'tzid' is required to make sure that appropriate time zones 758 are chosen and not necessarily those provided by the existing time points. 759 """ 760 761 new_slots = [] 762 current_date = None 763 previously_active = [] 764 765 for point, active in slots: 766 start_of_day = get_start_of_day(point.point, tzid) 767 this_date = point.point.date() 768 769 # For each new day, add a slot for the start of the day where periods 770 # are active and where no such slot already exists. 771 772 if this_date != current_date: 773 774 # Fill in days where events remain active. 775 776 if current_date: 777 current_date += timedelta(1) 778 while current_date < this_date: 779 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 780 current_date += timedelta(1) 781 else: 782 current_date = this_date 783 784 # Add any continuing periods. 785 786 if point.point != start_of_day: 787 new_slots.append((Point(start_of_day), previously_active)) 788 789 # Add the currently active periods at this point in time. 790 791 previously_active = active 792 793 for t in new_slots: 794 insort_left(slots, t) 795 796 def remove_end_slot(slots, view_period): 797 798 """ 799 Remove from 'slots' any slot situated at the end of the given 'view_period'. 800 """ 801 802 end = view_period.get_end_point() 803 if not end or not slots: 804 return 805 i = bisect_left(slots, (Point(end), None)) 806 if i < len(slots): 807 del slots[i:] 808 809 def add_slots(slots, points): 810 811 """ 812 Introduce into the 'slots' entries for those in 'points' that are not 813 already present, propagating active periods from time points preceding 814 those added. 815 """ 816 817 new_slots = [] 818 819 for point in points: 820 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 821 if i < len(slots) and slots[i][0] == point: 822 continue 823 824 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 825 826 for t in new_slots: 827 insort_left(slots, t) 828 829 def partition_by_day(slots): 830 831 """ 832 Return a mapping from dates to time points provided by 'slots'. 833 """ 834 835 d = {} 836 837 for point, value in slots: 838 day = point.point.date() 839 if not d.has_key(day): 840 d[day] = [] 841 d[day].append((point, value)) 842 843 return d 844 845 def add_empty_days(days, tzid, start=None, end=None): 846 847 """ 848 Add empty days to 'days' between busy days, and optionally from the given 849 'start' day and until the given 'end' day. 850 """ 851 852 last_day = start - timedelta(1) 853 all_days = days.keys() 854 all_days.sort() 855 856 for day in all_days: 857 if last_day: 858 empty_day = last_day + timedelta(1) 859 while empty_day < day: 860 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 861 empty_day += timedelta(1) 862 last_day = day 863 864 if end: 865 empty_day = last_day + timedelta(1) 866 while empty_day < end: 867 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 868 empty_day += timedelta(1) 869 870 def get_spans(slots): 871 872 "Inspect the given 'slots', returning a mapping of period keys to spans." 873 874 points = [point for point, active in slots] 875 spans = {} 876 877 for _point, active in slots: 878 for p in active: 879 if p: 880 key = p.get_key() 881 start_slot = bisect_left(points, p.get_start()) 882 end_slot = bisect_left(points, p.get_end()) 883 spans[key] = end_slot - start_slot 884 885 return spans 886 887 # vim: tabstop=4 expandtab shiftwidth=4