1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015, 2016 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 class FreeBusyCollection: 458 459 "An abstraction for a collection of free/busy periods." 460 461 def __init__(self, periods=None): 462 463 """ 464 Initialise the collection with the given list of 'periods', or start an 465 empty collection if no list is given. 466 """ 467 468 self.periods = periods or [] 469 470 # List emulation methods. 471 472 def __list__(self): 473 return self.periods 474 475 def __iter__(self): 476 return iter(self.periods) 477 478 def __len__(self): 479 return len(self.periods) 480 481 def __getitem__(self, i): 482 return self.periods[i] 483 484 def __iadd__(self, other): 485 for period in other: 486 self.insert_period(period) 487 return self 488 489 # Operations. 490 491 def can_schedule(self, periods, uid, recurrenceid): 492 493 """ 494 Return whether the collection can accommodate the given 'periods' 495 employing the specified 'uid' and 'recurrenceid'. 496 """ 497 498 for conflict in self.have_conflict(periods, True): 499 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 500 return False 501 502 return True 503 504 def have_conflict(self, periods, get_conflicts=False): 505 506 """ 507 Return whether any period in the collection overlaps with the given 508 'periods', returning a collection of such overlapping periods if 509 'get_conflicts' is set to a true value. 510 """ 511 512 conflicts = set() 513 for p in periods: 514 overlapping = self.period_overlaps(p, get_conflicts) 515 if overlapping: 516 if get_conflicts: 517 conflicts.update(overlapping) 518 else: 519 return True 520 521 if get_conflicts: 522 return conflicts 523 else: 524 return False 525 526 def insert_period(self, period): 527 528 "Insert the given 'period' into the collection." 529 530 i = bisect_left(self.periods, period) 531 if i == len(self.periods): 532 self.periods.append(period) 533 elif self.periods[i] != period: 534 self.periods.insert(i, period) 535 536 def remove_periods(self, periods): 537 538 "Remove the given 'periods' from the collection." 539 540 for period in periods: 541 i = bisect_left(self.periods, period) 542 if i < len(self.periods) and self.periods[i] == period: 543 del self.periods[i] 544 545 def remove_event_periods(self, uid, recurrenceid=None): 546 547 """ 548 Remove from the collection all periods associated with 'uid' and 549 'recurrenceid' (which if omitted causes the "parent" object's periods to 550 be referenced). 551 552 Return the removed periods. 553 """ 554 555 removed = [] 556 i = 0 557 while i < len(self.periods): 558 fb = self.periods[i] 559 if fb.uid == uid and fb.recurrenceid == recurrenceid: 560 removed.append(self.periods[i]) 561 del self.periods[i] 562 else: 563 i += 1 564 565 return removed 566 567 def remove_additional_periods(self, uid, recurrenceids=None): 568 569 """ 570 Remove from the collection all periods associated with 'uid' having a 571 recurrence identifier indicating an additional or modified period. 572 573 If 'recurrenceids' is specified, remove all periods associated with 574 'uid' that do not have a recurrence identifier in the given list. 575 576 Return the removed periods. 577 """ 578 579 removed = [] 580 i = 0 581 while i < len(self.periods): 582 fb = self.periods[i] 583 if fb.uid == uid and fb.recurrenceid and ( 584 recurrenceids is None or 585 recurrenceids is not None and fb.recurrenceid not in recurrenceids 586 ): 587 removed.append(self.periods[i]) 588 del self.periods[i] 589 else: 590 i += 1 591 592 return removed 593 594 def remove_affected_period(self, uid, start): 595 596 """ 597 Remove from the collection the period associated with 'uid' that 598 provides an occurrence starting at the given 'start' (provided by a 599 recurrence identifier, converted to a datetime). A recurrence identifier 600 is used to provide an alternative time period whilst also acting as a 601 reference to the originally-defined occurrence. 602 603 Return any removed period in a list. 604 """ 605 606 removed = [] 607 608 search = Period(start, start) 609 found = bisect_left(self.periods, search) 610 611 while found < len(self.periods): 612 fb = self.periods[found] 613 614 # Stop looking if the start no longer matches the recurrence identifier. 615 616 if fb.get_start_point() != search.get_start_point(): 617 break 618 619 # If the period belongs to the parent object, remove it and return. 620 621 if not fb.recurrenceid and uid == fb.uid: 622 removed.append(self.periods[found]) 623 del self.periods[found] 624 break 625 626 # Otherwise, keep looking for a matching period. 627 628 found += 1 629 630 return removed 631 632 def periods_from(self, period): 633 634 "Return the entries in the collection at or after 'period'." 635 636 first = bisect_left(self.periods, period) 637 return self.periods[first:] 638 639 def periods_until(self, period): 640 641 "Return the entries in the collection before 'period'." 642 643 last = bisect_right(self.periods, Period(period.get_end(), period.get_end(), period.get_tzid())) 644 return self.periods[:last] 645 646 def get_overlapping(self, period): 647 648 """ 649 Return the entries in the collection providing periods overlapping with 650 'period'. 651 """ 652 653 # Find the range of periods potentially overlapping the period in the 654 # free/busy collection. 655 656 startpoints = self.periods_until(period) 657 658 # Find the range of periods potentially overlapping the period in a version 659 # of the free/busy collection sorted according to end datetimes. 660 661 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 662 endpoints.sort() 663 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 664 endpoints = endpoints[first:] 665 666 overlapping = set() 667 668 for p, fb in endpoints: 669 if fb.overlaps(period): 670 overlapping.add(fb) 671 672 overlapping = list(overlapping) 673 overlapping.sort() 674 return overlapping 675 676 def period_overlaps(self, period, get_periods=False): 677 678 """ 679 Return whether any period in the collection overlaps with the given 680 'period', returning a collection of overlapping periods if 'get_periods' 681 is set to a true value. 682 """ 683 684 overlapping = self.get_overlapping(period) 685 686 if get_periods: 687 return overlapping 688 else: 689 return len(overlapping) != 0 690 691 def remove_overlapping(self, period): 692 693 "Remove all periods overlapping with 'period' from the collection." 694 695 overlapping = self.get_overlapping(period) 696 697 if overlapping: 698 for fb in overlapping: 699 self.periods.remove(fb) 700 701 def replace_overlapping(self, period, replacements): 702 703 """ 704 Replace existing periods in the collection within the given 'period', 705 using the given 'replacements'. 706 """ 707 708 self.remove_overlapping(period) 709 for replacement in replacements: 710 self.insert_period(replacement) 711 712 def coalesce_freebusy(self): 713 714 "Coalesce the periods in the collection, returning a new collection." 715 716 if not self.periods: 717 return FreeBusyCollection(self.periods) 718 719 fb = [] 720 start = self.periods[0].get_start_point() 721 end = self.periods[0].get_end_point() 722 723 for period in self.periods[1:]: 724 if period.get_start_point() > end: 725 fb.append(FreeBusyPeriod(start, end)) 726 start = period.get_start_point() 727 end = period.get_end_point() 728 else: 729 end = max(end, period.get_end_point()) 730 731 fb.append(FreeBusyPeriod(start, end)) 732 return FreeBusyCollection(fb) 733 734 def invert_freebusy(self): 735 736 "Return the free periods from the collection as a new collection." 737 738 if not self.periods: 739 return FreeBusyCollection([FreeBusyPeriod(None, None)]) 740 741 # Coalesce periods that overlap or are adjacent. 742 743 fb = self.coalesce_freebusy() 744 free = [] 745 746 # Add a start-of-time period if appropriate. 747 748 first = fb[0].get_start_point() 749 if first: 750 free.append(FreeBusyPeriod(None, first)) 751 752 start = fb[0].get_end_point() 753 754 for period in fb[1:]: 755 free.append(FreeBusyPeriod(start, period.get_start_point())) 756 start = period.get_end_point() 757 758 # Add an end-of-time period if appropriate. 759 760 if start: 761 free.append(FreeBusyPeriod(start, None)) 762 763 return FreeBusyCollection(free) 764 765 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 766 767 """ 768 Update the free/busy details with the given 'periods', 'transp' setting, 769 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 770 771 An optional 'expires' datetime string indicates the expiry time of any 772 free/busy offer. 773 """ 774 775 self.remove_event_periods(uid, recurrenceid) 776 777 for p in periods: 778 self.insert_period(FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 779 780 # Period layout. 781 782 def get_scale(periods, tzid, view_period=None): 783 784 """ 785 Return a time scale from the given list of 'periods'. 786 787 The given 'tzid' is used to make sure that the times are defined according 788 to the chosen time zone. 789 790 An optional 'view_period' is used to constrain the scale to the given 791 period. 792 793 The returned scale is a mapping from time to (starting, ending) tuples, 794 where starting and ending are collections of periods. 795 """ 796 797 scale = {} 798 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 799 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 800 801 for p in periods: 802 803 # Add a point and this event to the starting list. 804 805 start = to_timezone(p.get_start(), tzid) 806 start = view_start and max(start, view_start) or start 807 if not scale.has_key(start): 808 scale[start] = [], [] 809 scale[start][0].append(p) 810 811 # Add a point and this event to the ending list. 812 813 end = to_timezone(p.get_end(), tzid) 814 end = view_end and min(end, view_end) or end 815 if not scale.has_key(end): 816 scale[end] = [], [] 817 scale[end][1].append(p) 818 819 return scale 820 821 class Point: 822 823 "A qualified point in time." 824 825 PRINCIPAL, REPEATED = 0, 1 826 827 def __init__(self, point, indicator=None): 828 self.point = point 829 self.indicator = indicator or self.PRINCIPAL 830 831 def __hash__(self): 832 return hash((self.point, self.indicator)) 833 834 def __cmp__(self, other): 835 if isinstance(other, Point): 836 return cmp((self.point, self.indicator), (other.point, other.indicator)) 837 elif isinstance(other, datetime): 838 return cmp(self.point, other) 839 else: 840 return 1 841 842 def __eq__(self, other): 843 return self.__cmp__(other) == 0 844 845 def __ne__(self, other): 846 return not self == other 847 848 def __lt__(self, other): 849 return self.__cmp__(other) < 0 850 851 def __le__(self, other): 852 return self.__cmp__(other) <= 0 853 854 def __gt__(self, other): 855 return not self <= other 856 857 def __ge__(self, other): 858 return not self < other 859 860 def __repr__(self): 861 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 862 863 def get_slots(scale): 864 865 """ 866 Return an ordered list of time slots from the given 'scale'. 867 868 Each slot is a tuple containing details of a point in time for the start of 869 the slot, together with a list of parallel event periods. 870 871 Each point in time is described as a Point representing the actual point in 872 time together with an indicator of the nature of the point in time (as a 873 principal point in a time scale or as a repeated point used to terminate 874 events occurring for an instant in time). 875 """ 876 877 slots = [] 878 active = [] 879 880 points = scale.items() 881 points.sort() 882 883 for point, (starting, ending) in points: 884 ending = set(ending) 885 instants = ending.intersection(starting) 886 887 # Discard all active events ending at or before this start time. 888 # Free up the position in the active list. 889 890 for t in ending.difference(instants): 891 i = active.index(t) 892 active[i] = None 893 894 # For each event starting at the current point, fill any newly-vacated 895 # position or add to the end of the active list. 896 897 for t in starting: 898 try: 899 i = active.index(None) 900 active[i] = t 901 except ValueError: 902 active.append(t) 903 904 # Discard vacant positions from the end of the active list. 905 906 while active and active[-1] is None: 907 active.pop() 908 909 # Add an entry for the time point before "instants". 910 911 slots.append((Point(point), active[:])) 912 913 # Discard events ending at the same time as they began. 914 915 if instants: 916 for t in instants: 917 i = active.index(t) 918 active[i] = None 919 920 # Discard vacant positions from the end of the active list. 921 922 while active and active[-1] is None: 923 active.pop() 924 925 # Add another entry for the time point after "instants". 926 927 slots.append((Point(point, Point.REPEATED), active[:])) 928 929 return slots 930 931 def add_day_start_points(slots, tzid): 932 933 """ 934 Introduce into the 'slots' any day start points required by multi-day 935 periods. The 'tzid' is required to make sure that appropriate time zones 936 are chosen and not necessarily those provided by the existing time points. 937 """ 938 939 new_slots = [] 940 current_date = None 941 previously_active = [] 942 943 for point, active in slots: 944 start_of_day = get_start_of_day(point.point, tzid) 945 this_date = point.point.date() 946 947 # For each new day, add a slot for the start of the day where periods 948 # are active and where no such slot already exists. 949 950 if this_date != current_date: 951 952 # Fill in days where events remain active. 953 954 if current_date: 955 current_date += timedelta(1) 956 while current_date < this_date: 957 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 958 current_date += timedelta(1) 959 else: 960 current_date = this_date 961 962 # Add any continuing periods. 963 964 if point.point != start_of_day: 965 new_slots.append((Point(start_of_day), previously_active)) 966 967 # Add the currently active periods at this point in time. 968 969 previously_active = active 970 971 for t in new_slots: 972 insort_left(slots, t) 973 974 def remove_end_slot(slots, view_period): 975 976 """ 977 Remove from 'slots' any slot situated at the end of the given 'view_period'. 978 """ 979 980 end = view_period.get_end_point() 981 if not end or not slots: 982 return 983 i = bisect_left(slots, (Point(end), None)) 984 if i < len(slots): 985 del slots[i:] 986 987 def add_slots(slots, points): 988 989 """ 990 Introduce into the 'slots' entries for those in 'points' that are not 991 already present, propagating active periods from time points preceding 992 those added. 993 """ 994 995 new_slots = [] 996 997 for point in points: 998 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 999 if i < len(slots) and slots[i][0] == point: 1000 continue 1001 1002 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 1003 1004 for t in new_slots: 1005 insort_left(slots, t) 1006 1007 def partition_by_day(slots): 1008 1009 """ 1010 Return a mapping from dates to time points provided by 'slots'. 1011 """ 1012 1013 d = {} 1014 1015 for point, value in slots: 1016 day = point.point.date() 1017 if not d.has_key(day): 1018 d[day] = [] 1019 d[day].append((point, value)) 1020 1021 return d 1022 1023 def add_empty_days(days, tzid, start=None, end=None): 1024 1025 """ 1026 Add empty days to 'days' between busy days, and optionally from the given 1027 'start' day and until the given 'end' day. 1028 """ 1029 1030 last_day = start - timedelta(1) 1031 all_days = days.keys() 1032 all_days.sort() 1033 1034 for day in all_days: 1035 if last_day: 1036 empty_day = last_day + timedelta(1) 1037 while empty_day < day: 1038 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1039 empty_day += timedelta(1) 1040 last_day = day 1041 1042 if end: 1043 empty_day = last_day + timedelta(1) 1044 while empty_day < end: 1045 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1046 empty_day += timedelta(1) 1047 1048 def get_spans(slots): 1049 1050 "Inspect the given 'slots', returning a mapping of period keys to spans." 1051 1052 points = [point for point, active in slots] 1053 spans = {} 1054 1055 for _point, active in slots: 1056 for p in active: 1057 if p: 1058 key = p.get_key() 1059 start_slot = bisect_left(points, p.get_start()) 1060 end_slot = bisect_left(points, p.get_end()) 1061 spans[key] = end_slot - start_slot 1062 1063 return spans 1064 1065 # vim: tabstop=4 expandtab shiftwidth=4