1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015 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, bisect_right, insort_left 23 from datetime import date, datetime, timedelta 24 from imiptools.dates import format_datetime, get_datetime, \ 25 get_datetime_attributes, \ 26 get_recurrence_start, get_recurrence_start_point, \ 27 get_start_of_day, \ 28 get_tzid, \ 29 to_timezone, to_utc_datetime 30 31 class PeriodBase: 32 33 "A basic period abstraction." 34 35 def as_tuple(self): 36 return self.start, self.end 37 38 def __hash__(self): 39 return hash((self.get_start(), self.get_end())) 40 41 def __cmp__(self, other): 42 43 "Return a comparison result against 'other' using points in time." 44 45 if isinstance(other, PeriodBase): 46 return cmp( 47 (self.get_start_point(), self.get_end_point()), 48 (other.get_start_point(), other.get_end_point()) 49 ) 50 else: 51 return 1 52 53 def get_key(self): 54 return self.get_start(), self.get_end() 55 56 # Datetime and metadata methods. 57 58 def get_start(self): 59 return self.start 60 61 def get_end(self): 62 return self.end 63 64 def get_start_attr(self): 65 return get_datetime_attributes(self.start, self.tzid) 66 67 def get_end_attr(self): 68 return get_datetime_attributes(self.end, self.tzid) 69 70 def get_start_item(self): 71 return self.get_start(), self.get_start_attr() 72 73 def get_end_item(self): 74 return self.get_end(), self.get_end_attr() 75 76 def get_start_point(self): 77 return self.start 78 79 def get_end_point(self): 80 return self.end 81 82 class Period(PeriodBase): 83 84 "A simple period abstraction." 85 86 def __init__(self, start, end, tzid=None, origin=None): 87 88 """ 89 Initialise a period with the given 'start' and 'end', having a 90 contextual 'tzid', if specified, and an indicated 'origin'. 91 92 All metadata from the start and end points are derived from the supplied 93 dates/datetimes. 94 """ 95 96 self.start = isinstance(start, date) and start or get_datetime(start) 97 self.end = isinstance(end, date) and end or get_datetime(end) 98 self.tzid = tzid 99 self.origin = origin 100 101 def as_tuple(self): 102 return self.start, self.end, self.tzid, self.origin 103 104 def __repr__(self): 105 return "Period%r" % (self.as_tuple(),) 106 107 # Datetime and metadata methods. 108 109 def get_tzid(self): 110 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 111 112 def get_start_point(self): 113 return to_utc_datetime(self.get_start(), self.get_tzid()) 114 115 def get_end_point(self): 116 return to_utc_datetime(self.get_end(), self.get_tzid()) 117 118 # Period and event recurrence logic. 119 120 def is_replaced(self, recurrenceids): 121 122 """ 123 Return whether this period refers to one of the 'recurrenceids'. 124 The 'recurrenceids' should be normalised to UTC datetimes according to 125 time zone information provided by their objects or be floating dates or 126 datetimes requiring conversion using contextual time zone information. 127 """ 128 129 for recurrenceid in recurrenceids: 130 if self.is_affected(recurrenceid): 131 return recurrenceid 132 return None 133 134 def is_affected(self, recurrenceid): 135 136 """ 137 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 138 should be normalised to UTC datetimes according to time zone information 139 provided by their objects. Otherwise, this period's contextual time zone 140 information is used to convert any date or floating datetime 141 representation to a point in time. 142 """ 143 144 if not recurrenceid: 145 return None 146 d = get_recurrence_start(recurrenceid) 147 dt = get_recurrence_start_point(recurrenceid, self.tzid) 148 if self.get_start() == d or self.get_start_point() == dt: 149 return recurrenceid 150 return None 151 152 class FreeBusyPeriod(PeriodBase): 153 154 "A free/busy record abstraction." 155 156 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None): 157 158 """ 159 Initialise a free/busy period with the given 'start' and 'end' points, 160 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 161 details. 162 """ 163 164 self.start = isinstance(start, datetime) and start or get_datetime(start) 165 self.end = isinstance(end, datetime) and end or get_datetime(end) 166 self.uid = uid 167 self.transp = transp 168 self.recurrenceid = recurrenceid 169 self.summary = summary 170 self.organiser = organiser 171 172 def as_tuple(self, strings_only=False): 173 174 """ 175 Return the initialisation parameter tuple, converting false value 176 parameters to strings if 'strings_only' is set to a true value. 177 """ 178 179 null = lambda x: (strings_only and [""] or [x])[0] 180 return ( 181 strings_only and format_datetime(self.get_start_point()) or self.start, 182 strings_only and format_datetime(self.get_end_point()) or self.end, 183 self.uid or null(self.uid), 184 self.transp or strings_only and "OPAQUE" or None, 185 self.recurrenceid or null(self.recurrenceid), 186 self.summary or null(self.summary), 187 self.organiser or null(self.organiser) 188 ) 189 190 def __cmp__(self, other): 191 192 """ 193 Compare this object to 'other', employing the uid if the periods 194 involved are the same. 195 """ 196 197 result = PeriodBase.__cmp__(self, other) 198 if result == 0 and isinstance(other, FreeBusyPeriod): 199 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 200 else: 201 return result 202 203 def get_key(self): 204 return self.uid, self.recurrenceid, self.get_start() 205 206 def __repr__(self): 207 return "FreeBusyPeriod%r" % (self.as_tuple(),) 208 209 class RecurringPeriod(Period): 210 211 """ 212 A period with iCalendar metadata attributes and origin information from an 213 object. 214 """ 215 216 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 217 Period.__init__(self, start, end, tzid, origin) 218 self.start_attr = start_attr 219 self.end_attr = end_attr 220 221 def get_start_attr(self): 222 return self.start_attr 223 224 def get_end_attr(self): 225 return self.end_attr 226 227 def as_tuple(self): 228 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 229 230 def __repr__(self): 231 return "RecurringPeriod%r" % (self.as_tuple(),) 232 233 # Time and period management. 234 235 def can_schedule(freebusy, periods, uid, recurrenceid): 236 237 """ 238 Return whether the 'freebusy' list can accommodate the given 'periods' 239 employing the specified 'uid' and 'recurrenceid'. 240 """ 241 242 for conflict in have_conflict(freebusy, periods, True): 243 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 244 return False 245 246 return True 247 248 def have_conflict(freebusy, periods, get_conflicts=False): 249 250 """ 251 Return whether any period in 'freebusy' overlaps with the given 'periods', 252 returning a collection of such overlapping periods if 'get_conflicts' is 253 set to a true value. 254 """ 255 256 conflicts = set() 257 for p in periods: 258 overlapping = period_overlaps(freebusy, p, get_conflicts) 259 if overlapping: 260 if get_conflicts: 261 conflicts.update(overlapping) 262 else: 263 return True 264 265 if get_conflicts: 266 return conflicts 267 else: 268 return False 269 270 def insert_period(freebusy, period): 271 272 "Insert into 'freebusy' the given 'period'." 273 274 i = bisect_left(freebusy, period) 275 if i == len(freebusy): 276 freebusy.append(period) 277 elif freebusy[i] != period: 278 freebusy.insert(i, period) 279 280 def remove_period(freebusy, uid, recurrenceid=None): 281 282 """ 283 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 284 (which if omitted causes the "parent" object's periods to be referenced). 285 """ 286 287 removed = False 288 i = 0 289 while i < len(freebusy): 290 fb = freebusy[i] 291 if fb.uid == uid and fb.recurrenceid == recurrenceid: 292 del freebusy[i] 293 removed = True 294 else: 295 i += 1 296 297 return removed 298 299 def remove_additional_periods(freebusy, uid, recurrenceids=None): 300 301 """ 302 Remove from 'freebusy' all periods associated with 'uid' having a 303 recurrence identifier indicating an additional or modified period. 304 305 If 'recurrenceids' is specified, remove all periods associated with 'uid' 306 that do not have a recurrence identifier in the given list. 307 """ 308 309 i = 0 310 while i < len(freebusy): 311 fb = freebusy[i] 312 if fb.uid == uid and fb.recurrenceid and ( 313 recurrenceids is None or 314 recurrenceids is not None and fb.recurrenceid not in recurrenceids 315 ): 316 del freebusy[i] 317 else: 318 i += 1 319 320 def remove_affected_period(freebusy, uid, start): 321 322 """ 323 Remove from 'freebusy' a period associated with 'uid' that provides an 324 occurrence starting at the given 'start' (provided by a recurrence 325 identifier, converted to a datetime). A recurrence identifier is used to 326 provide an alternative time period whilst also acting as a reference to the 327 originally-defined occurrence. 328 """ 329 330 search = Period(start, start) 331 found = bisect_left(freebusy, search) 332 333 while found < len(freebusy): 334 fb = freebusy[found] 335 336 # Stop looking if the start no longer matches the recurrence identifier. 337 338 if fb.get_start_point() != search.get_start_point(): 339 return 340 341 # If the period belongs to the parent object, remove it and return. 342 343 if not fb.recurrenceid and uid == fb.uid: 344 del freebusy[found] 345 break 346 347 # Otherwise, keep looking for a matching period. 348 349 found += 1 350 351 def periods_from(freebusy, period): 352 353 "Return the entries in 'freebusy' at or after 'period'." 354 355 first = bisect_left(freebusy, period) 356 return freebusy[first:] 357 358 def periods_until(freebusy, period): 359 360 "Return the entries in 'freebusy' before 'period'." 361 362 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) 363 return freebusy[:last] 364 365 def get_overlapping(freebusy, period): 366 367 """ 368 Return the entries in 'freebusy' providing periods overlapping with 369 'period'. 370 """ 371 372 # Find the range of periods potentially overlapping the period in the 373 # free/busy collection. 374 375 startpoints = periods_until(freebusy, period) 376 377 # Find the range of periods potentially overlapping the period in a version 378 # of the free/busy collection sorted according to end datetimes. 379 380 endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints] 381 endpoints.sort() 382 first = bisect_left(endpoints, (period.get_start_point(),)) 383 endpoints = endpoints[first:] 384 385 overlapping = set() 386 387 for end, start, fb in endpoints: 388 if end > period.get_start_point() and start < period.get_end_point(): 389 overlapping.add(fb) 390 391 overlapping = list(overlapping) 392 overlapping.sort() 393 return overlapping 394 395 def period_overlaps(freebusy, period, get_periods=False): 396 397 """ 398 Return whether any period in 'freebusy' overlaps with the given 'period', 399 returning a collection of overlapping periods if 'get_periods' is set to a 400 true value. 401 """ 402 403 overlapping = get_overlapping(freebusy, period) 404 405 if get_periods: 406 return overlapping 407 else: 408 return len(overlapping) != 0 409 410 def remove_overlapping(freebusy, period): 411 412 "Remove from 'freebusy' all periods overlapping with 'period'." 413 414 overlapping = get_overlapping(freebusy, period) 415 416 if overlapping: 417 for fb in overlapping: 418 freebusy.remove(fb) 419 420 def replace_overlapping(freebusy, period, replacements): 421 422 """ 423 Replace existing periods in 'freebusy' within the given 'period', using the 424 given 'replacements'. 425 """ 426 427 remove_overlapping(freebusy, period) 428 for replacement in replacements: 429 insert_period(freebusy, replacement) 430 431 def get_free_periods(freebusy, period, overlapping=False): 432 433 """ 434 Return periods from 'freebusy' within which the given 'period' could be 435 inserted. If 'overlapping' is true, only return free periods that overlap 436 'period'. 437 """ 438 439 free = invert_freebusy(freebusy) 440 if not free: 441 return None 442 443 if overlapping: 444 return get_overlapping(free, period) 445 else: 446 return free 447 448 def coalesce_freebusy(freebusy): 449 450 "Coalesce the periods in 'freebusy'." 451 452 if not freebusy: 453 return freebusy 454 455 fb = [] 456 start = freebusy[0].get_start_point() 457 end = freebusy[0].get_end_point() 458 459 for period in freebusy[1:]: 460 if period.get_start_point() > end: 461 fb.append(FreeBusyPeriod(start, end)) 462 start = period.get_start_point() 463 end = period.get_end_point() 464 else: 465 end = max(end, period.get_end_point()) 466 467 fb.append(FreeBusyPeriod(start, end)) 468 return fb 469 470 def invert_freebusy(freebusy): 471 472 "Return the free periods from 'freebusy'." 473 474 if not freebusy: 475 return None 476 477 fb = coalesce_freebusy(freebusy) 478 free = [] 479 start = fb[0].get_end_point() 480 481 for period in fb[1:]: 482 free.append(FreeBusyPeriod(start, period.get_start_point())) 483 start = period.get_end_point() 484 485 return free 486 487 # Period layout. 488 489 def get_scale(periods, tzid): 490 491 """ 492 Return an ordered time scale from the given list of 'periods'. 493 494 The given 'tzid' is used to make sure that the times are defined according 495 to the chosen time zone. 496 497 The returned scale is a mapping from time to (starting, ending) tuples, 498 where starting and ending are collections of periods. 499 """ 500 501 scale = {} 502 503 for p in periods: 504 505 # Add a point and this event to the starting list. 506 507 start = to_timezone(p.get_start(), tzid) 508 if not scale.has_key(start): 509 scale[start] = [], [] 510 scale[start][0].append(p) 511 512 # Add a point and this event to the ending list. 513 514 end = to_timezone(p.get_end(), tzid) 515 if not scale.has_key(end): 516 scale[end] = [], [] 517 scale[end][1].append(p) 518 519 return scale 520 521 class Point: 522 523 "A qualified point in time." 524 525 PRINCIPAL, REPEATED = 0, 1 526 527 def __init__(self, point, indicator=None): 528 self.point = point 529 self.indicator = indicator or self.PRINCIPAL 530 531 def __hash__(self): 532 return hash((self.point, self.indicator)) 533 534 def __cmp__(self, other): 535 if isinstance(other, Point): 536 return cmp((self.point, self.indicator), (other.point, other.indicator)) 537 elif isinstance(other, datetime): 538 return cmp(self.point, other) 539 else: 540 return 1 541 542 def __eq__(self, other): 543 return self.__cmp__(other) == 0 544 545 def __ne__(self, other): 546 return not self == other 547 548 def __lt__(self, other): 549 return self.__cmp__(other) < 0 550 551 def __le__(self, other): 552 return self.__cmp__(other) <= 0 553 554 def __gt__(self, other): 555 return not self <= other 556 557 def __ge__(self, other): 558 return not self < other 559 560 def __repr__(self): 561 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 562 563 def get_slots(scale): 564 565 """ 566 Return an ordered list of time slots from the given 'scale'. 567 568 Each slot is a tuple containing details of a point in time for the start of 569 the slot, together with a list of parallel event periods. 570 571 Each point in time is described as a Point representing the actual point in 572 time together with an indicator of the nature of the point in time (as a 573 principal point in a time scale or as a repeated point used to terminate 574 events occurring for an instant in time). 575 """ 576 577 slots = [] 578 active = [] 579 580 points = scale.items() 581 points.sort() 582 583 for point, (starting, ending) in points: 584 ending = set(ending) 585 instants = ending.intersection(starting) 586 587 # Discard all active events ending at or before this start time. 588 # Free up the position in the active list. 589 590 for t in ending.difference(instants): 591 i = active.index(t) 592 active[i] = None 593 594 # For each event starting at the current point, fill any newly-vacated 595 # position or add to the end of the active list. 596 597 for t in starting: 598 try: 599 i = active.index(None) 600 active[i] = t 601 except ValueError: 602 active.append(t) 603 604 # Discard vacant positions from the end of the active list. 605 606 while active and active[-1] is None: 607 active.pop() 608 609 # Add an entry for the time point before "instants". 610 611 slots.append((Point(point), active[:])) 612 613 # Discard events ending at the same time as they began. 614 615 if instants: 616 for t in instants: 617 i = active.index(t) 618 active[i] = None 619 620 # Discard vacant positions from the end of the active list. 621 622 while active and active[-1] is None: 623 active.pop() 624 625 # Add another entry for the time point after "instants". 626 627 slots.append((Point(point, Point.REPEATED), active[:])) 628 629 return slots 630 631 def add_day_start_points(slots, tzid): 632 633 """ 634 Introduce into the 'slots' any day start points required by multi-day 635 periods. The 'tzid' is required to make sure that appropriate time zones 636 are chosen and not necessarily those provided by the existing time points. 637 """ 638 639 new_slots = [] 640 current_date = None 641 previously_active = [] 642 643 for point, active in slots: 644 start_of_day = get_start_of_day(point.point, tzid) 645 this_date = point.point.date() 646 647 # For each new day, add a slot for the start of the day where periods 648 # are active and where no such slot already exists. 649 650 if this_date != current_date: 651 652 # Fill in days where events remain active. 653 654 if current_date: 655 current_date += timedelta(1) 656 while current_date < this_date: 657 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 658 current_date += timedelta(1) 659 else: 660 current_date = this_date 661 662 # Add any continuing periods. 663 664 if point.point != start_of_day: 665 new_slots.append((Point(start_of_day), previously_active)) 666 667 # Add the currently active periods at this point in time. 668 669 previously_active = active 670 671 for t in new_slots: 672 insort_left(slots, t) 673 674 def add_slots(slots, points): 675 676 """ 677 Introduce into the 'slots' entries for those in 'points' that are not 678 already present, propagating active periods from time points preceding 679 those added. 680 """ 681 682 new_slots = [] 683 684 for point in points: 685 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 686 if i < len(slots) and slots[i][0] == point: 687 continue 688 689 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 690 691 for t in new_slots: 692 insort_left(slots, t) 693 694 def partition_by_day(slots): 695 696 """ 697 Return a mapping from dates to time points provided by 'slots'. 698 """ 699 700 d = {} 701 702 for point, value in slots: 703 day = point.point.date() 704 if not d.has_key(day): 705 d[day] = [] 706 d[day].append((point, value)) 707 708 return d 709 710 def add_empty_days(days, tzid): 711 712 "Add empty days to 'days' between busy days." 713 714 last_day = None 715 all_days = days.keys() 716 all_days.sort() 717 718 for day in all_days: 719 if last_day: 720 empty_day = last_day + timedelta(1) 721 while empty_day < day: 722 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 723 empty_day += timedelta(1) 724 last_day = day 725 726 def get_spans(slots): 727 728 "Inspect the given 'slots', returning a mapping of period keys to spans." 729 730 points = [point for point, active in slots] 731 spans = {} 732 733 for _point, active in slots: 734 for p in active: 735 if p: 736 key = p.get_key() 737 start_slot = bisect_left(points, p.get_start()) 738 end_slot = bisect_left(points, p.get_end()) 739 spans[key] = end_slot - start_slot 740 741 return spans 742 743 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 744 745 """ 746 Update the free/busy details with the given 'periods', 'transp' setting, 747 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 748 """ 749 750 remove_period(freebusy, uid, recurrenceid) 751 752 for p in periods: 753 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser)) 754 755 # vim: tabstop=4 expandtab shiftwidth=4