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