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