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 # Period layout. 430 431 def get_scale(periods, tzid, view_period=None): 432 433 """ 434 Return a time scale from the given list of 'periods'. 435 436 The given 'tzid' is used to make sure that the times are defined according 437 to the chosen time zone. 438 439 An optional 'view_period' is used to constrain the scale to the given 440 period. 441 442 The returned scale is a mapping from time to (starting, ending) tuples, 443 where starting and ending are collections of periods. 444 """ 445 446 scale = {} 447 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 448 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 449 450 for p in periods: 451 452 # Add a point and this event to the starting list. 453 454 start = to_timezone(p.get_start(), tzid) 455 start = view_start and max(start, view_start) or start 456 if not scale.has_key(start): 457 scale[start] = [], [] 458 scale[start][0].append(p) 459 460 # Add a point and this event to the ending list. 461 462 end = to_timezone(p.get_end(), tzid) 463 end = view_end and min(end, view_end) or end 464 if not scale.has_key(end): 465 scale[end] = [], [] 466 scale[end][1].append(p) 467 468 return scale 469 470 class Point: 471 472 "A qualified point in time." 473 474 PRINCIPAL, REPEATED = 0, 1 475 476 def __init__(self, point, indicator=None): 477 self.point = point 478 self.indicator = indicator or self.PRINCIPAL 479 480 def __hash__(self): 481 return hash((self.point, self.indicator)) 482 483 def __cmp__(self, other): 484 if isinstance(other, Point): 485 return cmp((self.point, self.indicator), (other.point, other.indicator)) 486 elif isinstance(other, datetime): 487 return cmp(self.point, other) 488 else: 489 return 1 490 491 def __eq__(self, other): 492 return self.__cmp__(other) == 0 493 494 def __ne__(self, other): 495 return not self == other 496 497 def __lt__(self, other): 498 return self.__cmp__(other) < 0 499 500 def __le__(self, other): 501 return self.__cmp__(other) <= 0 502 503 def __gt__(self, other): 504 return not self <= other 505 506 def __ge__(self, other): 507 return not self < other 508 509 def __repr__(self): 510 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 511 512 def get_slots(scale): 513 514 """ 515 Return an ordered list of time slots from the given 'scale'. 516 517 Each slot is a tuple containing details of a point in time for the start of 518 the slot, together with a list of parallel event periods. 519 520 Each point in time is described as a Point representing the actual point in 521 time together with an indicator of the nature of the point in time (as a 522 principal point in a time scale or as a repeated point used to terminate 523 events occurring for an instant in time). 524 """ 525 526 slots = [] 527 active = [] 528 529 points = scale.items() 530 points.sort() 531 532 for point, (starting, ending) in points: 533 ending = set(ending) 534 instants = ending.intersection(starting) 535 536 # Discard all active events ending at or before this start time. 537 # Free up the position in the active list. 538 539 for t in ending.difference(instants): 540 i = active.index(t) 541 active[i] = None 542 543 # For each event starting at the current point, fill any newly-vacated 544 # position or add to the end of the active list. 545 546 for t in starting: 547 try: 548 i = active.index(None) 549 active[i] = t 550 except ValueError: 551 active.append(t) 552 553 # Discard vacant positions from the end of the active list. 554 555 while active and active[-1] is None: 556 active.pop() 557 558 # Add an entry for the time point before "instants". 559 560 slots.append((Point(point), active[:])) 561 562 # Discard events ending at the same time as they began. 563 564 if instants: 565 for t in instants: 566 i = active.index(t) 567 active[i] = None 568 569 # Discard vacant positions from the end of the active list. 570 571 while active and active[-1] is None: 572 active.pop() 573 574 # Add another entry for the time point after "instants". 575 576 slots.append((Point(point, Point.REPEATED), active[:])) 577 578 return slots 579 580 def add_day_start_points(slots, tzid): 581 582 """ 583 Introduce into the 'slots' any day start points required by multi-day 584 periods. The 'tzid' is required to make sure that appropriate time zones 585 are chosen and not necessarily those provided by the existing time points. 586 """ 587 588 new_slots = [] 589 current_date = None 590 previously_active = [] 591 592 for point, active in slots: 593 start_of_day = get_start_of_day(point.point, tzid) 594 this_date = point.point.date() 595 596 # For each new day, add a slot for the start of the day where periods 597 # are active and where no such slot already exists. 598 599 if this_date != current_date: 600 601 # Fill in days where events remain active. 602 603 if current_date: 604 current_date += timedelta(1) 605 while current_date < this_date: 606 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 607 current_date += timedelta(1) 608 else: 609 current_date = this_date 610 611 # Add any continuing periods. 612 613 if point.point != start_of_day: 614 new_slots.append((Point(start_of_day), previously_active)) 615 616 # Add the currently active periods at this point in time. 617 618 previously_active = active 619 620 for t in new_slots: 621 insort_left(slots, t) 622 623 def remove_end_slot(slots, view_period): 624 625 """ 626 Remove from 'slots' any slot situated at the end of the given 'view_period'. 627 """ 628 629 end = view_period.get_end_point() 630 if not end or not slots: 631 return 632 i = bisect_left(slots, (Point(end), None)) 633 if i < len(slots): 634 del slots[i:] 635 636 def add_slots(slots, points): 637 638 """ 639 Introduce into the 'slots' entries for those in 'points' that are not 640 already present, propagating active periods from time points preceding 641 those added. 642 """ 643 644 new_slots = [] 645 646 for point in points: 647 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 648 if i < len(slots) and slots[i][0] == point: 649 continue 650 651 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 652 653 for t in new_slots: 654 insort_left(slots, t) 655 656 def partition_by_day(slots): 657 658 """ 659 Return a mapping from dates to time points provided by 'slots'. 660 """ 661 662 d = {} 663 664 for point, value in slots: 665 day = point.point.date() 666 if not d.has_key(day): 667 d[day] = [] 668 d[day].append((point, value)) 669 670 return d 671 672 def add_empty_days(days, tzid, start=None, end=None): 673 674 """ 675 Add empty days to 'days' between busy days, and optionally from the given 676 'start' day and until the given 'end' day. 677 """ 678 679 last_day = start - timedelta(1) 680 all_days = days.keys() 681 all_days.sort() 682 683 for day in all_days: 684 if last_day: 685 empty_day = last_day + timedelta(1) 686 while empty_day < day: 687 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 688 empty_day += timedelta(1) 689 last_day = day 690 691 if end: 692 empty_day = last_day + timedelta(1) 693 while empty_day < end: 694 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 695 empty_day += timedelta(1) 696 697 def get_spans(slots): 698 699 "Inspect the given 'slots', returning a mapping of period keys to spans." 700 701 points = [point for point, active in slots] 702 spans = {} 703 704 for _point, active in slots: 705 for p in active: 706 if p: 707 key = p.get_key() 708 start_slot = bisect_left(points, p.get_start()) 709 end_slot = bisect_left(points, p.get_end()) 710 spans[key] = end_slot - start_slot 711 712 return spans 713 714 # vim: tabstop=4 expandtab shiftwidth=4