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, period): 1010 1011 """ 1012 Return the entries in the collection providing periods overlapping with 1013 'period'. 1014 """ 1015 1016 # Find the range of periods potentially overlapping the period in the 1017 # free/busy collection. 1018 1019 startpoints = self.periods_until(period) 1020 1021 # Find the range of periods potentially overlapping the period in a version 1022 # of the free/busy collection sorted according to end datetimes. 1023 1024 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 1025 endpoints.sort() 1026 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 1027 endpoints = endpoints[first:] 1028 1029 overlapping = set() 1030 1031 for p, fb in endpoints: 1032 if fb.overlaps(period): 1033 overlapping.add(fb) 1034 1035 overlapping = list(overlapping) 1036 overlapping.sort() 1037 return overlapping 1038 1039 def remove_overlapping(self, period): 1040 1041 "Remove all periods overlapping with 'period' from the collection." 1042 1043 self._check_mutable() 1044 1045 overlapping = self.get_overlapping(period) 1046 1047 if overlapping: 1048 for fb in overlapping: 1049 self.periods.remove(fb) 1050 1051 class FreeBusyGroupCollection(SupportAttendee, FreeBusyCollection): 1052 1053 "A collection of quota group free/busy objects." 1054 1055 def remove_specific_event_periods(self, uid, recurrenceid=None, attendee=None): 1056 1057 """ 1058 Remove from the collection all periods associated with 'uid' and 1059 'recurrenceid' (which if omitted causes the "parent" object's periods to 1060 be referenced) and any 'attendee'. 1061 1062 Return the removed periods. 1063 """ 1064 1065 self._check_mutable() 1066 1067 removed = [] 1068 i = 0 1069 while i < len(self.periods): 1070 fb = self.periods[i] 1071 if fb.uid == uid and fb.recurrenceid == recurrenceid and fb.attendee == attendee: 1072 removed.append(self.periods[i]) 1073 del self.periods[i] 1074 else: 1075 i += 1 1076 1077 return removed 1078 1079 class FreeBusyOffersCollection(SupportExpires, FreeBusyCollection): 1080 1081 "A collection of offered free/busy objects." 1082 1083 pass 1084 1085 class FreeBusyDatabaseCollection(FreeBusyCollectionBase, DatabaseOperations): 1086 1087 """ 1088 An abstraction for a collection of free/busy periods stored in a database 1089 system. 1090 """ 1091 1092 def __init__(self, cursor, table_name, column_names=None, filter_values=None, 1093 mutable=True, paramstyle=None): 1094 1095 """ 1096 Initialise the collection with the given 'cursor' and with the 1097 'table_name', 'column_names' and 'filter_values' configuring the 1098 selection of data. If 'mutable' is indicated, the collection may be 1099 changed; otherwise, an exception will be raised. 1100 """ 1101 1102 FreeBusyCollectionBase.__init__(self, mutable) 1103 DatabaseOperations.__init__(self, column_names, filter_values, paramstyle) 1104 self.cursor = cursor 1105 self.table_name = table_name 1106 1107 # List emulation methods. 1108 1109 def __nonzero__(self): 1110 return len(self) and True or False 1111 1112 def __iter__(self): 1113 query, values = self.get_query( 1114 "select %(columns)s from %(table)s :condition" % { 1115 "columns" : self.columnlist(self.period_columns), 1116 "table" : self.table_name 1117 }) 1118 self.cursor.execute(query, values) 1119 return iter(map(lambda t: self.make_period(t), self.cursor.fetchall())) 1120 1121 def __len__(self): 1122 query, values = self.get_query( 1123 "select count(*) from %(table)s :condition" % { 1124 "table" : self.table_name 1125 }) 1126 self.cursor.execute(query, values) 1127 result = self.cursor.fetchone() 1128 return result and int(result[0]) or 0 1129 1130 def __getitem__(self, i): 1131 return list(iter(self))[i] 1132 1133 # Operations. 1134 1135 def insert_period(self, period): 1136 1137 "Insert the given 'period' into the collection." 1138 1139 self._check_mutable() 1140 1141 columns, values = self.period_columns, period.as_tuple(string_datetimes=True) 1142 1143 query, values = self.get_query( 1144 "insert into %(table)s (:columns) values (:values)" % { 1145 "table" : self.table_name 1146 }, 1147 columns, [to_string(v, "utf-8") for v in values]) 1148 1149 self.cursor.execute(query, values) 1150 1151 def remove_periods(self, periods): 1152 1153 "Remove the given 'periods' from the collection." 1154 1155 self._check_mutable() 1156 1157 for period in periods: 1158 values = period.as_tuple(string_datetimes=True) 1159 1160 query, values = self.get_query( 1161 "delete from %(table)s :condition" % { 1162 "table" : self.table_name 1163 }, 1164 self.period_columns, [to_string(v, "utf-8") for v in values]) 1165 1166 self.cursor.execute(query, values) 1167 1168 def remove_event_periods(self, uid, recurrenceid=None): 1169 1170 """ 1171 Remove from the collection all periods associated with 'uid' and 1172 'recurrenceid' (which if omitted causes the "parent" object's periods to 1173 be referenced). 1174 1175 Return the removed periods. 1176 """ 1177 1178 self._check_mutable() 1179 1180 if recurrenceid: 1181 columns, values = ["object_uid", "object_recurrenceid"], [uid, recurrenceid] 1182 else: 1183 columns, values = ["object_uid", "object_recurrenceid is null"], [uid] 1184 1185 query, _values = self.get_query( 1186 "select %(columns)s from %(table)s :condition" % { 1187 "columns" : self.columnlist(self.period_columns), 1188 "table" : self.table_name 1189 }, 1190 columns, values) 1191 1192 self.cursor.execute(query, _values) 1193 removed = self.cursor.fetchall() 1194 1195 query, values = self.get_query( 1196 "delete from %(table)s :condition" % { 1197 "table" : self.table_name 1198 }, 1199 columns, values) 1200 1201 self.cursor.execute(query, values) 1202 1203 return map(lambda t: self.make_period(t), removed) 1204 1205 # Specific period removal when updating event details. 1206 1207 remove_specific_event_periods = remove_event_periods 1208 1209 def remove_additional_periods(self, uid, recurrenceids=None): 1210 1211 """ 1212 Remove from the collection all periods associated with 'uid' having a 1213 recurrence identifier indicating an additional or modified period. 1214 1215 If 'recurrenceids' is specified, remove all periods associated with 1216 'uid' that do not have a recurrence identifier in the given list. 1217 1218 Return the removed periods. 1219 """ 1220 1221 self._check_mutable() 1222 1223 if not recurrenceids: 1224 columns, values = ["object_uid", "object_recurrenceid is not null"], [uid] 1225 else: 1226 columns, values = ["object_uid", "object_recurrenceid not in ?", "object_recurrenceid is not null"], [uid, tuple(recurrenceids)] 1227 1228 query, _values = self.get_query( 1229 "select %(columns)s from %(table)s :condition" % { 1230 "columns" : self.columnlist(self.period_columns), 1231 "table" : self.table_name 1232 }, 1233 columns, values) 1234 1235 self.cursor.execute(query, _values) 1236 removed = self.cursor.fetchall() 1237 1238 query, values = self.get_query( 1239 "delete from %(table)s :condition" % { 1240 "table" : self.table_name 1241 }, 1242 columns, values) 1243 1244 self.cursor.execute(query, values) 1245 1246 return map(lambda t: self.make_period(t), removed) 1247 1248 def remove_affected_period(self, uid, start): 1249 1250 """ 1251 Remove from the collection the period associated with 'uid' that 1252 provides an occurrence starting at the given 'start' (provided by a 1253 recurrence identifier, converted to a datetime). A recurrence identifier 1254 is used to provide an alternative time period whilst also acting as a 1255 reference to the originally-defined occurrence. 1256 1257 Return any removed period in a list. 1258 """ 1259 1260 self._check_mutable() 1261 1262 start = format_datetime(start) 1263 1264 columns, values = ["object_uid", "start", "object_recurrenceid is null"], [uid, start] 1265 1266 query, _values = self.get_query( 1267 "select %(columns)s from %(table)s :condition" % { 1268 "columns" : self.columnlist(self.period_columns), 1269 "table" : self.table_name 1270 }, 1271 columns, values) 1272 1273 self.cursor.execute(query, _values) 1274 removed = self.cursor.fetchall() 1275 1276 query, values = self.get_query( 1277 "delete from %(table)s :condition" % { 1278 "table" : self.table_name 1279 }, 1280 columns, values) 1281 1282 self.cursor.execute(query, values) 1283 1284 return map(lambda t: self.make_period(t), removed) 1285 1286 def periods_from(self, period): 1287 1288 "Return the entries in the collection at or after 'period'." 1289 1290 start = format_datetime(period.get_start_point()) 1291 1292 columns, values = [], [] 1293 1294 if start: 1295 columns.append("start >= ?") 1296 values.append(start) 1297 1298 query, values = self.get_query( 1299 "select %(columns)s from %(table)s :condition" % { 1300 "columns" : self.columnlist(self.period_columns), 1301 "table" : self.table_name 1302 }, 1303 columns, values) 1304 1305 self.cursor.execute(query, values) 1306 1307 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1308 1309 def periods_until(self, period): 1310 1311 "Return the entries in the collection before 'period'." 1312 1313 end = format_datetime(period.get_end_point()) 1314 1315 columns, values = [], [] 1316 1317 if end: 1318 columns.append("start < ?") 1319 values.append(end) 1320 1321 query, values = self.get_query( 1322 "select %(columns)s from %(table)s :condition" % { 1323 "columns" : self.columnlist(self.period_columns), 1324 "table" : self.table_name 1325 }, 1326 columns, values) 1327 1328 self.cursor.execute(query, values) 1329 1330 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1331 1332 def get_overlapping(self, period): 1333 1334 """ 1335 Return the entries in the collection providing periods overlapping with 1336 'period'. 1337 """ 1338 1339 columns, values = self._get_period_values(period) 1340 1341 query, values = self.get_query( 1342 "select %(columns)s from %(table)s :condition" % { 1343 "columns" : self.columnlist(self.period_columns), 1344 "table" : self.table_name 1345 }, 1346 columns, values) 1347 1348 self.cursor.execute(query, values) 1349 1350 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1351 1352 def remove_overlapping(self, period): 1353 1354 "Remove all periods overlapping with 'period' from the collection." 1355 1356 self._check_mutable() 1357 1358 columns, values = self._get_period_values(period) 1359 1360 query, values = self.get_query( 1361 "delete from %(table)s :condition" % { 1362 "table" : self.table_name 1363 }, 1364 columns, values) 1365 1366 self.cursor.execute(query, values) 1367 1368 def _get_period_values(self, period): 1369 1370 start = format_datetime(period.get_start_point()) 1371 end = format_datetime(period.get_end_point()) 1372 1373 columns, values = [], [] 1374 1375 if end: 1376 columns.append("start < ?") 1377 values.append(end) 1378 if start: 1379 columns.append("end > ?") 1380 values.append(start) 1381 1382 return columns, values 1383 1384 class FreeBusyGroupDatabaseCollection(SupportAttendee, FreeBusyDatabaseCollection): 1385 1386 "A collection of quota group free/busy objects." 1387 1388 def remove_specific_event_periods(self, uid, recurrenceid=None, attendee=None): 1389 1390 """ 1391 Remove from the collection all periods associated with 'uid' and 1392 'recurrenceid' (which if omitted causes the "parent" object's periods to 1393 be referenced) and any 'attendee'. 1394 1395 Return the removed periods. 1396 """ 1397 1398 self._check_mutable() 1399 1400 columns, values = ["object_uid"], [uid] 1401 1402 if recurrenceid: 1403 columns.append("object_recurrenceid") 1404 values.append(recurrenceid) 1405 else: 1406 columns.append("object_recurrenceid is null") 1407 1408 if attendee: 1409 columns.append("attendee") 1410 values.append(attendee) 1411 else: 1412 columns.append("attendee is null") 1413 1414 query, _values = self.get_query( 1415 "select %(columns)s from %(table)s :condition" % { 1416 "columns" : self.columnlist(self.period_columns), 1417 "table" : self.table_name 1418 }, 1419 columns, values) 1420 1421 self.cursor.execute(query, _values) 1422 removed = self.cursor.fetchall() 1423 1424 query, values = self.get_query( 1425 "delete from %(table)s :condition" % { 1426 "table" : self.table_name 1427 }, 1428 columns, values) 1429 1430 self.cursor.execute(query, values) 1431 1432 return map(lambda t: self.make_period(t), removed) 1433 1434 class FreeBusyOffersDatabaseCollection(SupportExpires, FreeBusyDatabaseCollection): 1435 1436 "A collection of offered free/busy objects." 1437 1438 pass 1439 1440 # Period layout. 1441 1442 def get_scale(periods, tzid, view_period=None): 1443 1444 """ 1445 Return a time scale from the given list of 'periods'. 1446 1447 The given 'tzid' is used to make sure that the times are defined according 1448 to the chosen time zone. 1449 1450 An optional 'view_period' is used to constrain the scale to the given 1451 period. 1452 1453 The returned scale is a mapping from time to (starting, ending) tuples, 1454 where starting and ending are collections of periods. 1455 """ 1456 1457 scale = {} 1458 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 1459 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 1460 1461 for p in periods: 1462 1463 # Add a point and this event to the starting list. 1464 1465 start = to_timezone(p.get_start(), tzid) 1466 start = view_start and max(start, view_start) or start 1467 if not scale.has_key(start): 1468 scale[start] = [], [] 1469 scale[start][0].append(p) 1470 1471 # Add a point and this event to the ending list. 1472 1473 end = to_timezone(p.get_end(), tzid) 1474 end = view_end and min(end, view_end) or end 1475 if not scale.has_key(end): 1476 scale[end] = [], [] 1477 scale[end][1].append(p) 1478 1479 return scale 1480 1481 class Point: 1482 1483 "A qualified point in time." 1484 1485 PRINCIPAL, REPEATED = 0, 1 1486 1487 def __init__(self, point, indicator=None): 1488 self.point = point 1489 self.indicator = indicator or self.PRINCIPAL 1490 1491 def __hash__(self): 1492 return hash((self.point, self.indicator)) 1493 1494 def __cmp__(self, other): 1495 if isinstance(other, Point): 1496 return cmp((self.point, self.indicator), (other.point, other.indicator)) 1497 elif isinstance(other, datetime): 1498 return cmp(self.point, other) 1499 else: 1500 return 1 1501 1502 def __eq__(self, other): 1503 return self.__cmp__(other) == 0 1504 1505 def __ne__(self, other): 1506 return not self == other 1507 1508 def __lt__(self, other): 1509 return self.__cmp__(other) < 0 1510 1511 def __le__(self, other): 1512 return self.__cmp__(other) <= 0 1513 1514 def __gt__(self, other): 1515 return not self <= other 1516 1517 def __ge__(self, other): 1518 return not self < other 1519 1520 def __repr__(self): 1521 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 1522 1523 def get_slots(scale): 1524 1525 """ 1526 Return an ordered list of time slots from the given 'scale'. 1527 1528 Each slot is a tuple containing details of a point in time for the start of 1529 the slot, together with a list of parallel event periods. 1530 1531 Each point in time is described as a Point representing the actual point in 1532 time together with an indicator of the nature of the point in time (as a 1533 principal point in a time scale or as a repeated point used to terminate 1534 events occurring for an instant in time). 1535 """ 1536 1537 slots = [] 1538 active = [] 1539 1540 points = scale.items() 1541 points.sort() 1542 1543 for point, (starting, ending) in points: 1544 ending = set(ending) 1545 instants = ending.intersection(starting) 1546 1547 # Discard all active events ending at or before this start time. 1548 # Free up the position in the active list. 1549 1550 for t in ending.difference(instants): 1551 i = active.index(t) 1552 active[i] = None 1553 1554 # For each event starting at the current point, fill any newly-vacated 1555 # position or add to the end of the active list. 1556 1557 for t in starting: 1558 try: 1559 i = active.index(None) 1560 active[i] = t 1561 except ValueError: 1562 active.append(t) 1563 1564 # Discard vacant positions from the end of the active list. 1565 1566 while active and active[-1] is None: 1567 active.pop() 1568 1569 # Add an entry for the time point before "instants". 1570 1571 slots.append((Point(point), active[:])) 1572 1573 # Discard events ending at the same time as they began. 1574 1575 if instants: 1576 for t in instants: 1577 i = active.index(t) 1578 active[i] = None 1579 1580 # Discard vacant positions from the end of the active list. 1581 1582 while active and active[-1] is None: 1583 active.pop() 1584 1585 # Add another entry for the time point after "instants". 1586 1587 slots.append((Point(point, Point.REPEATED), active[:])) 1588 1589 return slots 1590 1591 def add_day_start_points(slots, tzid): 1592 1593 """ 1594 Introduce into the 'slots' any day start points required by multi-day 1595 periods. The 'tzid' is required to make sure that appropriate time zones 1596 are chosen and not necessarily those provided by the existing time points. 1597 """ 1598 1599 new_slots = [] 1600 current_date = None 1601 previously_active = [] 1602 1603 for point, active in slots: 1604 start_of_day = get_start_of_day(point.point, tzid) 1605 this_date = point.point.date() 1606 1607 # For each new day, add a slot for the start of the day where periods 1608 # are active and where no such slot already exists. 1609 1610 if this_date != current_date: 1611 1612 # Fill in days where events remain active. 1613 1614 if current_date: 1615 current_date += timedelta(1) 1616 while current_date < this_date: 1617 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 1618 current_date += timedelta(1) 1619 else: 1620 current_date = this_date 1621 1622 # Add any continuing periods. 1623 1624 if point.point != start_of_day: 1625 new_slots.append((Point(start_of_day), previously_active)) 1626 1627 # Add the currently active periods at this point in time. 1628 1629 previously_active = active 1630 1631 for t in new_slots: 1632 insort_left(slots, t) 1633 1634 def remove_end_slot(slots, view_period): 1635 1636 """ 1637 Remove from 'slots' any slot situated at the end of the given 'view_period'. 1638 """ 1639 1640 end = view_period.get_end_point() 1641 if not end or not slots: 1642 return 1643 i = bisect_left(slots, (Point(end), None)) 1644 if i < len(slots): 1645 del slots[i:] 1646 1647 def add_slots(slots, points): 1648 1649 """ 1650 Introduce into the 'slots' entries for those in 'points' that are not 1651 already present, propagating active periods from time points preceding 1652 those added. 1653 """ 1654 1655 new_slots = [] 1656 1657 for point in points: 1658 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 1659 if i < len(slots) and slots[i][0] == point: 1660 continue 1661 1662 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 1663 1664 for t in new_slots: 1665 insort_left(slots, t) 1666 1667 def partition_by_day(slots): 1668 1669 """ 1670 Return a mapping from dates to time points provided by 'slots'. 1671 """ 1672 1673 d = {} 1674 1675 for point, value in slots: 1676 day = point.point.date() 1677 if not d.has_key(day): 1678 d[day] = [] 1679 d[day].append((point, value)) 1680 1681 return d 1682 1683 def add_empty_days(days, tzid, start=None, end=None): 1684 1685 """ 1686 Add empty days to 'days' between busy days, and optionally from the given 1687 'start' day and until the given 'end' day. 1688 """ 1689 1690 last_day = start - timedelta(1) 1691 all_days = days.keys() 1692 all_days.sort() 1693 1694 for day in all_days: 1695 if last_day: 1696 empty_day = last_day + timedelta(1) 1697 while empty_day < day: 1698 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1699 empty_day += timedelta(1) 1700 last_day = day 1701 1702 if end: 1703 empty_day = last_day + timedelta(1) 1704 while empty_day < end: 1705 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1706 empty_day += timedelta(1) 1707 1708 def get_spans(slots): 1709 1710 "Inspect the given 'slots', returning a mapping of period keys to spans." 1711 1712 points = [point for point, active in slots] 1713 spans = {} 1714 1715 for _point, active in slots: 1716 for p in active: 1717 if p: 1718 key = p.get_key() 1719 start_slot = bisect_left(points, p.get_start()) 1720 end_slot = bisect_left(points, p.get_end()) 1721 spans[key] = end_slot - start_slot 1722 1723 return spans 1724 1725 # vim: tabstop=4 expandtab shiftwidth=4