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