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