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