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