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