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 from imiptools.sql import DatabaseOperations 32 33 def ifnone(x, y): 34 if x is None: return y 35 else: return x 36 37 def from_string(s, encoding): 38 if s: 39 return unicode(s, encoding) 40 else: 41 return s 42 43 def to_string(s, encoding): 44 if s: 45 return s.encode(encoding) 46 else: 47 return s 48 49 class Comparable: 50 51 "A date/datetime wrapper that allows comparisons with other types." 52 53 def __init__(self, dt): 54 self.dt = dt 55 56 def __cmp__(self, other): 57 dt = None 58 odt = None 59 60 # Find any dates/datetimes. 61 62 if isinstance(self.dt, date): 63 dt = self.dt 64 if isinstance(other, date): 65 odt = other 66 elif isinstance(other, Comparable): 67 if isinstance(other.dt, date): 68 odt = other.dt 69 else: 70 other = other.dt 71 72 if dt and odt: 73 return cmp(dt, odt) 74 elif dt: 75 return other.__rcmp__(dt) 76 elif odt: 77 return self.dt.__cmp__(odt) 78 else: 79 return self.dt.__cmp__(other) 80 81 class PointInTime: 82 83 "A base class for special values." 84 85 pass 86 87 class StartOfTime(PointInTime): 88 89 "A special value that compares earlier than other values." 90 91 def __cmp__(self, other): 92 if isinstance(other, StartOfTime): 93 return 0 94 else: 95 return -1 96 97 def __rcmp__(self, other): 98 return -self.__cmp__(other) 99 100 def __nonzero__(self): 101 return False 102 103 def __hash__(self): 104 return 0 105 106 class EndOfTime(PointInTime): 107 108 "A special value that compares later than other values." 109 110 def __cmp__(self, other): 111 if isinstance(other, EndOfTime): 112 return 0 113 else: 114 return 1 115 116 def __rcmp__(self, other): 117 return -self.__cmp__(other) 118 119 def __nonzero__(self): 120 return False 121 122 def __hash__(self): 123 return 0 124 125 class Endless: 126 127 "A special value indicating an endless period." 128 129 def __cmp__(self, other): 130 if isinstance(other, Endless): 131 return 0 132 else: 133 return 1 134 135 def __rcmp__(self, other): 136 return -self.__cmp__(other) 137 138 def __nonzero__(self): 139 return True 140 141 class PeriodBase: 142 143 "A basic period abstraction." 144 145 def __init__(self, start, end): 146 147 """ 148 Define a period according to 'start' and 'end' which may be special 149 start/end of time values or iCalendar-format datetime strings. 150 """ 151 152 if isinstance(start, (date, PointInTime)): 153 self.start = start 154 else: 155 self.start = get_datetime(start) or StartOfTime() 156 157 if isinstance(end, (date, PointInTime)): 158 self.end = end 159 else: 160 self.end = get_datetime(end) or EndOfTime() 161 162 def as_tuple(self): 163 return self.start, self.end 164 165 def __hash__(self): 166 return hash((self.get_start(), self.get_end())) 167 168 def __cmp__(self, other): 169 170 "Return a comparison result against 'other' using points in time." 171 172 if isinstance(other, PeriodBase): 173 return cmp( 174 (Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(self.get_end_point(), EndOfTime()))), 175 (Comparable(ifnone(other.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 176 ) 177 else: 178 return 1 179 180 def overlaps(self, other): 181 return Comparable(ifnone(self.get_end_point(), EndOfTime())) > Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 182 Comparable(ifnone(self.get_start_point(), StartOfTime())) < Comparable(ifnone(other.get_end_point(), EndOfTime())) 183 184 def within(self, other): 185 return Comparable(ifnone(self.get_start_point(), StartOfTime())) >= Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 186 Comparable(ifnone(self.get_end_point(), EndOfTime())) <= Comparable(ifnone(other.get_end_point(), EndOfTime())) 187 188 def common(self, other): 189 start = max(Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_start_point(), StartOfTime()))) 190 end = min(Comparable(ifnone(self.get_end_point(), EndOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 191 if start <= end: 192 return self.make_corrected(start.dt, end.dt) 193 else: 194 return None 195 196 def get_key(self): 197 return self.get_start(), self.get_end() 198 199 # Datetime and metadata methods. 200 201 def get_start(self): 202 return self.start 203 204 def get_end(self): 205 return self.end 206 207 def get_start_attr(self): 208 return get_datetime_attributes(self.start, self.tzid) 209 210 def get_end_attr(self): 211 return get_datetime_attributes(self.end, self.tzid) 212 213 def get_start_item(self): 214 return self.get_start(), self.get_start_attr() 215 216 def get_end_item(self): 217 return self.get_end(), self.get_end_attr() 218 219 def get_start_point(self): 220 return self.start 221 222 def get_end_point(self): 223 return self.end 224 225 def get_duration(self): 226 start = self.get_start_point() 227 end = self.get_end_point() 228 if start and end: 229 return end - start 230 else: 231 return Endless() 232 233 class Period(PeriodBase): 234 235 "A simple period abstraction." 236 237 def __init__(self, start, end, tzid=None, origin=None): 238 239 """ 240 Initialise a period with the given 'start' and 'end', having a 241 contextual 'tzid', if specified, and an indicated 'origin'. 242 243 All metadata from the start and end points are derived from the supplied 244 dates/datetimes. 245 """ 246 247 PeriodBase.__init__(self, start, end) 248 self.tzid = tzid 249 self.origin = origin 250 251 def as_tuple(self): 252 return self.start, self.end, self.tzid, self.origin 253 254 def __repr__(self): 255 return "Period%r" % (self.as_tuple(),) 256 257 # Datetime and metadata methods. 258 259 def get_tzid(self): 260 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 261 262 def get_start_point(self): 263 start = self.get_start() 264 if isinstance(start, PointInTime): return start 265 else: return to_utc_datetime(start, self.get_tzid()) 266 267 def get_end_point(self): 268 end = self.get_end() 269 if isinstance(end, PointInTime): return end 270 else: return to_utc_datetime(end, self.get_tzid()) 271 272 # Period and event recurrence logic. 273 274 def is_replaced(self, recurrenceids): 275 276 """ 277 Return whether this period refers to one of the 'recurrenceids'. 278 The 'recurrenceids' should be normalised to UTC datetimes according to 279 time zone information provided by their objects or be floating dates or 280 datetimes requiring conversion using contextual time zone information. 281 """ 282 283 for recurrenceid in recurrenceids: 284 if self.is_affected(recurrenceid): 285 return recurrenceid 286 return None 287 288 def is_affected(self, recurrenceid): 289 290 """ 291 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 292 should be normalised to UTC datetimes according to time zone information 293 provided by their objects. Otherwise, this period's contextual time zone 294 information is used to convert any date or floating datetime 295 representation to a point in time. 296 """ 297 298 if not recurrenceid: 299 return None 300 d = get_recurrence_start(recurrenceid) 301 dt = get_recurrence_start_point(recurrenceid, self.tzid) 302 303 # Compare the start to dates only, using the normalised start datetime 304 # for comparisons with the start point. 305 306 if not isinstance(d, datetime) and self.get_start() == d or self.get_start_point() == dt: 307 return recurrenceid 308 309 return None 310 311 # Value correction methods. 312 313 def with_duration(self, duration): 314 315 """ 316 Return a version of this period with the same start point but with the 317 given 'duration'. 318 """ 319 320 return self.make_corrected(self.get_start(), self.get_start() + duration) 321 322 def check_permitted(self, permitted_values): 323 324 "Check the period against the given 'permitted_values'." 325 326 start = self.get_start() 327 end = self.get_end() 328 start_errors = check_permitted_values(start, permitted_values) 329 end_errors = check_permitted_values(end, permitted_values) 330 331 if not (start_errors or end_errors): 332 return None 333 334 return start_errors, end_errors 335 336 def get_corrected(self, permitted_values): 337 338 "Return a corrected version of this period." 339 340 errors = self.check_permitted(permitted_values) 341 342 if not errors: 343 return self 344 345 start_errors, end_errors = errors 346 347 start = self.get_start() 348 end = self.get_end() 349 350 if start_errors: 351 start = correct_datetime(start, permitted_values) 352 if end_errors: 353 end = correct_datetime(end, permitted_values) 354 355 return self.make_corrected(start, end) 356 357 def make_corrected(self, start, end): 358 return self.__class__(start, end, self.tzid, self.origin) 359 360 class FreeBusyPeriod(PeriodBase): 361 362 "A free/busy record abstraction." 363 364 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, 365 summary=None, organiser=None): 366 367 """ 368 Initialise a free/busy period with the given 'start' and 'end' points, 369 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 370 details. 371 """ 372 373 PeriodBase.__init__(self, start, end) 374 self.uid = uid 375 self.transp = transp or None 376 self.recurrenceid = recurrenceid or None 377 self.summary = summary or None 378 self.organiser = organiser or None 379 380 def as_tuple(self, strings_only=False, string_datetimes=False): 381 382 """ 383 Return the initialisation parameter tuple, converting datetimes and 384 false value parameters to strings if 'strings_only' is set to a true 385 value. Otherwise, if 'string_datetimes' is set to a true value, only the 386 datetime values are converted to strings. 387 """ 388 389 null = lambda x: (strings_only and [""] or [x])[0] 390 return ( 391 (strings_only or string_datetimes) and format_datetime(self.get_start_point()) or self.start, 392 (strings_only or string_datetimes) and format_datetime(self.get_end_point()) or self.end, 393 self.uid or null(self.uid), 394 self.transp or strings_only and "OPAQUE" or None, 395 self.recurrenceid or null(self.recurrenceid), 396 self.summary or null(self.summary), 397 self.organiser or null(self.organiser) 398 ) 399 400 def __cmp__(self, other): 401 402 """ 403 Compare this object to 'other', employing the uid if the periods 404 involved are the same. 405 """ 406 407 result = PeriodBase.__cmp__(self, other) 408 if result == 0 and isinstance(other, FreeBusyPeriod): 409 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 410 else: 411 return result 412 413 def get_key(self): 414 return self.uid, self.recurrenceid, self.get_start() 415 416 def __repr__(self): 417 return "FreeBusyPeriod%r" % (self.as_tuple(),) 418 419 def get_tzid(self): 420 return "UTC" 421 422 # Period and event recurrence logic. 423 424 def is_replaced(self, recurrences): 425 426 """ 427 Return whether this period refers to one of the 'recurrences'. 428 The 'recurrences' must be UTC datetimes corresponding to the start of 429 the period described by a recurrence. 430 """ 431 432 for recurrence in recurrences: 433 if self.is_affected(recurrence): 434 return True 435 return False 436 437 def is_affected(self, recurrence): 438 439 """ 440 Return whether this period refers to 'recurrence'. The 'recurrence' must 441 be a UTC datetime corresponding to the start of the period described by 442 a recurrence. 443 """ 444 445 return recurrence and self.get_start_point() == recurrence 446 447 # Value correction methods. 448 449 def make_corrected(self, start, end): 450 return self.__class__(start, end) 451 452 class FreeBusyOfferPeriod(FreeBusyPeriod): 453 454 "A free/busy record abstraction for an offer period." 455 456 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, 457 summary=None, organiser=None, expires=None): 458 459 """ 460 Initialise a free/busy period with the given 'start' and 'end' points, 461 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 462 details. 463 464 An additional 'expires' parameter can be used to indicate an expiry 465 datetime in conjunction with free/busy offers made when countering 466 event proposals. 467 """ 468 469 FreeBusyPeriod.__init__(self, start, end, uid, transp, recurrenceid, 470 summary, organiser) 471 self.expires = expires or None 472 473 def as_tuple(self, strings_only=False, string_datetimes=False): 474 475 """ 476 Return the initialisation parameter tuple, converting datetimes and 477 false value parameters to strings if 'strings_only' is set to a true 478 value. Otherwise, if 'string_datetimes' is set to a true value, only the 479 datetime values are converted to strings. 480 """ 481 482 null = lambda x: (strings_only and [""] or [x])[0] 483 return FreeBusyPeriod.as_tuple(self, strings_only, string_datetimes) + ( 484 self.expires or null(self.expires),) 485 486 def __repr__(self): 487 return "FreeBusyOfferPeriod%r" % (self.as_tuple(),) 488 489 class FreeBusyGroupPeriod(FreeBusyPeriod): 490 491 "A free/busy record abstraction for a quota group period." 492 493 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, 494 summary=None, organiser=None, attendee=None): 495 496 """ 497 Initialise a free/busy period with the given 'start' and 'end' points, 498 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 499 details. 500 501 An additional 'attendee' parameter can be used to indicate the identity 502 of the attendee recording the period. 503 """ 504 505 FreeBusyPeriod.__init__(self, start, end, uid, transp, recurrenceid, 506 summary, organiser) 507 self.attendee = attendee or None 508 509 def as_tuple(self, strings_only=False, string_datetimes=False): 510 511 """ 512 Return the initialisation parameter tuple, converting datetimes and 513 false value parameters to strings if 'strings_only' is set to a true 514 value. Otherwise, if 'string_datetimes' is set to a true value, only the 515 datetime values are converted to strings. 516 """ 517 518 null = lambda x: (strings_only and [""] or [x])[0] 519 return FreeBusyPeriod.as_tuple(self, strings_only, string_datetimes) + ( 520 self.attendee or null(self.attendee),) 521 522 def __cmp__(self, other): 523 524 """ 525 Compare this object to 'other', employing the uid if the periods 526 involved are the same. 527 """ 528 529 result = FreeBusyPeriod.__cmp__(self, other) 530 if isinstance(other, FreeBusyGroupPeriod) and result == 0: 531 return cmp(self.attendee, other.attendee) 532 else: 533 return result 534 535 def __repr__(self): 536 return "FreeBusyGroupPeriod%r" % (self.as_tuple(),) 537 538 class RecurringPeriod(Period): 539 540 """ 541 A period with iCalendar metadata attributes and origin information from an 542 object. 543 """ 544 545 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 546 Period.__init__(self, start, end, tzid, origin) 547 self.start_attr = start_attr 548 self.end_attr = end_attr 549 550 def get_start_attr(self): 551 return self.start_attr 552 553 def get_end_attr(self): 554 return self.end_attr 555 556 def as_tuple(self): 557 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 558 559 def __repr__(self): 560 return "RecurringPeriod%r" % (self.as_tuple(),) 561 562 def make_corrected(self, start, end): 563 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 564 565 class FreeBusyCollectionBase: 566 567 "Common operations on free/busy period collections." 568 569 period_columns = [ 570 "start", "end", "object_uid", "transp", "object_recurrenceid", 571 "summary", "organiser" 572 ] 573 574 period_class = FreeBusyPeriod 575 576 def __init__(self, mutable=True): 577 self.mutable = mutable 578 579 def _check_mutable(self): 580 if not self.mutable: 581 raise TypeError, "Cannot mutate this collection." 582 583 def copy(self): 584 585 "Make an independent mutable copy of the collection." 586 587 return FreeBusyCollection(list(self), True) 588 589 def make_period(self, t): 590 591 """ 592 Make a period using the given tuple of arguments and the collection's 593 column details. 594 """ 595 596 args = [] 597 for arg, column in zip(t, self.period_columns): 598 args.append(from_string(arg, "utf-8")) 599 return self.period_class(*args) 600 601 def make_tuple(self, t): 602 603 """ 604 Return a tuple from the given tuple 't' conforming to the collection's 605 column details. 606 """ 607 608 args = [] 609 for arg, column in zip(t, self.period_columns): 610 args.append(arg) 611 return tuple(args) 612 613 # List emulation methods. 614 615 def __iadd__(self, periods): 616 for period in periods: 617 self.insert_period(period) 618 return self 619 620 def append(self, period): 621 self.insert_period(period) 622 623 # Operations. 624 625 def can_schedule(self, periods, uid, recurrenceid): 626 627 """ 628 Return whether the collection can accommodate the given 'periods' 629 employing the specified 'uid' and 'recurrenceid'. 630 """ 631 632 for conflict in self.have_conflict(periods, True): 633 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 634 return False 635 636 return True 637 638 def have_conflict(self, periods, get_conflicts=False): 639 640 """ 641 Return whether any period in the collection overlaps with the given 642 'periods', returning a collection of such overlapping periods if 643 'get_conflicts' is set to a true value. 644 """ 645 646 conflicts = set() 647 for p in periods: 648 overlapping = self.period_overlaps(p, get_conflicts) 649 if overlapping: 650 if get_conflicts: 651 conflicts.update(overlapping) 652 else: 653 return True 654 655 if get_conflicts: 656 return conflicts 657 else: 658 return False 659 660 def period_overlaps(self, period, get_periods=False): 661 662 """ 663 Return whether any period in the collection overlaps with the given 664 'period', returning a collection of overlapping periods if 'get_periods' 665 is set to a true value. 666 """ 667 668 overlapping = self.get_overlapping([period]) 669 670 if get_periods: 671 return overlapping 672 else: 673 return len(overlapping) != 0 674 675 def replace_overlapping(self, period, replacements): 676 677 """ 678 Replace existing periods in the collection within the given 'period', 679 using the given 'replacements'. 680 """ 681 682 self._check_mutable() 683 684 self.remove_overlapping(period) 685 for replacement in replacements: 686 self.insert_period(replacement) 687 688 def coalesce_freebusy(self): 689 690 "Coalesce the periods in the collection, returning a new collection." 691 692 if not self: 693 return FreeBusyCollection() 694 695 fb = [] 696 697 it = iter(self) 698 period = it.next() 699 700 start = period.get_start_point() 701 end = period.get_end_point() 702 703 try: 704 while True: 705 period = it.next() 706 if period.get_start_point() > end: 707 fb.append(self.period_class(start, end)) 708 start = period.get_start_point() 709 end = period.get_end_point() 710 else: 711 end = max(end, period.get_end_point()) 712 except StopIteration: 713 pass 714 715 fb.append(self.period_class(start, end)) 716 return FreeBusyCollection(fb) 717 718 def invert_freebusy(self): 719 720 "Return the free periods from the collection as a new collection." 721 722 if not self: 723 return FreeBusyCollection([self.period_class(None, None)]) 724 725 # Coalesce periods that overlap or are adjacent. 726 727 fb = self.coalesce_freebusy() 728 free = [] 729 730 # Add a start-of-time period if appropriate. 731 732 first = fb[0].get_start_point() 733 if first: 734 free.append(self.period_class(None, first)) 735 736 start = fb[0].get_end_point() 737 738 for period in fb[1:]: 739 free.append(self.period_class(start, period.get_start_point())) 740 start = period.get_end_point() 741 742 # Add an end-of-time period if appropriate. 743 744 if start: 745 free.append(self.period_class(start, None)) 746 747 return FreeBusyCollection(free) 748 749 def _update_freebusy(self, periods, uid, recurrenceid): 750 751 """ 752 Update the free/busy details with the given 'periods', using the given 753 'uid' plus 'recurrenceid' to remove existing periods. 754 """ 755 756 self._check_mutable() 757 758 self.remove_specific_event_periods(uid, recurrenceid) 759 760 for p in periods: 761 self.insert_period(p) 762 763 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser): 764 765 """ 766 Update the free/busy details with the given 'periods', 'transp' setting, 767 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 768 """ 769 770 new_periods = [] 771 772 for p in periods: 773 new_periods.append( 774 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser) 775 ) 776 777 self._update_freebusy(new_periods, uid, recurrenceid) 778 779 class SupportAttendee: 780 781 "A mix-in that supports the affected attendee in free/busy periods." 782 783 period_columns = FreeBusyCollectionBase.period_columns + ["attendee"] 784 period_class = FreeBusyGroupPeriod 785 786 def _update_freebusy(self, periods, uid, recurrenceid, attendee=None): 787 788 """ 789 Update the free/busy details with the given 'periods', using the given 790 'uid' plus 'recurrenceid' and 'attendee' to remove existing periods. 791 """ 792 793 self._check_mutable() 794 795 self.remove_specific_event_periods(uid, recurrenceid, attendee) 796 797 for p in periods: 798 self.insert_period(p) 799 800 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, attendee=None): 801 802 """ 803 Update the free/busy details with the given 'periods', 'transp' setting, 804 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 805 806 An optional 'attendee' indicates the attendee affected by the period. 807 """ 808 809 new_periods = [] 810 811 for p in periods: 812 new_periods.append( 813 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, attendee) 814 ) 815 816 self._update_freebusy(new_periods, uid, recurrenceid, attendee) 817 818 class SupportExpires: 819 820 "A mix-in that supports the expiry datetime in free/busy periods." 821 822 period_columns = FreeBusyCollectionBase.period_columns + ["expires"] 823 period_class = FreeBusyOfferPeriod 824 825 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 826 827 """ 828 Update the free/busy details with the given 'periods', 'transp' setting, 829 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 830 831 An optional 'expires' datetime string indicates the expiry time of any 832 free/busy offer. 833 """ 834 835 new_periods = [] 836 837 for p in periods: 838 new_periods.append( 839 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires) 840 ) 841 842 self._update_freebusy(new_periods, uid, recurrenceid) 843 844 class FreeBusyCollection(FreeBusyCollectionBase): 845 846 "An abstraction for a collection of free/busy periods." 847 848 def __init__(self, periods=None, mutable=True): 849 850 """ 851 Initialise the collection with the given list of 'periods', or start an 852 empty collection if no list is given. If 'mutable' is indicated, the 853 collection may be changed; otherwise, an exception will be raised. 854 """ 855 856 FreeBusyCollectionBase.__init__(self, mutable) 857 self.periods = periods or [] 858 859 # List emulation methods. 860 861 def __nonzero__(self): 862 return bool(self.periods) 863 864 def __iter__(self): 865 return iter(self.periods) 866 867 def __len__(self): 868 return len(self.periods) 869 870 def __getitem__(self, i): 871 return self.periods[i] 872 873 # Operations. 874 875 def insert_period(self, period): 876 877 "Insert the given 'period' into the collection." 878 879 self._check_mutable() 880 881 i = bisect_left(self.periods, period) 882 if i == len(self.periods): 883 self.periods.append(period) 884 elif self.periods[i] != period: 885 self.periods.insert(i, period) 886 887 def remove_periods(self, periods): 888 889 "Remove the given 'periods' from the collection." 890 891 self._check_mutable() 892 893 for period in periods: 894 i = bisect_left(self.periods, period) 895 if i < len(self.periods) and self.periods[i] == period: 896 del self.periods[i] 897 898 def remove_event_periods(self, uid, recurrenceid=None): 899 900 """ 901 Remove from the collection all periods associated with 'uid' and 902 'recurrenceid' (which if omitted causes the "parent" object's periods to 903 be referenced). 904 905 Return the removed periods. 906 """ 907 908 self._check_mutable() 909 910 removed = [] 911 i = 0 912 while i < len(self.periods): 913 fb = self.periods[i] 914 if fb.uid == uid and fb.recurrenceid == recurrenceid: 915 removed.append(self.periods[i]) 916 del self.periods[i] 917 else: 918 i += 1 919 920 return removed 921 922 # Specific period removal when updating event details. 923 924 remove_specific_event_periods = remove_event_periods 925 926 def remove_additional_periods(self, uid, recurrenceids=None): 927 928 """ 929 Remove from the collection all periods associated with 'uid' having a 930 recurrence identifier indicating an additional or modified period. 931 932 If 'recurrenceids' is specified, remove all periods associated with 933 'uid' that do not have a recurrence identifier in the given list. 934 935 Return the removed periods. 936 """ 937 938 self._check_mutable() 939 940 removed = [] 941 i = 0 942 while i < len(self.periods): 943 fb = self.periods[i] 944 if fb.uid == uid and fb.recurrenceid and ( 945 recurrenceids is None or 946 recurrenceids is not None and fb.recurrenceid not in recurrenceids 947 ): 948 removed.append(self.periods[i]) 949 del self.periods[i] 950 else: 951 i += 1 952 953 return removed 954 955 def remove_affected_period(self, uid, start): 956 957 """ 958 Remove from the collection the period associated with 'uid' that 959 provides an occurrence starting at the given 'start' (provided by a 960 recurrence identifier, converted to a datetime). A recurrence identifier 961 is used to provide an alternative time period whilst also acting as a 962 reference to the originally-defined occurrence. 963 964 Return any removed period in a list. 965 """ 966 967 self._check_mutable() 968 969 removed = [] 970 971 search = Period(start, start) 972 found = bisect_left(self.periods, search) 973 974 while found < len(self.periods): 975 fb = self.periods[found] 976 977 # Stop looking if the start no longer matches the recurrence identifier. 978 979 if fb.get_start_point() != search.get_start_point(): 980 break 981 982 # If the period belongs to the parent object, remove it and return. 983 984 if not fb.recurrenceid and uid == fb.uid: 985 removed.append(self.periods[found]) 986 del self.periods[found] 987 break 988 989 # Otherwise, keep looking for a matching period. 990 991 found += 1 992 993 return removed 994 995 def periods_from(self, period): 996 997 "Return the entries in the collection at or after 'period'." 998 999 first = bisect_left(self.periods, period) 1000 return self.periods[first:] 1001 1002 def periods_until(self, period): 1003 1004 "Return the entries in the collection before 'period'." 1005 1006 last = bisect_right(self.periods, Period(period.get_end(), period.get_end(), period.get_tzid())) 1007 return self.periods[:last] 1008 1009 def get_overlapping(self, periods): 1010 1011 """ 1012 Return the entries in the collection providing periods overlapping with 1013 the given sorted collection of 'periods'. 1014 """ 1015 1016 return get_overlapping(self.periods, periods) 1017 1018 def remove_overlapping(self, period): 1019 1020 "Remove all periods overlapping with 'period' from the collection." 1021 1022 self._check_mutable() 1023 1024 overlapping = self.get_overlapping([period]) 1025 1026 if overlapping: 1027 for fb in overlapping: 1028 self.periods.remove(fb) 1029 1030 class FreeBusyGroupCollection(SupportAttendee, FreeBusyCollection): 1031 1032 "A collection of quota group free/busy objects." 1033 1034 def remove_specific_event_periods(self, uid, recurrenceid=None, attendee=None): 1035 1036 """ 1037 Remove from the collection all periods associated with 'uid' and 1038 'recurrenceid' (which if omitted causes the "parent" object's periods to 1039 be referenced) and any 'attendee'. 1040 1041 Return the removed periods. 1042 """ 1043 1044 self._check_mutable() 1045 1046 removed = [] 1047 i = 0 1048 while i < len(self.periods): 1049 fb = self.periods[i] 1050 if fb.uid == uid and fb.recurrenceid == recurrenceid and fb.attendee == attendee: 1051 removed.append(self.periods[i]) 1052 del self.periods[i] 1053 else: 1054 i += 1 1055 1056 return removed 1057 1058 class FreeBusyOffersCollection(SupportExpires, FreeBusyCollection): 1059 1060 "A collection of offered free/busy objects." 1061 1062 pass 1063 1064 class FreeBusyDatabaseCollection(FreeBusyCollectionBase, DatabaseOperations): 1065 1066 """ 1067 An abstraction for a collection of free/busy periods stored in a database 1068 system. 1069 """ 1070 1071 def __init__(self, cursor, table_name, column_names=None, filter_values=None, 1072 mutable=True, paramstyle=None): 1073 1074 """ 1075 Initialise the collection with the given 'cursor' and with the 1076 'table_name', 'column_names' and 'filter_values' configuring the 1077 selection of data. If 'mutable' is indicated, the collection may be 1078 changed; otherwise, an exception will be raised. 1079 """ 1080 1081 FreeBusyCollectionBase.__init__(self, mutable) 1082 DatabaseOperations.__init__(self, column_names, filter_values, paramstyle) 1083 self.cursor = cursor 1084 self.table_name = table_name 1085 1086 # List emulation methods. 1087 1088 def __nonzero__(self): 1089 return len(self) and True or False 1090 1091 def __iter__(self): 1092 query, values = self.get_query( 1093 "select %(columns)s from %(table)s :condition" % { 1094 "columns" : self.columnlist(self.period_columns), 1095 "table" : self.table_name 1096 }) 1097 self.cursor.execute(query, values) 1098 return iter(map(lambda t: self.make_period(t), self.cursor.fetchall())) 1099 1100 def __len__(self): 1101 query, values = self.get_query( 1102 "select count(*) from %(table)s :condition" % { 1103 "table" : self.table_name 1104 }) 1105 self.cursor.execute(query, values) 1106 result = self.cursor.fetchone() 1107 return result and int(result[0]) or 0 1108 1109 def __getitem__(self, i): 1110 return list(iter(self))[i] 1111 1112 # Operations. 1113 1114 def insert_period(self, period): 1115 1116 "Insert the given 'period' into the collection." 1117 1118 self._check_mutable() 1119 1120 columns, values = self.period_columns, period.as_tuple(string_datetimes=True) 1121 1122 query, values = self.get_query( 1123 "insert into %(table)s (:columns) values (:values)" % { 1124 "table" : self.table_name 1125 }, 1126 columns, [to_string(v, "utf-8") for v in values]) 1127 1128 self.cursor.execute(query, values) 1129 1130 def remove_periods(self, periods): 1131 1132 "Remove the given 'periods' from the collection." 1133 1134 self._check_mutable() 1135 1136 for period in periods: 1137 values = period.as_tuple(string_datetimes=True) 1138 1139 query, values = self.get_query( 1140 "delete from %(table)s :condition" % { 1141 "table" : self.table_name 1142 }, 1143 self.period_columns, [to_string(v, "utf-8") for v in values]) 1144 1145 self.cursor.execute(query, values) 1146 1147 def remove_event_periods(self, uid, recurrenceid=None): 1148 1149 """ 1150 Remove from the collection all periods associated with 'uid' and 1151 'recurrenceid' (which if omitted causes the "parent" object's periods to 1152 be referenced). 1153 1154 Return the removed periods. 1155 """ 1156 1157 self._check_mutable() 1158 1159 if recurrenceid: 1160 columns, values = ["object_uid", "object_recurrenceid"], [uid, recurrenceid] 1161 else: 1162 columns, values = ["object_uid", "object_recurrenceid is null"], [uid] 1163 1164 query, _values = self.get_query( 1165 "select %(columns)s from %(table)s :condition" % { 1166 "columns" : self.columnlist(self.period_columns), 1167 "table" : self.table_name 1168 }, 1169 columns, values) 1170 1171 self.cursor.execute(query, _values) 1172 removed = self.cursor.fetchall() 1173 1174 query, values = self.get_query( 1175 "delete from %(table)s :condition" % { 1176 "table" : self.table_name 1177 }, 1178 columns, values) 1179 1180 self.cursor.execute(query, values) 1181 1182 return map(lambda t: self.make_period(t), removed) 1183 1184 # Specific period removal when updating event details. 1185 1186 remove_specific_event_periods = remove_event_periods 1187 1188 def remove_additional_periods(self, uid, recurrenceids=None): 1189 1190 """ 1191 Remove from the collection all periods associated with 'uid' having a 1192 recurrence identifier indicating an additional or modified period. 1193 1194 If 'recurrenceids' is specified, remove all periods associated with 1195 'uid' that do not have a recurrence identifier in the given list. 1196 1197 Return the removed periods. 1198 """ 1199 1200 self._check_mutable() 1201 1202 if not recurrenceids: 1203 columns, values = ["object_uid", "object_recurrenceid is not null"], [uid] 1204 else: 1205 columns, values = ["object_uid", "object_recurrenceid not in ?", "object_recurrenceid is not null"], [uid, tuple(recurrenceids)] 1206 1207 query, _values = self.get_query( 1208 "select %(columns)s from %(table)s :condition" % { 1209 "columns" : self.columnlist(self.period_columns), 1210 "table" : self.table_name 1211 }, 1212 columns, values) 1213 1214 self.cursor.execute(query, _values) 1215 removed = self.cursor.fetchall() 1216 1217 query, values = self.get_query( 1218 "delete from %(table)s :condition" % { 1219 "table" : self.table_name 1220 }, 1221 columns, values) 1222 1223 self.cursor.execute(query, values) 1224 1225 return map(lambda t: self.make_period(t), removed) 1226 1227 def remove_affected_period(self, uid, start): 1228 1229 """ 1230 Remove from the collection the period associated with 'uid' that 1231 provides an occurrence starting at the given 'start' (provided by a 1232 recurrence identifier, converted to a datetime). A recurrence identifier 1233 is used to provide an alternative time period whilst also acting as a 1234 reference to the originally-defined occurrence. 1235 1236 Return any removed period in a list. 1237 """ 1238 1239 self._check_mutable() 1240 1241 start = format_datetime(start) 1242 1243 columns, values = ["object_uid", "start", "object_recurrenceid is null"], [uid, start] 1244 1245 query, _values = self.get_query( 1246 "select %(columns)s from %(table)s :condition" % { 1247 "columns" : self.columnlist(self.period_columns), 1248 "table" : self.table_name 1249 }, 1250 columns, values) 1251 1252 self.cursor.execute(query, _values) 1253 removed = self.cursor.fetchall() 1254 1255 query, values = self.get_query( 1256 "delete from %(table)s :condition" % { 1257 "table" : self.table_name 1258 }, 1259 columns, values) 1260 1261 self.cursor.execute(query, values) 1262 1263 return map(lambda t: self.make_period(t), removed) 1264 1265 def periods_from(self, period): 1266 1267 "Return the entries in the collection at or after 'period'." 1268 1269 start = format_datetime(period.get_start_point()) 1270 1271 columns, values = [], [] 1272 1273 if start: 1274 columns.append("start >= ?") 1275 values.append(start) 1276 1277 query, values = self.get_query( 1278 "select %(columns)s from %(table)s :condition" % { 1279 "columns" : self.columnlist(self.period_columns), 1280 "table" : self.table_name 1281 }, 1282 columns, values) 1283 1284 self.cursor.execute(query, values) 1285 1286 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1287 1288 def periods_until(self, period): 1289 1290 "Return the entries in the collection before 'period'." 1291 1292 end = format_datetime(period.get_end_point()) 1293 1294 columns, values = [], [] 1295 1296 if end: 1297 columns.append("start < ?") 1298 values.append(end) 1299 1300 query, values = self.get_query( 1301 "select %(columns)s from %(table)s :condition" % { 1302 "columns" : self.columnlist(self.period_columns), 1303 "table" : self.table_name 1304 }, 1305 columns, values) 1306 1307 self.cursor.execute(query, values) 1308 1309 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1310 1311 def get_overlapping(self, periods): 1312 1313 """ 1314 Return the entries in the collection providing periods overlapping with 1315 the given sorted collection of 'periods'. 1316 """ 1317 1318 overlapping = set() 1319 1320 for period in periods: 1321 columns, values = self._get_period_values(period) 1322 1323 query, values = self.get_query( 1324 "select %(columns)s from %(table)s :condition" % { 1325 "columns" : self.columnlist(self.period_columns), 1326 "table" : self.table_name 1327 }, 1328 columns, values) 1329 1330 self.cursor.execute(query, values) 1331 1332 overlapping.update(map(lambda t: self.make_period(t), self.cursor.fetchall())) 1333 1334 overlapping = list(overlapping) 1335 overlapping.sort() 1336 return overlapping 1337 1338 def remove_overlapping(self, period): 1339 1340 "Remove all periods overlapping with 'period' from the collection." 1341 1342 self._check_mutable() 1343 1344 columns, values = self._get_period_values(period) 1345 1346 query, values = self.get_query( 1347 "delete from %(table)s :condition" % { 1348 "table" : self.table_name 1349 }, 1350 columns, values) 1351 1352 self.cursor.execute(query, values) 1353 1354 def _get_period_values(self, period): 1355 1356 start = format_datetime(period.get_start_point()) 1357 end = format_datetime(period.get_end_point()) 1358 1359 columns, values = [], [] 1360 1361 if end: 1362 columns.append("start < ?") 1363 values.append(end) 1364 if start: 1365 columns.append("end > ?") 1366 values.append(start) 1367 1368 return columns, values 1369 1370 class FreeBusyGroupDatabaseCollection(SupportAttendee, FreeBusyDatabaseCollection): 1371 1372 "A collection of quota group free/busy objects." 1373 1374 def remove_specific_event_periods(self, uid, recurrenceid=None, attendee=None): 1375 1376 """ 1377 Remove from the collection all periods associated with 'uid' and 1378 'recurrenceid' (which if omitted causes the "parent" object's periods to 1379 be referenced) and any 'attendee'. 1380 1381 Return the removed periods. 1382 """ 1383 1384 self._check_mutable() 1385 1386 columns, values = ["object_uid"], [uid] 1387 1388 if recurrenceid: 1389 columns.append("object_recurrenceid") 1390 values.append(recurrenceid) 1391 else: 1392 columns.append("object_recurrenceid is null") 1393 1394 if attendee: 1395 columns.append("attendee") 1396 values.append(attendee) 1397 else: 1398 columns.append("attendee is null") 1399 1400 query, _values = self.get_query( 1401 "select %(columns)s from %(table)s :condition" % { 1402 "columns" : self.columnlist(self.period_columns), 1403 "table" : self.table_name 1404 }, 1405 columns, values) 1406 1407 self.cursor.execute(query, _values) 1408 removed = self.cursor.fetchall() 1409 1410 query, values = self.get_query( 1411 "delete from %(table)s :condition" % { 1412 "table" : self.table_name 1413 }, 1414 columns, values) 1415 1416 self.cursor.execute(query, values) 1417 1418 return map(lambda t: self.make_period(t), removed) 1419 1420 class FreeBusyOffersDatabaseCollection(SupportExpires, FreeBusyDatabaseCollection): 1421 1422 "A collection of offered free/busy objects." 1423 1424 pass 1425 1426 def get_overlapping(first, second): 1427 1428 """ 1429 Return the entries in the sorted 'first' collection that are overlapping 1430 with the given sorted 'second' collection. 1431 """ 1432 1433 if not first or not second: 1434 return [] 1435 1436 # Examine each period in the second collection, attempting to match periods 1437 # in the first collection. 1438 1439 overlapping = set() 1440 1441 for p2 in second: 1442 last_point = p2.get_end_point() 1443 1444 # Examine the first collection up to the point where no matches will 1445 # occur. 1446 1447 for p1 in first: 1448 if p1.get_start_point() > last_point: 1449 break 1450 elif p1.overlaps(p2): 1451 overlapping.add(p1) 1452 1453 overlapping = list(overlapping) 1454 overlapping.sort() 1455 return overlapping 1456 1457 # Period layout. 1458 1459 def get_scale(periods, tzid, view_period=None): 1460 1461 """ 1462 Return a time scale from the given list of 'periods'. 1463 1464 The given 'tzid' is used to make sure that the times are defined according 1465 to the chosen time zone. 1466 1467 An optional 'view_period' is used to constrain the scale to the given 1468 period. 1469 1470 The returned scale is a mapping from time to (starting, ending) tuples, 1471 where starting and ending are collections of periods. 1472 """ 1473 1474 scale = {} 1475 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 1476 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 1477 1478 for p in periods: 1479 1480 # Add a point and this event to the starting list. 1481 1482 start = to_timezone(p.get_start(), tzid) 1483 start = view_start and max(start, view_start) or start 1484 if not scale.has_key(start): 1485 scale[start] = [], [] 1486 scale[start][0].append(p) 1487 1488 # Add a point and this event to the ending list. 1489 1490 end = to_timezone(p.get_end(), tzid) 1491 end = view_end and min(end, view_end) or end 1492 if not scale.has_key(end): 1493 scale[end] = [], [] 1494 scale[end][1].append(p) 1495 1496 return scale 1497 1498 class Point: 1499 1500 "A qualified point in time." 1501 1502 PRINCIPAL, REPEATED = 0, 1 1503 1504 def __init__(self, point, indicator=None): 1505 self.point = point 1506 self.indicator = indicator or self.PRINCIPAL 1507 1508 def __hash__(self): 1509 return hash((self.point, self.indicator)) 1510 1511 def __cmp__(self, other): 1512 if isinstance(other, Point): 1513 return cmp((self.point, self.indicator), (other.point, other.indicator)) 1514 elif isinstance(other, datetime): 1515 return cmp(self.point, other) 1516 else: 1517 return 1 1518 1519 def __eq__(self, other): 1520 return self.__cmp__(other) == 0 1521 1522 def __ne__(self, other): 1523 return not self == other 1524 1525 def __lt__(self, other): 1526 return self.__cmp__(other) < 0 1527 1528 def __le__(self, other): 1529 return self.__cmp__(other) <= 0 1530 1531 def __gt__(self, other): 1532 return not self <= other 1533 1534 def __ge__(self, other): 1535 return not self < other 1536 1537 def __repr__(self): 1538 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 1539 1540 def get_slots(scale): 1541 1542 """ 1543 Return an ordered list of time slots from the given 'scale'. 1544 1545 Each slot is a tuple containing details of a point in time for the start of 1546 the slot, together with a list of parallel event periods. 1547 1548 Each point in time is described as a Point representing the actual point in 1549 time together with an indicator of the nature of the point in time (as a 1550 principal point in a time scale or as a repeated point used to terminate 1551 events occurring for an instant in time). 1552 """ 1553 1554 slots = [] 1555 active = [] 1556 1557 points = scale.items() 1558 points.sort() 1559 1560 for point, (starting, ending) in points: 1561 ending = set(ending) 1562 instants = ending.intersection(starting) 1563 1564 # Discard all active events ending at or before this start time. 1565 # Free up the position in the active list. 1566 1567 for t in ending.difference(instants): 1568 i = active.index(t) 1569 active[i] = None 1570 1571 # For each event starting at the current point, fill any newly-vacated 1572 # position or add to the end of the active list. 1573 1574 for t in starting: 1575 try: 1576 i = active.index(None) 1577 active[i] = t 1578 except ValueError: 1579 active.append(t) 1580 1581 # Discard vacant positions from the end of the active list. 1582 1583 while active and active[-1] is None: 1584 active.pop() 1585 1586 # Add an entry for the time point before "instants". 1587 1588 slots.append((Point(point), active[:])) 1589 1590 # Discard events ending at the same time as they began. 1591 1592 if instants: 1593 for t in instants: 1594 i = active.index(t) 1595 active[i] = None 1596 1597 # Discard vacant positions from the end of the active list. 1598 1599 while active and active[-1] is None: 1600 active.pop() 1601 1602 # Add another entry for the time point after "instants". 1603 1604 slots.append((Point(point, Point.REPEATED), active[:])) 1605 1606 return slots 1607 1608 def add_day_start_points(slots, tzid): 1609 1610 """ 1611 Introduce into the 'slots' any day start points required by multi-day 1612 periods. The 'tzid' is required to make sure that appropriate time zones 1613 are chosen and not necessarily those provided by the existing time points. 1614 """ 1615 1616 new_slots = [] 1617 current_date = None 1618 previously_active = [] 1619 1620 for point, active in slots: 1621 start_of_day = get_start_of_day(point.point, tzid) 1622 this_date = point.point.date() 1623 1624 # For each new day, add a slot for the start of the day where periods 1625 # are active and where no such slot already exists. 1626 1627 if this_date != current_date: 1628 1629 # Fill in days where events remain active. 1630 1631 if current_date: 1632 current_date += timedelta(1) 1633 while current_date < this_date: 1634 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 1635 current_date += timedelta(1) 1636 else: 1637 current_date = this_date 1638 1639 # Add any continuing periods. 1640 1641 if point.point != start_of_day: 1642 new_slots.append((Point(start_of_day), previously_active)) 1643 1644 # Add the currently active periods at this point in time. 1645 1646 previously_active = active 1647 1648 for t in new_slots: 1649 insort_left(slots, t) 1650 1651 def remove_end_slot(slots, view_period): 1652 1653 """ 1654 Remove from 'slots' any slot situated at the end of the given 'view_period'. 1655 """ 1656 1657 end = view_period.get_end_point() 1658 if not end or not slots: 1659 return 1660 i = bisect_left(slots, (Point(end), None)) 1661 if i < len(slots): 1662 del slots[i:] 1663 1664 def add_slots(slots, points): 1665 1666 """ 1667 Introduce into the 'slots' entries for those in 'points' that are not 1668 already present, propagating active periods from time points preceding 1669 those added. 1670 """ 1671 1672 new_slots = [] 1673 1674 for point in points: 1675 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 1676 if i < len(slots) and slots[i][0] == point: 1677 continue 1678 1679 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 1680 1681 for t in new_slots: 1682 insort_left(slots, t) 1683 1684 def partition_by_day(slots): 1685 1686 """ 1687 Return a mapping from dates to time points provided by 'slots'. 1688 """ 1689 1690 d = {} 1691 1692 for point, value in slots: 1693 day = point.point.date() 1694 if not d.has_key(day): 1695 d[day] = [] 1696 d[day].append((point, value)) 1697 1698 return d 1699 1700 def add_empty_days(days, tzid, start=None, end=None): 1701 1702 """ 1703 Add empty days to 'days' between busy days, and optionally from the given 1704 'start' day and until the given 'end' day. 1705 """ 1706 1707 last_day = start - timedelta(1) 1708 all_days = days.keys() 1709 all_days.sort() 1710 1711 for day in all_days: 1712 if last_day: 1713 empty_day = last_day + timedelta(1) 1714 while empty_day < day: 1715 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1716 empty_day += timedelta(1) 1717 last_day = day 1718 1719 if end: 1720 empty_day = last_day + timedelta(1) 1721 while empty_day < end: 1722 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1723 empty_day += timedelta(1) 1724 1725 def get_spans(slots): 1726 1727 "Inspect the given 'slots', returning a mapping of period keys to spans." 1728 1729 points = [point for point, active in slots] 1730 spans = {} 1731 1732 for _point, active in slots: 1733 for p in active: 1734 if p: 1735 key = p.get_key() 1736 start_slot = bisect_left(points, p.get_start()) 1737 end_slot = bisect_left(points, p.get_end()) 1738 spans[key] = end_slot - start_slot 1739 1740 return spans 1741 1742 # vim: tabstop=4 expandtab shiftwidth=4