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