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 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 # Value correction methods. 309 310 def with_duration(self, duration): 311 312 """ 313 Return a version of this period with the same start point but with the 314 given 'duration'. 315 """ 316 317 return self.make_corrected(self.get_start(), self.get_start() + duration) 318 319 def check_permitted(self, permitted_values): 320 321 "Check the period against the given 'permitted_values'." 322 323 start = self.get_start() 324 end = self.get_end() 325 start_errors = check_permitted_values(start, permitted_values) 326 end_errors = check_permitted_values(end, permitted_values) 327 328 if not (start_errors or end_errors): 329 return None 330 331 return start_errors, end_errors 332 333 def get_corrected(self, permitted_values): 334 335 "Return a corrected version of this period." 336 337 errors = self.check_permitted(permitted_values) 338 339 if not errors: 340 return self 341 342 start_errors, end_errors = errors 343 344 start = self.get_start() 345 end = self.get_end() 346 347 if start_errors: 348 start = correct_datetime(start, permitted_values) 349 if end_errors: 350 end = correct_datetime(end, permitted_values) 351 352 return self.make_corrected(start, end) 353 354 def make_corrected(self, start, end): 355 return self.__class__(start, end, self.tzid, self.origin) 356 357 class RecurringPeriod(Period): 358 359 """ 360 A period with iCalendar metadata attributes and origin information from an 361 object. 362 """ 363 364 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 365 Period.__init__(self, start, end, tzid, origin) 366 self.start_attr = start_attr 367 self.end_attr = end_attr 368 369 def get_start_attr(self): 370 return self.start_attr 371 372 def get_end_attr(self): 373 return self.end_attr 374 375 def as_tuple(self): 376 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 377 378 def __repr__(self): 379 return "RecurringPeriod%r" % (self.as_tuple(),) 380 381 def make_corrected(self, start, end): 382 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 383 384 def get_overlapping(first, second): 385 386 """ 387 Return the entries in the sorted 'first' collection that are overlapping 388 with the given sorted 'second' collection. 389 """ 390 391 if not first or not second: 392 return [] 393 394 # Examine each period in the second collection, attempting to match periods 395 # in the first collection. 396 397 overlapping = set() 398 399 for p2 in second: 400 last_point = p2.get_end_point() 401 402 # Examine the first collection up to the point where no matches will 403 # occur. 404 405 for p1 in first: 406 if p1.get_start_point() > last_point: 407 break 408 elif p1.overlaps(p2): 409 overlapping.add(p1) 410 411 overlapping = list(overlapping) 412 overlapping.sort() 413 return overlapping 414 415 def get_overlapping_members(periods): 416 417 "Return members of the 'periods' collection that overlap with others." 418 419 if not periods: 420 return [] 421 422 l = periods[:] 423 l.sort() 424 425 overlapping = [] 426 427 last = l[0] 428 last_added = None 429 430 for p in l[1:]: 431 if p.get_start_point() < last.get_end_point(): 432 if last_added != last: 433 overlapping.append(last) 434 overlapping.append(p) 435 last_added = p 436 last = p 437 438 return overlapping 439 440 # Period layout. 441 442 def get_scale(periods, tzid, view_period=None): 443 444 """ 445 Return a time scale from the given list of 'periods'. 446 447 The given 'tzid' is used to make sure that the times are defined according 448 to the chosen time zone. 449 450 An optional 'view_period' is used to constrain the scale to the given 451 period. 452 453 The returned scale is a mapping from time to (starting, ending) tuples, 454 where starting and ending are collections of periods. 455 """ 456 457 scale = {} 458 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 459 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 460 461 for p in periods: 462 463 # Add a point and this event to the starting list. 464 465 start = to_timezone(p.get_start(), tzid) 466 start = view_start and max(start, view_start) or start 467 if not scale.has_key(start): 468 scale[start] = [], [] 469 scale[start][0].append(p) 470 471 # Add a point and this event to the ending list. 472 473 end = to_timezone(p.get_end(), tzid) 474 end = view_end and min(end, view_end) or end 475 if not scale.has_key(end): 476 scale[end] = [], [] 477 scale[end][1].append(p) 478 479 return scale 480 481 class Point: 482 483 "A qualified point in time." 484 485 PRINCIPAL, REPEATED = 0, 1 486 487 def __init__(self, point, indicator=None): 488 self.point = point 489 self.indicator = indicator or self.PRINCIPAL 490 491 def __hash__(self): 492 return hash((self.point, self.indicator)) 493 494 def __cmp__(self, other): 495 if isinstance(other, Point): 496 return cmp((self.point, self.indicator), (other.point, other.indicator)) 497 elif isinstance(other, datetime): 498 return cmp(self.point, other) 499 else: 500 return 1 501 502 def __eq__(self, other): 503 return self.__cmp__(other) == 0 504 505 def __ne__(self, other): 506 return not self == other 507 508 def __lt__(self, other): 509 return self.__cmp__(other) < 0 510 511 def __le__(self, other): 512 return self.__cmp__(other) <= 0 513 514 def __gt__(self, other): 515 return not self <= other 516 517 def __ge__(self, other): 518 return not self < other 519 520 def __repr__(self): 521 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 522 523 def get_slots(scale): 524 525 """ 526 Return an ordered list of time slots from the given 'scale'. 527 528 Each slot is a tuple containing details of a point in time for the start of 529 the slot, together with a list of parallel event periods. 530 531 Each point in time is described as a Point representing the actual point in 532 time together with an indicator of the nature of the point in time (as a 533 principal point in a time scale or as a repeated point used to terminate 534 events occurring for an instant in time). 535 """ 536 537 slots = [] 538 active = [] 539 540 points = scale.items() 541 points.sort() 542 543 for point, (starting, ending) in points: 544 ending = set(ending) 545 instants = ending.intersection(starting) 546 547 # Discard all active events ending at or before this start time. 548 # Free up the position in the active list. 549 550 for t in ending.difference(instants): 551 i = active.index(t) 552 active[i] = None 553 554 # For each event starting at the current point, fill any newly-vacated 555 # position or add to the end of the active list. 556 557 for t in starting: 558 try: 559 i = active.index(None) 560 active[i] = t 561 except ValueError: 562 active.append(t) 563 564 # Discard vacant positions from the end of the active list. 565 566 while active and active[-1] is None: 567 active.pop() 568 569 # Add an entry for the time point before "instants". 570 571 slots.append((Point(point), active[:])) 572 573 # Discard events ending at the same time as they began. 574 575 if instants: 576 for t in instants: 577 i = active.index(t) 578 active[i] = None 579 580 # Discard vacant positions from the end of the active list. 581 582 while active and active[-1] is None: 583 active.pop() 584 585 # Add another entry for the time point after "instants". 586 587 slots.append((Point(point, Point.REPEATED), active[:])) 588 589 return slots 590 591 def add_day_start_points(slots, tzid): 592 593 """ 594 Introduce into the 'slots' any day start points required by multi-day 595 periods. The 'tzid' is required to make sure that appropriate time zones 596 are chosen and not necessarily those provided by the existing time points. 597 """ 598 599 new_slots = [] 600 current_date = None 601 previously_active = [] 602 603 for point, active in slots: 604 start_of_day = get_start_of_day(point.point, tzid) 605 this_date = point.point.date() 606 607 # For each new day, add a slot for the start of the day where periods 608 # are active and where no such slot already exists. 609 610 if this_date != current_date: 611 612 # Fill in days where events remain active. 613 614 if current_date: 615 current_date += timedelta(1) 616 while current_date < this_date: 617 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 618 current_date += timedelta(1) 619 else: 620 current_date = this_date 621 622 # Add any continuing periods. 623 624 if point.point != start_of_day: 625 new_slots.append((Point(start_of_day), previously_active)) 626 627 # Add the currently active periods at this point in time. 628 629 previously_active = active 630 631 for t in new_slots: 632 insort_left(slots, t) 633 634 def remove_end_slot(slots, view_period): 635 636 """ 637 Remove from 'slots' any slot situated at the end of the given 'view_period'. 638 """ 639 640 end = view_period.get_end_point() 641 if not end or not slots: 642 return 643 i = bisect_left(slots, (Point(end), None)) 644 if i < len(slots): 645 del slots[i:] 646 647 def add_slots(slots, points): 648 649 """ 650 Introduce into the 'slots' entries for those in 'points' that are not 651 already present, propagating active periods from time points preceding 652 those added. 653 """ 654 655 new_slots = [] 656 657 for point in points: 658 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 659 if i < len(slots) and slots[i][0] == point: 660 continue 661 662 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 663 664 for t in new_slots: 665 insort_left(slots, t) 666 667 def partition_by_day(slots): 668 669 """ 670 Return a mapping from dates to time points provided by 'slots'. 671 """ 672 673 d = {} 674 675 for point, value in slots: 676 day = point.point.date() 677 if not d.has_key(day): 678 d[day] = [] 679 d[day].append((point, value)) 680 681 return d 682 683 def add_empty_days(days, tzid, start=None, end=None): 684 685 """ 686 Add empty days to 'days' between busy days, and optionally from the given 687 'start' day and until the given 'end' day. 688 """ 689 690 last_day = start - timedelta(1) 691 all_days = days.keys() 692 all_days.sort() 693 694 for day in all_days: 695 if last_day: 696 empty_day = last_day + timedelta(1) 697 while empty_day < day: 698 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 699 empty_day += timedelta(1) 700 last_day = day 701 702 if end: 703 empty_day = last_day + timedelta(1) 704 while empty_day < end: 705 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 706 empty_day += timedelta(1) 707 708 def get_spans(slots): 709 710 "Inspect the given 'slots', returning a mapping of period keys to spans." 711 712 points = [point for point, active in slots] 713 spans = {} 714 715 for _point, active in slots: 716 for p in active: 717 if p: 718 key = p.get_key() 719 start_slot = bisect_left(points, p.get_start()) 720 end_slot = bisect_left(points, p.get_end()) 721 spans[key] = end_slot - start_slot 722 723 return spans 724 725 # vim: tabstop=4 expandtab shiftwidth=4