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 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 # Value correction methods. 310 311 def with_duration(self, duration): 312 313 """ 314 Return a version of this period with the same start point but with the 315 given 'duration'. 316 """ 317 318 return self.make_corrected(self.get_start(), self.get_start() + duration) 319 320 def check_permitted(self, permitted_values): 321 322 "Check the period against the given 'permitted_values'." 323 324 start = self.get_start() 325 end = self.get_end() 326 start_errors = check_permitted_values(start, permitted_values) 327 end_errors = check_permitted_values(end, permitted_values) 328 329 if not (start_errors or end_errors): 330 return None 331 332 return start_errors, end_errors 333 334 def get_corrected(self, permitted_values): 335 336 "Return a corrected version of this period." 337 338 errors = self.check_permitted(permitted_values) 339 340 if not errors: 341 return self 342 343 start_errors, end_errors = errors 344 345 start = self.get_start() 346 end = self.get_end() 347 348 if start_errors: 349 start = correct_datetime(start, permitted_values) 350 if end_errors: 351 end = correct_datetime(end, permitted_values) 352 353 return self.make_corrected(start, end) 354 355 def make_corrected(self, start, end): 356 return self.__class__(start, end, self.tzid, self.origin) 357 358 class RecurringPeriod(Period): 359 360 """ 361 A period with iCalendar metadata attributes and origin information from an 362 object. 363 """ 364 365 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 366 Period.__init__(self, start, end, tzid, origin) 367 self.start_attr = start_attr 368 self.end_attr = end_attr 369 370 def get_start_attr(self): 371 return self.start_attr 372 373 def get_end_attr(self): 374 return self.end_attr 375 376 def as_tuple(self): 377 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 378 379 def __repr__(self): 380 return "RecurringPeriod%r" % (self.as_tuple(),) 381 382 def make_corrected(self, start, end): 383 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 384 385 def make_rule_period(start, duration, attr, tzid): 386 387 """ 388 Make a period for the rule period starting at 'start' with the given 389 'duration' employing the given datetime 'attr' and 'tzid'. 390 """ 391 392 # Determine the resolution of the period. 393 394 create = len(start) == 3 and date or datetime 395 start = to_timezone(create(*start), tzid) 396 end = start + duration 397 398 # Create the period with accompanying metadata based on the main 399 # period and event details. 400 401 return RecurringPeriod(start, end, tzid, "RRULE", attr) 402 403 class RulePeriodCollection: 404 405 "A collection of rule periods." 406 407 def __init__(self, rrule, main_period, tzid, end, inclusive=False): 408 409 """ 410 Initialise a period collection for the given 'rrule', employing the 411 'main_period' and 'tzid'. 412 413 The specified 'end' datetime indicates the end of the window for which 414 periods shall be computed. 415 416 If 'inclusive' is set to a true value, any period occurring at the 'end' 417 will be included. 418 """ 419 420 self.rrule = rrule 421 self.main_period = main_period 422 self.tzid = tzid 423 424 parameters = rrule and get_parameters(rrule) 425 until = parameters.get("UNTIL") 426 427 # Any UNTIL qualifier changes the nature of the end of the collection. 428 429 if until: 430 attr = main_period.get_start_attr() 431 until_dt = to_timezone(get_datetime(until, attr), tzid) 432 self.end = end and min(until_dt, end) or until_dt 433 self.inclusive = True 434 else: 435 self.end = end 436 self.inclusive = inclusive 437 438 def __iter__(self): 439 440 """ 441 Obtain period instances, starting from the main period. Since counting 442 must start from the first period, filtering from a start date must be 443 done after the instances have been obtained. 444 """ 445 446 start = self.main_period.get_start() 447 selector = get_rule(start, self.rrule) 448 449 return RulePeriodIterator(self.main_period, self.tzid, 450 selector.select(start, self.end, self.inclusive)) 451 452 class RulePeriodIterator: 453 454 "An iterator over rule periods." 455 456 def __init__(self, main_period, tzid, iterator): 457 self.attr = main_period.get_start_attr() 458 self.duration = main_period.get_duration() 459 self.tzid = tzid 460 self.iterator = iterator 461 462 def next(self): 463 recurrence_start = self.iterator.next() 464 return make_rule_period(recurrence_start, self.duration, self.attr, self.tzid) 465 466 class MergingIterator: 467 468 "An iterator merging ordered collections." 469 470 def __init__(self, iterators): 471 472 "Initialise an iterator merging 'iterators'." 473 474 self.current = [] 475 476 # Populate an ordered collection of (value, iterator) pairs by obtaining 477 # the first value from each iterator. 478 479 for iterator in iterators: 480 t = self.get_next(iterator) 481 if t: 482 self.current.append(t) 483 484 self.current.sort() 485 486 def __iter__(self): 487 return self 488 489 def get_next(self, iterator): 490 491 """ 492 Return a (value, iterator) pair for 'iterator' or None if the iterator 493 has been exhausted. 494 """ 495 496 try: 497 return (iterator.next(), iterator) 498 except StopIteration: 499 return None 500 501 def next(self): 502 503 """ 504 Return the next value in an ordered sequence, choosing it from one of 505 the available iterators. 506 """ 507 508 if not self.current: 509 raise StopIteration 510 511 # Obtain the current value and remove the (value, iterator) pair, 512 # pending insertion of a new pair for the iterator. 513 514 current, iterator = self.current[0] 515 del self.current[0] 516 517 # Get the next value, if any and insert the value and iterator into the 518 # ordered collection. 519 520 t = self.get_next(iterator) 521 if t: 522 insort_left(self.current, t) 523 524 return current 525 526 def get_overlapping(first, second): 527 528 """ 529 Return the entries in the sorted 'first' collection that are overlapping 530 with the given sorted 'second' collection. 531 """ 532 533 if not first or not second: 534 return [] 535 536 # Examine each period in the second collection, attempting to match periods 537 # in the first collection. 538 539 overlapping = set() 540 541 for p2 in second: 542 last_point = p2.get_end_point() 543 544 # Examine the first collection up to the point where no matches will 545 # occur. 546 547 for p1 in first: 548 if p1.get_start_point() > last_point: 549 break 550 elif p1.overlaps(p2): 551 overlapping.add(p1) 552 553 overlapping = list(overlapping) 554 overlapping.sort() 555 return overlapping 556 557 def get_overlapping_members(periods): 558 559 "Return members of the 'periods' collection that overlap with others." 560 561 if not periods: 562 return [] 563 564 l = periods[:] 565 l.sort() 566 567 overlapping = [] 568 569 last = l[0] 570 last_added = None 571 572 for p in l[1:]: 573 if p.get_start_point() < last.get_end_point(): 574 if last_added != last: 575 overlapping.append(last) 576 overlapping.append(p) 577 last_added = p 578 last = p 579 580 return overlapping 581 582 # Period layout. 583 584 def get_scale(periods, tzid, view_period=None): 585 586 """ 587 Return a time scale from the given list of 'periods'. 588 589 The given 'tzid' is used to make sure that the times are defined according 590 to the chosen time zone. 591 592 An optional 'view_period' is used to constrain the scale to the given 593 period. 594 595 The returned scale is a mapping from time to (starting, ending) tuples, 596 where starting and ending are collections of periods. 597 """ 598 599 scale = {} 600 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 601 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 602 603 for p in periods: 604 605 # Add a point and this event to the starting list. 606 607 start = to_timezone(p.get_start(), tzid) 608 start = view_start and max(start, view_start) or start 609 if not scale.has_key(start): 610 scale[start] = [], [] 611 scale[start][0].append(p) 612 613 # Add a point and this event to the ending list. 614 615 end = to_timezone(p.get_end(), tzid) 616 end = view_end and min(end, view_end) or end 617 if not scale.has_key(end): 618 scale[end] = [], [] 619 scale[end][1].append(p) 620 621 return scale 622 623 class Point: 624 625 "A qualified point in time." 626 627 PRINCIPAL, REPEATED = 0, 1 628 629 def __init__(self, point, indicator=None): 630 self.point = point 631 self.indicator = indicator or self.PRINCIPAL 632 633 def __hash__(self): 634 return hash((self.point, self.indicator)) 635 636 def __cmp__(self, other): 637 if isinstance(other, Point): 638 return cmp((self.point, self.indicator), (other.point, other.indicator)) 639 elif isinstance(other, datetime): 640 return cmp(self.point, other) 641 else: 642 return 1 643 644 def __eq__(self, other): 645 return self.__cmp__(other) == 0 646 647 def __ne__(self, other): 648 return not self == other 649 650 def __lt__(self, other): 651 return self.__cmp__(other) < 0 652 653 def __le__(self, other): 654 return self.__cmp__(other) <= 0 655 656 def __gt__(self, other): 657 return not self <= other 658 659 def __ge__(self, other): 660 return not self < other 661 662 def __repr__(self): 663 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 664 665 def get_slots(scale): 666 667 """ 668 Return an ordered list of time slots from the given 'scale'. 669 670 Each slot is a tuple containing details of a point in time for the start of 671 the slot, together with a list of parallel event periods. 672 673 Each point in time is described as a Point representing the actual point in 674 time together with an indicator of the nature of the point in time (as a 675 principal point in a time scale or as a repeated point used to terminate 676 events occurring for an instant in time). 677 """ 678 679 slots = [] 680 active = [] 681 682 points = scale.items() 683 points.sort() 684 685 for point, (starting, ending) in points: 686 ending = set(ending) 687 instants = ending.intersection(starting) 688 689 # Discard all active events ending at or before this start time. 690 # Free up the position in the active list. 691 692 for t in ending.difference(instants): 693 i = active.index(t) 694 active[i] = None 695 696 # For each event starting at the current point, fill any newly-vacated 697 # position or add to the end of the active list. 698 699 for t in starting: 700 try: 701 i = active.index(None) 702 active[i] = t 703 except ValueError: 704 active.append(t) 705 706 # Discard vacant positions from the end of the active list. 707 708 while active and active[-1] is None: 709 active.pop() 710 711 # Add an entry for the time point before "instants". 712 713 slots.append((Point(point), active[:])) 714 715 # Discard events ending at the same time as they began. 716 717 if instants: 718 for t in instants: 719 i = active.index(t) 720 active[i] = None 721 722 # Discard vacant positions from the end of the active list. 723 724 while active and active[-1] is None: 725 active.pop() 726 727 # Add another entry for the time point after "instants". 728 729 slots.append((Point(point, Point.REPEATED), active[:])) 730 731 return slots 732 733 def add_day_start_points(slots, tzid): 734 735 """ 736 Introduce into the 'slots' any day start points required by multi-day 737 periods. The 'tzid' is required to make sure that appropriate time zones 738 are chosen and not necessarily those provided by the existing time points. 739 """ 740 741 new_slots = [] 742 current_date = None 743 previously_active = [] 744 745 for point, active in slots: 746 start_of_day = get_start_of_day(point.point, tzid) 747 this_date = point.point.date() 748 749 # For each new day, add a slot for the start of the day where periods 750 # are active and where no such slot already exists. 751 752 if this_date != current_date: 753 754 # Fill in days where events remain active. 755 756 if current_date: 757 current_date += timedelta(1) 758 while current_date < this_date: 759 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 760 current_date += timedelta(1) 761 else: 762 current_date = this_date 763 764 # Add any continuing periods. 765 766 if point.point != start_of_day: 767 new_slots.append((Point(start_of_day), previously_active)) 768 769 # Add the currently active periods at this point in time. 770 771 previously_active = active 772 773 for t in new_slots: 774 insort_left(slots, t) 775 776 def remove_end_slot(slots, view_period): 777 778 """ 779 Remove from 'slots' any slot situated at the end of the given 'view_period'. 780 """ 781 782 end = view_period.get_end_point() 783 if not end or not slots: 784 return 785 i = bisect_left(slots, (Point(end), None)) 786 if i < len(slots): 787 del slots[i:] 788 789 def add_slots(slots, points): 790 791 """ 792 Introduce into the 'slots' entries for those in 'points' that are not 793 already present, propagating active periods from time points preceding 794 those added. 795 """ 796 797 new_slots = [] 798 799 for point in points: 800 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 801 if i < len(slots) and slots[i][0] == point: 802 continue 803 804 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 805 806 for t in new_slots: 807 insort_left(slots, t) 808 809 def partition_by_day(slots): 810 811 """ 812 Return a mapping from dates to time points provided by 'slots'. 813 """ 814 815 d = {} 816 817 for point, value in slots: 818 day = point.point.date() 819 if not d.has_key(day): 820 d[day] = [] 821 d[day].append((point, value)) 822 823 return d 824 825 def add_empty_days(days, tzid, start=None, end=None): 826 827 """ 828 Add empty days to 'days' between busy days, and optionally from the given 829 'start' day and until the given 'end' day. 830 """ 831 832 last_day = start - timedelta(1) 833 all_days = days.keys() 834 all_days.sort() 835 836 for day in all_days: 837 if last_day: 838 empty_day = last_day + timedelta(1) 839 while empty_day < day: 840 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 841 empty_day += timedelta(1) 842 last_day = day 843 844 if end: 845 empty_day = last_day + timedelta(1) 846 while empty_day < end: 847 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 848 empty_day += timedelta(1) 849 850 def get_spans(slots): 851 852 "Inspect the given 'slots', returning a mapping of period keys to spans." 853 854 points = [point for point, active in slots] 855 spans = {} 856 857 for _point, active in slots: 858 for p in active: 859 if p: 860 key = p.get_key() 861 start_slot = bisect_left(points, p.get_start()) 862 end_slot = bisect_left(points, p.get_end()) 863 spans[key] = end_slot - start_slot 864 865 return spans 866 867 # vim: tabstop=4 expandtab shiftwidth=4