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