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 class Comparable: 37 38 "A date/datetime wrapper that allows comparisons with other types." 39 40 def __init__(self, dt): 41 self.dt = dt 42 43 def __cmp__(self, other): 44 dt = None 45 odt = None 46 47 # Find any dates/datetimes. 48 49 if isinstance(self.dt, date): 50 dt = self.dt 51 if isinstance(other, date): 52 odt = other 53 elif isinstance(other, Comparable): 54 if isinstance(other.dt, date): 55 odt = other.dt 56 else: 57 other = other.dt 58 59 if dt and odt: 60 return cmp(dt, odt) 61 elif dt: 62 return other.__rcmp__(dt) 63 elif odt: 64 return self.dt.__cmp__(odt) 65 else: 66 return self.dt.__cmp__(other) 67 68 class PointInTime: 69 70 "A base class for special values." 71 72 pass 73 74 class StartOfTime(PointInTime): 75 76 "A special value that compares earlier than other values." 77 78 def __cmp__(self, other): 79 if isinstance(other, StartOfTime): 80 return 0 81 else: 82 return -1 83 84 def __rcmp__(self, other): 85 return -self.__cmp__(other) 86 87 def __nonzero__(self): 88 return False 89 90 def __hash__(self): 91 return 0 92 93 class EndOfTime(PointInTime): 94 95 "A special value that compares later than other values." 96 97 def __cmp__(self, other): 98 if isinstance(other, EndOfTime): 99 return 0 100 else: 101 return 1 102 103 def __rcmp__(self, other): 104 return -self.__cmp__(other) 105 106 def __nonzero__(self): 107 return False 108 109 def __hash__(self): 110 return 0 111 112 class Endless: 113 114 "A special value indicating an endless period." 115 116 def __cmp__(self, other): 117 if isinstance(other, Endless): 118 return 0 119 else: 120 return 1 121 122 def __rcmp__(self, other): 123 return -self.__cmp__(other) 124 125 def __nonzero__(self): 126 return True 127 128 class PeriodBase: 129 130 "A basic period abstraction." 131 132 def __init__(self, start, end): 133 134 """ 135 Define a period according to 'start' and 'end' which may be special 136 start/end of time values or iCalendar-format datetime strings. 137 """ 138 139 if isinstance(start, (date, PointInTime)): 140 self.start = start 141 else: 142 self.start = get_datetime(start) or StartOfTime() 143 144 if isinstance(end, (date, PointInTime)): 145 self.end = end 146 else: 147 self.end = get_datetime(end) or EndOfTime() 148 149 def as_tuple(self): 150 return self.start, self.end 151 152 def __hash__(self): 153 return hash((self.get_start(), self.get_end())) 154 155 def __cmp__(self, other): 156 157 "Return a comparison result against 'other' using points in time." 158 159 if isinstance(other, PeriodBase): 160 return cmp( 161 (Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(self.get_end_point(), EndOfTime()))), 162 (Comparable(ifnone(other.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 163 ) 164 else: 165 return 1 166 167 def overlaps(self, other): 168 return Comparable(ifnone(self.get_end_point(), EndOfTime())) > Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 169 Comparable(ifnone(self.get_start_point(), StartOfTime())) < Comparable(ifnone(other.get_end_point(), EndOfTime())) 170 171 def within(self, other): 172 return Comparable(ifnone(self.get_start_point(), StartOfTime())) >= Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 173 Comparable(ifnone(self.get_end_point(), EndOfTime())) <= Comparable(ifnone(other.get_end_point(), EndOfTime())) 174 175 def common(self, other): 176 start = max(Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_start_point(), StartOfTime()))) 177 end = min(Comparable(ifnone(self.get_end_point(), EndOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 178 if start <= end: 179 return self.make_corrected(start.dt, end.dt) 180 else: 181 return None 182 183 def get_key(self): 184 return self.get_start(), self.get_end() 185 186 # Datetime and metadata methods. 187 188 def get_start(self): 189 return self.start 190 191 def get_end(self): 192 return self.end 193 194 def get_start_attr(self): 195 return get_datetime_attributes(self.start, self.tzid) 196 197 def get_end_attr(self): 198 return get_datetime_attributes(self.end, self.tzid) 199 200 def get_start_item(self): 201 return self.get_start(), self.get_start_attr() 202 203 def get_end_item(self): 204 return self.get_end(), self.get_end_attr() 205 206 def get_start_point(self): 207 return self.start 208 209 def get_end_point(self): 210 return self.end 211 212 def get_duration(self): 213 start = self.get_start_point() 214 end = self.get_end_point() 215 if start and end: 216 return end - start 217 else: 218 return Endless() 219 220 class Period(PeriodBase): 221 222 "A simple period abstraction." 223 224 def __init__(self, start, end, tzid=None, origin=None): 225 226 """ 227 Initialise a period with the given 'start' and 'end', having a 228 contextual 'tzid', if specified, and an indicated 'origin'. 229 230 All metadata from the start and end points are derived from the supplied 231 dates/datetimes. 232 """ 233 234 PeriodBase.__init__(self, start, end) 235 self.tzid = tzid 236 self.origin = origin 237 238 def as_tuple(self): 239 return self.start, self.end, self.tzid, self.origin 240 241 def __repr__(self): 242 return "Period%r" % (self.as_tuple(),) 243 244 # Datetime and metadata methods. 245 246 def get_tzid(self): 247 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 248 249 def get_start_point(self): 250 start = self.get_start() 251 if isinstance(start, PointInTime): return start 252 else: return to_utc_datetime(start, self.get_tzid()) 253 254 def get_end_point(self): 255 end = self.get_end() 256 if isinstance(end, PointInTime): return end 257 else: return to_utc_datetime(end, self.get_tzid()) 258 259 # Period and event recurrence logic. 260 261 def is_replaced(self, recurrenceids): 262 263 """ 264 Return whether this period refers to one of the 'recurrenceids'. 265 The 'recurrenceids' should be normalised to UTC datetimes according to 266 time zone information provided by their objects or be floating dates or 267 datetimes requiring conversion using contextual time zone information. 268 """ 269 270 for recurrenceid in recurrenceids: 271 if self.is_affected(recurrenceid): 272 return recurrenceid 273 return None 274 275 def is_affected(self, recurrenceid): 276 277 """ 278 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 279 should be normalised to UTC datetimes according to time zone information 280 provided by their objects. Otherwise, this period's contextual time zone 281 information is used to convert any date or floating datetime 282 representation to a point in time. 283 """ 284 285 if not recurrenceid: 286 return None 287 d = get_recurrence_start(recurrenceid) 288 dt = get_recurrence_start_point(recurrenceid, self.tzid) 289 290 # Compare the start to dates only, using the normalised start datetime 291 # for comparisons with the start point. 292 293 if not isinstance(d, datetime) and self.get_start() == d or self.get_start_point() == dt: 294 return recurrenceid 295 296 return None 297 298 # Value correction methods. 299 300 def with_duration(self, duration): 301 302 """ 303 Return a version of this period with the same start point but with the 304 given 'duration'. 305 """ 306 307 return self.make_corrected(self.get_start(), self.get_start() + duration) 308 309 def check_permitted(self, permitted_values): 310 311 "Check the period against the given 'permitted_values'." 312 313 start = self.get_start() 314 end = self.get_end() 315 start_errors = check_permitted_values(start, permitted_values) 316 end_errors = check_permitted_values(end, permitted_values) 317 318 if not (start_errors or end_errors): 319 return None 320 321 return start_errors, end_errors 322 323 def get_corrected(self, permitted_values): 324 325 "Return a corrected version of this period." 326 327 errors = self.check_permitted(permitted_values) 328 329 if not errors: 330 return self 331 332 start_errors, end_errors = errors 333 334 start = self.get_start() 335 end = self.get_end() 336 337 if start_errors: 338 start = correct_datetime(start, permitted_values) 339 if end_errors: 340 end = correct_datetime(end, permitted_values) 341 342 return self.make_corrected(start, end) 343 344 def make_corrected(self, start, end): 345 return self.__class__(start, end, self.tzid, self.origin) 346 347 class RecurringPeriod(Period): 348 349 """ 350 A period with iCalendar metadata attributes and origin information from an 351 object. 352 """ 353 354 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 355 Period.__init__(self, start, end, tzid, origin) 356 self.start_attr = start_attr 357 self.end_attr = end_attr 358 359 def get_start_attr(self): 360 return self.start_attr 361 362 def get_end_attr(self): 363 return self.end_attr 364 365 def as_tuple(self): 366 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 367 368 def __repr__(self): 369 return "RecurringPeriod%r" % (self.as_tuple(),) 370 371 def make_corrected(self, start, end): 372 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 373 374 def get_overlapping(first, second): 375 376 """ 377 Return the entries in the sorted 'first' collection that are overlapping 378 with the given sorted 'second' collection. 379 """ 380 381 if not first or not second: 382 return [] 383 384 # Examine each period in the second collection, attempting to match periods 385 # in the first collection. 386 387 overlapping = set() 388 389 for p2 in second: 390 last_point = p2.get_end_point() 391 392 # Examine the first collection up to the point where no matches will 393 # occur. 394 395 for p1 in first: 396 if p1.get_start_point() > last_point: 397 break 398 elif p1.overlaps(p2): 399 overlapping.add(p1) 400 401 overlapping = list(overlapping) 402 overlapping.sort() 403 return overlapping 404 405 # Period layout. 406 407 def get_scale(periods, tzid, view_period=None): 408 409 """ 410 Return a time scale from the given list of 'periods'. 411 412 The given 'tzid' is used to make sure that the times are defined according 413 to the chosen time zone. 414 415 An optional 'view_period' is used to constrain the scale to the given 416 period. 417 418 The returned scale is a mapping from time to (starting, ending) tuples, 419 where starting and ending are collections of periods. 420 """ 421 422 scale = {} 423 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 424 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 425 426 for p in periods: 427 428 # Add a point and this event to the starting list. 429 430 start = to_timezone(p.get_start(), tzid) 431 start = view_start and max(start, view_start) or start 432 if not scale.has_key(start): 433 scale[start] = [], [] 434 scale[start][0].append(p) 435 436 # Add a point and this event to the ending list. 437 438 end = to_timezone(p.get_end(), tzid) 439 end = view_end and min(end, view_end) or end 440 if not scale.has_key(end): 441 scale[end] = [], [] 442 scale[end][1].append(p) 443 444 return scale 445 446 class Point: 447 448 "A qualified point in time." 449 450 PRINCIPAL, REPEATED = 0, 1 451 452 def __init__(self, point, indicator=None): 453 self.point = point 454 self.indicator = indicator or self.PRINCIPAL 455 456 def __hash__(self): 457 return hash((self.point, self.indicator)) 458 459 def __cmp__(self, other): 460 if isinstance(other, Point): 461 return cmp((self.point, self.indicator), (other.point, other.indicator)) 462 elif isinstance(other, datetime): 463 return cmp(self.point, other) 464 else: 465 return 1 466 467 def __eq__(self, other): 468 return self.__cmp__(other) == 0 469 470 def __ne__(self, other): 471 return not self == other 472 473 def __lt__(self, other): 474 return self.__cmp__(other) < 0 475 476 def __le__(self, other): 477 return self.__cmp__(other) <= 0 478 479 def __gt__(self, other): 480 return not self <= other 481 482 def __ge__(self, other): 483 return not self < other 484 485 def __repr__(self): 486 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 487 488 def get_slots(scale): 489 490 """ 491 Return an ordered list of time slots from the given 'scale'. 492 493 Each slot is a tuple containing details of a point in time for the start of 494 the slot, together with a list of parallel event periods. 495 496 Each point in time is described as a Point representing the actual point in 497 time together with an indicator of the nature of the point in time (as a 498 principal point in a time scale or as a repeated point used to terminate 499 events occurring for an instant in time). 500 """ 501 502 slots = [] 503 active = [] 504 505 points = scale.items() 506 points.sort() 507 508 for point, (starting, ending) in points: 509 ending = set(ending) 510 instants = ending.intersection(starting) 511 512 # Discard all active events ending at or before this start time. 513 # Free up the position in the active list. 514 515 for t in ending.difference(instants): 516 i = active.index(t) 517 active[i] = None 518 519 # For each event starting at the current point, fill any newly-vacated 520 # position or add to the end of the active list. 521 522 for t in starting: 523 try: 524 i = active.index(None) 525 active[i] = t 526 except ValueError: 527 active.append(t) 528 529 # Discard vacant positions from the end of the active list. 530 531 while active and active[-1] is None: 532 active.pop() 533 534 # Add an entry for the time point before "instants". 535 536 slots.append((Point(point), active[:])) 537 538 # Discard events ending at the same time as they began. 539 540 if instants: 541 for t in instants: 542 i = active.index(t) 543 active[i] = None 544 545 # Discard vacant positions from the end of the active list. 546 547 while active and active[-1] is None: 548 active.pop() 549 550 # Add another entry for the time point after "instants". 551 552 slots.append((Point(point, Point.REPEATED), active[:])) 553 554 return slots 555 556 def add_day_start_points(slots, tzid): 557 558 """ 559 Introduce into the 'slots' any day start points required by multi-day 560 periods. The 'tzid' is required to make sure that appropriate time zones 561 are chosen and not necessarily those provided by the existing time points. 562 """ 563 564 new_slots = [] 565 current_date = None 566 previously_active = [] 567 568 for point, active in slots: 569 start_of_day = get_start_of_day(point.point, tzid) 570 this_date = point.point.date() 571 572 # For each new day, add a slot for the start of the day where periods 573 # are active and where no such slot already exists. 574 575 if this_date != current_date: 576 577 # Fill in days where events remain active. 578 579 if current_date: 580 current_date += timedelta(1) 581 while current_date < this_date: 582 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 583 current_date += timedelta(1) 584 else: 585 current_date = this_date 586 587 # Add any continuing periods. 588 589 if point.point != start_of_day: 590 new_slots.append((Point(start_of_day), previously_active)) 591 592 # Add the currently active periods at this point in time. 593 594 previously_active = active 595 596 for t in new_slots: 597 insort_left(slots, t) 598 599 def remove_end_slot(slots, view_period): 600 601 """ 602 Remove from 'slots' any slot situated at the end of the given 'view_period'. 603 """ 604 605 end = view_period.get_end_point() 606 if not end or not slots: 607 return 608 i = bisect_left(slots, (Point(end), None)) 609 if i < len(slots): 610 del slots[i:] 611 612 def add_slots(slots, points): 613 614 """ 615 Introduce into the 'slots' entries for those in 'points' that are not 616 already present, propagating active periods from time points preceding 617 those added. 618 """ 619 620 new_slots = [] 621 622 for point in points: 623 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 624 if i < len(slots) and slots[i][0] == point: 625 continue 626 627 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 628 629 for t in new_slots: 630 insort_left(slots, t) 631 632 def partition_by_day(slots): 633 634 """ 635 Return a mapping from dates to time points provided by 'slots'. 636 """ 637 638 d = {} 639 640 for point, value in slots: 641 day = point.point.date() 642 if not d.has_key(day): 643 d[day] = [] 644 d[day].append((point, value)) 645 646 return d 647 648 def add_empty_days(days, tzid, start=None, end=None): 649 650 """ 651 Add empty days to 'days' between busy days, and optionally from the given 652 'start' day and until the given 'end' day. 653 """ 654 655 last_day = start - timedelta(1) 656 all_days = days.keys() 657 all_days.sort() 658 659 for day in all_days: 660 if last_day: 661 empty_day = last_day + timedelta(1) 662 while empty_day < day: 663 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 664 empty_day += timedelta(1) 665 last_day = day 666 667 if end: 668 empty_day = last_day + timedelta(1) 669 while empty_day < end: 670 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 671 empty_day += timedelta(1) 672 673 def get_spans(slots): 674 675 "Inspect the given 'slots', returning a mapping of period keys to spans." 676 677 points = [point for point, active in slots] 678 spans = {} 679 680 for _point, active in slots: 681 for p in active: 682 if p: 683 key = p.get_key() 684 start_slot = bisect_left(points, p.get_start()) 685 end_slot = bisect_left(points, p.get_end()) 686 spans[key] = end_slot - start_slot 687 688 return spans 689 690 # vim: tabstop=4 expandtab shiftwidth=4