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 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 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 if isinstance(start, (date, PointInTime)): 134 self.start = start 135 else: 136 self.start = get_datetime(start) or StartOfTime() 137 if isinstance(end, (date, PointInTime)): 138 self.end = end 139 else: 140 self.end = get_datetime(end) or EndOfTime() 141 142 def as_tuple(self): 143 return self.start, self.end 144 145 def __hash__(self): 146 return hash((self.get_start(), self.get_end())) 147 148 def __cmp__(self, other): 149 150 "Return a comparison result against 'other' using points in time." 151 152 if isinstance(other, PeriodBase): 153 return cmp( 154 (Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(self.get_end_point(), EndOfTime()))), 155 (Comparable(ifnone(other.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 156 ) 157 else: 158 return 1 159 160 def overlaps(self, other): 161 return Comparable(ifnone(self.get_end_point(), EndOfTime())) > Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 162 Comparable(ifnone(self.get_start_point(), StartOfTime())) < Comparable(ifnone(other.get_end_point(), EndOfTime())) 163 164 def within(self, other): 165 return Comparable(ifnone(self.get_start_point(), StartOfTime())) >= Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 166 Comparable(ifnone(self.get_end_point(), EndOfTime())) <= Comparable(ifnone(other.get_end_point(), EndOfTime())) 167 168 def common(self, other): 169 start = max(Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_start_point(), StartOfTime()))) 170 end = min(Comparable(ifnone(self.get_end_point(), EndOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 171 if start <= end: 172 return self.make_corrected(start.dt, end.dt) 173 else: 174 return None 175 176 def get_key(self): 177 return self.get_start(), self.get_end() 178 179 # Datetime and metadata methods. 180 181 def get_start(self): 182 return self.start 183 184 def get_end(self): 185 return self.end 186 187 def get_start_attr(self): 188 return get_datetime_attributes(self.start, self.tzid) 189 190 def get_end_attr(self): 191 return get_datetime_attributes(self.end, self.tzid) 192 193 def get_start_item(self): 194 return self.get_start(), self.get_start_attr() 195 196 def get_end_item(self): 197 return self.get_end(), self.get_end_attr() 198 199 def get_start_point(self): 200 return self.start 201 202 def get_end_point(self): 203 return self.end 204 205 def get_duration(self): 206 start = self.get_start_point() 207 end = self.get_end_point() 208 if start and end: 209 return end - start 210 else: 211 return Endless() 212 213 class Period(PeriodBase): 214 215 "A simple period abstraction." 216 217 def __init__(self, start, end, tzid=None, origin=None): 218 219 """ 220 Initialise a period with the given 'start' and 'end', having a 221 contextual 'tzid', if specified, and an indicated 'origin'. 222 223 All metadata from the start and end points are derived from the supplied 224 dates/datetimes. 225 """ 226 227 PeriodBase.__init__(self, start, end) 228 self.tzid = tzid 229 self.origin = origin 230 231 def as_tuple(self): 232 return self.start, self.end, self.tzid, self.origin 233 234 def __repr__(self): 235 return "Period%r" % (self.as_tuple(),) 236 237 # Datetime and metadata methods. 238 239 def get_tzid(self): 240 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 241 242 def get_start_point(self): 243 start = self.get_start() 244 if isinstance(start, PointInTime): return start 245 else: return to_utc_datetime(start, self.get_tzid()) 246 247 def get_end_point(self): 248 end = self.get_end() 249 if isinstance(end, PointInTime): return end 250 else: return to_utc_datetime(end, self.get_tzid()) 251 252 # Period and event recurrence logic. 253 254 def is_replaced(self, recurrenceids): 255 256 """ 257 Return whether this period refers to one of the 'recurrenceids'. 258 The 'recurrenceids' should be normalised to UTC datetimes according to 259 time zone information provided by their objects or be floating dates or 260 datetimes requiring conversion using contextual time zone information. 261 """ 262 263 for recurrenceid in recurrenceids: 264 if self.is_affected(recurrenceid): 265 return recurrenceid 266 return None 267 268 def is_affected(self, recurrenceid): 269 270 """ 271 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 272 should be normalised to UTC datetimes according to time zone information 273 provided by their objects. Otherwise, this period's contextual time zone 274 information is used to convert any date or floating datetime 275 representation to a point in time. 276 """ 277 278 if not recurrenceid: 279 return None 280 d = get_recurrence_start(recurrenceid) 281 dt = get_recurrence_start_point(recurrenceid, self.tzid) 282 if self.get_start() == d or self.get_start_point() == dt: 283 return recurrenceid 284 return None 285 286 # Value correction methods. 287 288 def with_duration(self, duration): 289 290 """ 291 Return a version of this period with the same start point but with the 292 given 'duration'. 293 """ 294 295 return self.make_corrected(self.get_start(), self.get_start() + duration) 296 297 def check_permitted(self, permitted_values): 298 299 "Check the period against the given 'permitted_values'." 300 301 start = self.get_start() 302 end = self.get_end() 303 start_errors = check_permitted_values(start, permitted_values) 304 end_errors = check_permitted_values(end, permitted_values) 305 306 if not (start_errors or end_errors): 307 return None 308 309 return start_errors, end_errors 310 311 def get_corrected(self, permitted_values): 312 313 "Return a corrected version of this period." 314 315 errors = self.check_permitted(permitted_values) 316 317 if not errors: 318 return self 319 320 start_errors, end_errors = errors 321 322 start = self.get_start() 323 end = self.get_end() 324 325 if start_errors: 326 start = correct_datetime(start, permitted_values) 327 if end_errors: 328 end = correct_datetime(end, permitted_values) 329 330 return self.make_corrected(start, end) 331 332 def make_corrected(self, start, end): 333 return self.__class__(start, end, self.tzid, self.origin) 334 335 class FreeBusyPeriod(PeriodBase): 336 337 "A free/busy record abstraction." 338 339 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None): 340 341 """ 342 Initialise a free/busy period with the given 'start' and 'end' points, 343 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 344 details. 345 346 An additional 'expires' parameter can be used to indicate an expiry 347 datetime in conjunction with free/busy offers made when countering 348 event proposals. 349 """ 350 351 PeriodBase.__init__(self, start, end) 352 self.uid = uid 353 self.transp = transp 354 self.recurrenceid = recurrenceid 355 self.summary = summary 356 self.organiser = organiser 357 self.expires = expires 358 359 def as_tuple(self, strings_only=False): 360 361 """ 362 Return the initialisation parameter tuple, converting false value 363 parameters to strings if 'strings_only' is set to a true value. 364 """ 365 366 null = lambda x: (strings_only and [""] or [x])[0] 367 return ( 368 strings_only and format_datetime(self.get_start_point()) or self.start, 369 strings_only and format_datetime(self.get_end_point()) or self.end, 370 self.uid or null(self.uid), 371 self.transp or strings_only and "OPAQUE" or None, 372 self.recurrenceid or null(self.recurrenceid), 373 self.summary or null(self.summary), 374 self.organiser or null(self.organiser), 375 self.expires or null(self.expires) 376 ) 377 378 def __cmp__(self, other): 379 380 """ 381 Compare this object to 'other', employing the uid if the periods 382 involved are the same. 383 """ 384 385 result = PeriodBase.__cmp__(self, other) 386 if result == 0 and isinstance(other, FreeBusyPeriod): 387 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 388 else: 389 return result 390 391 def get_key(self): 392 return self.uid, self.recurrenceid, self.get_start() 393 394 def __repr__(self): 395 return "FreeBusyPeriod%r" % (self.as_tuple(),) 396 397 def get_tzid(self): 398 return "UTC" 399 400 # Period and event recurrence logic. 401 402 def is_replaced(self, recurrences): 403 404 """ 405 Return whether this period refers to one of the 'recurrences'. 406 The 'recurrences' must be UTC datetimes corresponding to the start of 407 the period described by a recurrence. 408 """ 409 410 for recurrence in recurrences: 411 if self.is_affected(recurrence): 412 return True 413 return False 414 415 def is_affected(self, recurrence): 416 417 """ 418 Return whether this period refers to 'recurrence'. The 'recurrence' must 419 be a UTC datetime corresponding to the start of the period described by 420 a recurrence. 421 """ 422 423 return recurrence and self.get_start_point() == recurrence 424 425 # Value correction methods. 426 427 def make_corrected(self, start, end): 428 return self.__class__(start, end) 429 430 class RecurringPeriod(Period): 431 432 """ 433 A period with iCalendar metadata attributes and origin information from an 434 object. 435 """ 436 437 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 438 Period.__init__(self, start, end, tzid, origin) 439 self.start_attr = start_attr 440 self.end_attr = end_attr 441 442 def get_start_attr(self): 443 return self.start_attr 444 445 def get_end_attr(self): 446 return self.end_attr 447 448 def as_tuple(self): 449 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 450 451 def __repr__(self): 452 return "RecurringPeriod%r" % (self.as_tuple(),) 453 454 def make_corrected(self, start, end): 455 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 456 457 # Time and period management. 458 459 def can_schedule(freebusy, periods, uid, recurrenceid): 460 461 """ 462 Return whether the 'freebusy' list can accommodate the given 'periods' 463 employing the specified 'uid' and 'recurrenceid'. 464 """ 465 466 for conflict in have_conflict(freebusy, periods, True): 467 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 468 return False 469 470 return True 471 472 def have_conflict(freebusy, periods, get_conflicts=False): 473 474 """ 475 Return whether any period in 'freebusy' overlaps with the given 'periods', 476 returning a collection of such overlapping periods if 'get_conflicts' is 477 set to a true value. 478 """ 479 480 conflicts = set() 481 for p in periods: 482 overlapping = period_overlaps(freebusy, p, get_conflicts) 483 if overlapping: 484 if get_conflicts: 485 conflicts.update(overlapping) 486 else: 487 return True 488 489 if get_conflicts: 490 return conflicts 491 else: 492 return False 493 494 def insert_period(freebusy, period): 495 496 "Insert into 'freebusy' the given 'period'." 497 498 i = bisect_left(freebusy, period) 499 if i == len(freebusy): 500 freebusy.append(period) 501 elif freebusy[i] != period: 502 freebusy.insert(i, period) 503 504 def remove_periods(freebusy, periods): 505 506 "Remove from 'freebusy' the given 'periods'." 507 508 for period in periods: 509 i = bisect_left(freebusy, period) 510 if i < len(freebusy) and freebusy[i] == period: 511 del freebusy[i] 512 513 def remove_event_periods(freebusy, uid, recurrenceid=None): 514 515 """ 516 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 517 (which if omitted causes the "parent" object's periods to be referenced). 518 519 Return the removed periods. 520 """ 521 522 removed = [] 523 i = 0 524 while i < len(freebusy): 525 fb = freebusy[i] 526 if fb.uid == uid and fb.recurrenceid == recurrenceid: 527 removed.append(freebusy[i]) 528 del freebusy[i] 529 else: 530 i += 1 531 532 return removed 533 534 def remove_additional_periods(freebusy, uid, recurrenceids=None): 535 536 """ 537 Remove from 'freebusy' all periods associated with 'uid' having a 538 recurrence identifier indicating an additional or modified period. 539 540 If 'recurrenceids' is specified, remove all periods associated with 'uid' 541 that do not have a recurrence identifier in the given list. 542 """ 543 544 i = 0 545 while i < len(freebusy): 546 fb = freebusy[i] 547 if fb.uid == uid and fb.recurrenceid and ( 548 recurrenceids is None or 549 recurrenceids is not None and fb.recurrenceid not in recurrenceids 550 ): 551 del freebusy[i] 552 else: 553 i += 1 554 555 def remove_affected_period(freebusy, uid, start): 556 557 """ 558 Remove from 'freebusy' a period associated with 'uid' that provides an 559 occurrence starting at the given 'start' (provided by a recurrence 560 identifier, converted to a datetime). A recurrence identifier is used to 561 provide an alternative time period whilst also acting as a reference to the 562 originally-defined occurrence. 563 """ 564 565 search = Period(start, start) 566 found = bisect_left(freebusy, search) 567 568 while found < len(freebusy): 569 fb = freebusy[found] 570 571 # Stop looking if the start no longer matches the recurrence identifier. 572 573 if fb.get_start_point() != search.get_start_point(): 574 return 575 576 # If the period belongs to the parent object, remove it and return. 577 578 if not fb.recurrenceid and uid == fb.uid: 579 del freebusy[found] 580 break 581 582 # Otherwise, keep looking for a matching period. 583 584 found += 1 585 586 def periods_from(freebusy, period): 587 588 "Return the entries in 'freebusy' at or after 'period'." 589 590 first = bisect_left(freebusy, period) 591 return freebusy[first:] 592 593 def periods_until(freebusy, period): 594 595 "Return the entries in 'freebusy' before 'period'." 596 597 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) 598 return freebusy[:last] 599 600 def get_overlapping(freebusy, period): 601 602 """ 603 Return the entries in 'freebusy' providing periods overlapping with 604 'period'. 605 """ 606 607 # Find the range of periods potentially overlapping the period in the 608 # free/busy collection. 609 610 startpoints = periods_until(freebusy, period) 611 612 # Find the range of periods potentially overlapping the period in a version 613 # of the free/busy collection sorted according to end datetimes. 614 615 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 616 endpoints.sort() 617 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 618 endpoints = endpoints[first:] 619 620 overlapping = set() 621 622 for p, fb in endpoints: 623 if fb.overlaps(period): 624 overlapping.add(fb) 625 626 overlapping = list(overlapping) 627 overlapping.sort() 628 return overlapping 629 630 def period_overlaps(freebusy, period, get_periods=False): 631 632 """ 633 Return whether any period in 'freebusy' overlaps with the given 'period', 634 returning a collection of overlapping periods if 'get_periods' is set to a 635 true value. 636 """ 637 638 overlapping = get_overlapping(freebusy, period) 639 640 if get_periods: 641 return overlapping 642 else: 643 return len(overlapping) != 0 644 645 def remove_overlapping(freebusy, period): 646 647 "Remove from 'freebusy' all periods overlapping with 'period'." 648 649 overlapping = get_overlapping(freebusy, period) 650 651 if overlapping: 652 for fb in overlapping: 653 freebusy.remove(fb) 654 655 def replace_overlapping(freebusy, period, replacements): 656 657 """ 658 Replace existing periods in 'freebusy' within the given 'period', using the 659 given 'replacements'. 660 """ 661 662 remove_overlapping(freebusy, period) 663 for replacement in replacements: 664 insert_period(freebusy, replacement) 665 666 def coalesce_freebusy(freebusy): 667 668 "Coalesce the periods in 'freebusy'." 669 670 if not freebusy: 671 return freebusy 672 673 fb = [] 674 start = freebusy[0].get_start_point() 675 end = freebusy[0].get_end_point() 676 677 for period in freebusy[1:]: 678 if period.get_start_point() > end: 679 fb.append(FreeBusyPeriod(start, end)) 680 start = period.get_start_point() 681 end = period.get_end_point() 682 else: 683 end = max(end, period.get_end_point()) 684 685 fb.append(FreeBusyPeriod(start, end)) 686 return fb 687 688 def invert_freebusy(freebusy): 689 690 "Return the free periods from 'freebusy'." 691 692 if not freebusy: 693 return [FreeBusyPeriod(None, None)] 694 695 # Coalesce periods that overlap or are adjacent. 696 697 fb = coalesce_freebusy(freebusy) 698 free = [] 699 700 # Add a start-of-time period if appropriate. 701 702 first = fb[0].get_start_point() 703 if first: 704 free.append(FreeBusyPeriod(None, first)) 705 706 start = fb[0].get_end_point() 707 708 for period in fb[1:]: 709 free.append(FreeBusyPeriod(start, period.get_start_point())) 710 start = period.get_end_point() 711 712 # Add an end-of-time period if appropriate. 713 714 if start: 715 free.append(FreeBusyPeriod(start, None)) 716 717 return free 718 719 def get_common_periods(all_freebusy): 720 721 "Return common periods to all collections in the 'all_freebusy' list." 722 723 if not all_freebusy: 724 return None 725 726 common = all_freebusy[0] 727 728 # Intersect periods with the current common set. 729 730 for freebusy in all_freebusy[1:]: 731 new_common = [] 732 733 # Find the overlapping periods and then obtain the regions that 734 # are common to both sets. 735 736 for period in freebusy: 737 for overlapping in get_overlapping(common, period): 738 p = period.common(overlapping) 739 if p: 740 new_common.append(p) 741 742 common = new_common 743 744 return common 745 746 # Period layout. 747 748 def get_scale(periods, tzid, view_period=None): 749 750 """ 751 Return a time scale from the given list of 'periods'. 752 753 The given 'tzid' is used to make sure that the times are defined according 754 to the chosen time zone. 755 756 An optional 'view_period' is used to constrain the scale to the given 757 period. 758 759 The returned scale is a mapping from time to (starting, ending) tuples, 760 where starting and ending are collections of periods. 761 """ 762 763 scale = {} 764 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 765 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 766 767 for p in periods: 768 769 # Add a point and this event to the starting list. 770 771 start = to_timezone(p.get_start(), tzid) 772 start = view_start and max(start, view_start) or start 773 if not scale.has_key(start): 774 scale[start] = [], [] 775 scale[start][0].append(p) 776 777 # Add a point and this event to the ending list. 778 779 end = to_timezone(p.get_end(), tzid) 780 end = view_end and min(end, view_end) or end 781 if not scale.has_key(end): 782 scale[end] = [], [] 783 scale[end][1].append(p) 784 785 return scale 786 787 class Point: 788 789 "A qualified point in time." 790 791 PRINCIPAL, REPEATED = 0, 1 792 793 def __init__(self, point, indicator=None): 794 self.point = point 795 self.indicator = indicator or self.PRINCIPAL 796 797 def __hash__(self): 798 return hash((self.point, self.indicator)) 799 800 def __cmp__(self, other): 801 if isinstance(other, Point): 802 return cmp((self.point, self.indicator), (other.point, other.indicator)) 803 elif isinstance(other, datetime): 804 return cmp(self.point, other) 805 else: 806 return 1 807 808 def __eq__(self, other): 809 return self.__cmp__(other) == 0 810 811 def __ne__(self, other): 812 return not self == other 813 814 def __lt__(self, other): 815 return self.__cmp__(other) < 0 816 817 def __le__(self, other): 818 return self.__cmp__(other) <= 0 819 820 def __gt__(self, other): 821 return not self <= other 822 823 def __ge__(self, other): 824 return not self < other 825 826 def __repr__(self): 827 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 828 829 def get_slots(scale): 830 831 """ 832 Return an ordered list of time slots from the given 'scale'. 833 834 Each slot is a tuple containing details of a point in time for the start of 835 the slot, together with a list of parallel event periods. 836 837 Each point in time is described as a Point representing the actual point in 838 time together with an indicator of the nature of the point in time (as a 839 principal point in a time scale or as a repeated point used to terminate 840 events occurring for an instant in time). 841 """ 842 843 slots = [] 844 active = [] 845 846 points = scale.items() 847 points.sort() 848 849 for point, (starting, ending) in points: 850 ending = set(ending) 851 instants = ending.intersection(starting) 852 853 # Discard all active events ending at or before this start time. 854 # Free up the position in the active list. 855 856 for t in ending.difference(instants): 857 i = active.index(t) 858 active[i] = None 859 860 # For each event starting at the current point, fill any newly-vacated 861 # position or add to the end of the active list. 862 863 for t in starting: 864 try: 865 i = active.index(None) 866 active[i] = t 867 except ValueError: 868 active.append(t) 869 870 # Discard vacant positions from the end of the active list. 871 872 while active and active[-1] is None: 873 active.pop() 874 875 # Add an entry for the time point before "instants". 876 877 slots.append((Point(point), active[:])) 878 879 # Discard events ending at the same time as they began. 880 881 if instants: 882 for t in instants: 883 i = active.index(t) 884 active[i] = None 885 886 # Discard vacant positions from the end of the active list. 887 888 while active and active[-1] is None: 889 active.pop() 890 891 # Add another entry for the time point after "instants". 892 893 slots.append((Point(point, Point.REPEATED), active[:])) 894 895 return slots 896 897 def add_day_start_points(slots, tzid): 898 899 """ 900 Introduce into the 'slots' any day start points required by multi-day 901 periods. The 'tzid' is required to make sure that appropriate time zones 902 are chosen and not necessarily those provided by the existing time points. 903 """ 904 905 new_slots = [] 906 current_date = None 907 previously_active = [] 908 909 for point, active in slots: 910 start_of_day = get_start_of_day(point.point, tzid) 911 this_date = point.point.date() 912 913 # For each new day, add a slot for the start of the day where periods 914 # are active and where no such slot already exists. 915 916 if this_date != current_date: 917 918 # Fill in days where events remain active. 919 920 if current_date: 921 current_date += timedelta(1) 922 while current_date < this_date: 923 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 924 current_date += timedelta(1) 925 else: 926 current_date = this_date 927 928 # Add any continuing periods. 929 930 if point.point != start_of_day: 931 new_slots.append((Point(start_of_day), previously_active)) 932 933 # Add the currently active periods at this point in time. 934 935 previously_active = active 936 937 for t in new_slots: 938 insort_left(slots, t) 939 940 def remove_end_slot(slots, view_period): 941 942 """ 943 Remove from 'slots' any slot situated at the end of the given 'view_period'. 944 """ 945 946 end = view_period.get_end_point() 947 if not end or not slots: 948 return 949 i = bisect_left(slots, (Point(end), None)) 950 if i < len(slots): 951 del slots[i:] 952 953 def add_slots(slots, points): 954 955 """ 956 Introduce into the 'slots' entries for those in 'points' that are not 957 already present, propagating active periods from time points preceding 958 those added. 959 """ 960 961 new_slots = [] 962 963 for point in points: 964 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 965 if i < len(slots) and slots[i][0] == point: 966 continue 967 968 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 969 970 for t in new_slots: 971 insort_left(slots, t) 972 973 def partition_by_day(slots): 974 975 """ 976 Return a mapping from dates to time points provided by 'slots'. 977 """ 978 979 d = {} 980 981 for point, value in slots: 982 day = point.point.date() 983 if not d.has_key(day): 984 d[day] = [] 985 d[day].append((point, value)) 986 987 return d 988 989 def add_empty_days(days, tzid, start=None, end=None): 990 991 """ 992 Add empty days to 'days' between busy days, and optionally from the given 993 'start' day and until the given 'end' day. 994 """ 995 996 last_day = start - timedelta(1) 997 all_days = days.keys() 998 all_days.sort() 999 1000 for day in all_days: 1001 if last_day: 1002 empty_day = last_day + timedelta(1) 1003 while empty_day < day: 1004 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1005 empty_day += timedelta(1) 1006 last_day = day 1007 1008 if end: 1009 empty_day = last_day + timedelta(1) 1010 while empty_day < end: 1011 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1012 empty_day += timedelta(1) 1013 1014 def get_spans(slots): 1015 1016 "Inspect the given 'slots', returning a mapping of period keys to spans." 1017 1018 points = [point for point, active in slots] 1019 spans = {} 1020 1021 for _point, active in slots: 1022 for p in active: 1023 if p: 1024 key = p.get_key() 1025 start_slot = bisect_left(points, p.get_start()) 1026 end_slot = bisect_left(points, p.get_end()) 1027 spans[key] = end_slot - start_slot 1028 1029 return spans 1030 1031 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 1032 1033 """ 1034 Update the free/busy details with the given 'periods', 'transp' setting, 1035 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 1036 1037 An optional 'expires' datetime string indicates the expiry time of any 1038 free/busy offer. 1039 """ 1040 1041 remove_event_periods(freebusy, uid, recurrenceid) 1042 1043 for p in periods: 1044 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 1045 1046 # vim: tabstop=4 expandtab shiftwidth=4