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 __repr__(self): 523 return "FreeBusyGroupPeriod%r" % (self.as_tuple(),) 524 525 class RecurringPeriod(Period): 526 527 """ 528 A period with iCalendar metadata attributes and origin information from an 529 object. 530 """ 531 532 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 533 Period.__init__(self, start, end, tzid, origin) 534 self.start_attr = start_attr 535 self.end_attr = end_attr 536 537 def get_start_attr(self): 538 return self.start_attr 539 540 def get_end_attr(self): 541 return self.end_attr 542 543 def as_tuple(self): 544 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 545 546 def __repr__(self): 547 return "RecurringPeriod%r" % (self.as_tuple(),) 548 549 def make_corrected(self, start, end): 550 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 551 552 class FreeBusyCollectionBase: 553 554 "Common operations on free/busy period collections." 555 556 period_columns = [ 557 "start", "end", "object_uid", "transp", "object_recurrenceid", 558 "summary", "organiser" 559 ] 560 561 period_class = FreeBusyPeriod 562 563 def __init__(self, mutable=True): 564 self.mutable = mutable 565 566 def _check_mutable(self): 567 if not self.mutable: 568 raise TypeError, "Cannot mutate this collection." 569 570 def copy(self): 571 572 "Make an independent mutable copy of the collection." 573 574 return FreeBusyCollection(list(self), True) 575 576 def make_period(self, t): 577 578 """ 579 Make a period using the given tuple of arguments and the collection's 580 column details. 581 """ 582 583 args = [] 584 for arg, column in zip(t, self.period_columns): 585 args.append(from_string(arg, "utf-8")) 586 return self.period_class(*args) 587 588 def make_tuple(self, t): 589 590 """ 591 Return a tuple from the given tuple 't' conforming to the collection's 592 column details. 593 """ 594 595 args = [] 596 for arg, column in zip(t, self.period_columns): 597 args.append(arg) 598 return tuple(args) 599 600 # List emulation methods. 601 602 def __iadd__(self, periods): 603 for period in periods: 604 self.insert_period(period) 605 return self 606 607 def append(self, period): 608 self.insert_period(period) 609 610 # Operations. 611 612 def can_schedule(self, periods, uid, recurrenceid): 613 614 """ 615 Return whether the collection can accommodate the given 'periods' 616 employing the specified 'uid' and 'recurrenceid'. 617 """ 618 619 for conflict in self.have_conflict(periods, True): 620 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 621 return False 622 623 return True 624 625 def have_conflict(self, periods, get_conflicts=False): 626 627 """ 628 Return whether any period in the collection overlaps with the given 629 'periods', returning a collection of such overlapping periods if 630 'get_conflicts' is set to a true value. 631 """ 632 633 conflicts = set() 634 for p in periods: 635 overlapping = self.period_overlaps(p, get_conflicts) 636 if overlapping: 637 if get_conflicts: 638 conflicts.update(overlapping) 639 else: 640 return True 641 642 if get_conflicts: 643 return conflicts 644 else: 645 return False 646 647 def period_overlaps(self, period, get_periods=False): 648 649 """ 650 Return whether any period in the collection overlaps with the given 651 'period', returning a collection of overlapping periods if 'get_periods' 652 is set to a true value. 653 """ 654 655 overlapping = self.get_overlapping(period) 656 657 if get_periods: 658 return overlapping 659 else: 660 return len(overlapping) != 0 661 662 def replace_overlapping(self, period, replacements): 663 664 """ 665 Replace existing periods in the collection within the given 'period', 666 using the given 'replacements'. 667 """ 668 669 self._check_mutable() 670 671 self.remove_overlapping(period) 672 for replacement in replacements: 673 self.insert_period(replacement) 674 675 def coalesce_freebusy(self): 676 677 "Coalesce the periods in the collection, returning a new collection." 678 679 if not self: 680 return FreeBusyCollection() 681 682 fb = [] 683 684 it = iter(self) 685 period = it.next() 686 687 start = period.get_start_point() 688 end = period.get_end_point() 689 690 try: 691 while True: 692 period = it.next() 693 if period.get_start_point() > end: 694 fb.append(self.period_class(start, end)) 695 start = period.get_start_point() 696 end = period.get_end_point() 697 else: 698 end = max(end, period.get_end_point()) 699 except StopIteration: 700 pass 701 702 fb.append(self.period_class(start, end)) 703 return FreeBusyCollection(fb) 704 705 def invert_freebusy(self): 706 707 "Return the free periods from the collection as a new collection." 708 709 if not self: 710 return FreeBusyCollection([self.period_class(None, None)]) 711 712 # Coalesce periods that overlap or are adjacent. 713 714 fb = self.coalesce_freebusy() 715 free = [] 716 717 # Add a start-of-time period if appropriate. 718 719 first = fb[0].get_start_point() 720 if first: 721 free.append(self.period_class(None, first)) 722 723 start = fb[0].get_end_point() 724 725 for period in fb[1:]: 726 free.append(self.period_class(start, period.get_start_point())) 727 start = period.get_end_point() 728 729 # Add an end-of-time period if appropriate. 730 731 if start: 732 free.append(self.period_class(start, None)) 733 734 return FreeBusyCollection(free) 735 736 def _update_freebusy(self, periods, uid, recurrenceid): 737 738 """ 739 Update the free/busy details with the given 'periods', using the given 740 'uid' plus 'recurrenceid' to remove existing periods. 741 """ 742 743 self._check_mutable() 744 745 self.remove_event_periods(uid, recurrenceid) 746 747 for p in periods: 748 self.insert_period(p) 749 750 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser): 751 752 """ 753 Update the free/busy details with the given 'periods', 'transp' setting, 754 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 755 """ 756 757 new_periods = [] 758 759 for p in periods: 760 new_periods.append( 761 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser) 762 ) 763 764 self._update_freebusy(new_periods, uid, recurrenceid) 765 766 class SupportAttendee: 767 768 "A mix-in that supports the affected attendee in free/busy periods." 769 770 period_columns = FreeBusyCollectionBase.period_columns + ["attendee"] 771 period_class = FreeBusyGroupPeriod 772 773 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, attendee=None): 774 775 """ 776 Update the free/busy details with the given 'periods', 'transp' setting, 777 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 778 779 An optional 'attendee' indicates the attendee affected by the period. 780 """ 781 782 new_periods = [] 783 784 for p in periods: 785 new_periods.append( 786 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, attendee) 787 ) 788 789 self._update_freebusy(new_periods, uid, recurrenceid) 790 791 class SupportExpires: 792 793 "A mix-in that supports the expiry datetime in free/busy periods." 794 795 period_columns = FreeBusyCollectionBase.period_columns + ["expires"] 796 period_class = FreeBusyOfferPeriod 797 798 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 799 800 """ 801 Update the free/busy details with the given 'periods', 'transp' setting, 802 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 803 804 An optional 'expires' datetime string indicates the expiry time of any 805 free/busy offer. 806 """ 807 808 new_periods = [] 809 810 for p in periods: 811 new_periods.append( 812 self.period_class(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires) 813 ) 814 815 self._update_freebusy(new_periods, uid, recurrenceid) 816 817 class FreeBusyCollection(FreeBusyCollectionBase): 818 819 "An abstraction for a collection of free/busy periods." 820 821 def __init__(self, periods=None, mutable=True): 822 823 """ 824 Initialise the collection with the given list of 'periods', or start an 825 empty collection if no list is given. If 'mutable' is indicated, the 826 collection may be changed; otherwise, an exception will be raised. 827 """ 828 829 FreeBusyCollectionBase.__init__(self, mutable) 830 self.periods = periods or [] 831 832 # List emulation methods. 833 834 def __nonzero__(self): 835 return bool(self.periods) 836 837 def __iter__(self): 838 return iter(self.periods) 839 840 def __len__(self): 841 return len(self.periods) 842 843 def __getitem__(self, i): 844 return self.periods[i] 845 846 # Operations. 847 848 def insert_period(self, period): 849 850 "Insert the given 'period' into the collection." 851 852 self._check_mutable() 853 854 i = bisect_left(self.periods, period) 855 if i == len(self.periods): 856 self.periods.append(period) 857 elif self.periods[i] != period: 858 self.periods.insert(i, period) 859 860 def remove_periods(self, periods): 861 862 "Remove the given 'periods' from the collection." 863 864 self._check_mutable() 865 866 for period in periods: 867 i = bisect_left(self.periods, period) 868 if i < len(self.periods) and self.periods[i] == period: 869 del self.periods[i] 870 871 def remove_event_periods(self, uid, recurrenceid=None): 872 873 """ 874 Remove from the collection all periods associated with 'uid' and 875 'recurrenceid' (which if omitted causes the "parent" object's periods to 876 be referenced). 877 878 Return the removed periods. 879 """ 880 881 self._check_mutable() 882 883 removed = [] 884 i = 0 885 while i < len(self.periods): 886 fb = self.periods[i] 887 if fb.uid == uid and fb.recurrenceid == recurrenceid: 888 removed.append(self.periods[i]) 889 del self.periods[i] 890 else: 891 i += 1 892 893 return removed 894 895 def remove_additional_periods(self, uid, recurrenceids=None): 896 897 """ 898 Remove from the collection all periods associated with 'uid' having a 899 recurrence identifier indicating an additional or modified period. 900 901 If 'recurrenceids' is specified, remove all periods associated with 902 'uid' that do not have a recurrence identifier in the given list. 903 904 Return the removed periods. 905 """ 906 907 self._check_mutable() 908 909 removed = [] 910 i = 0 911 while i < len(self.periods): 912 fb = self.periods[i] 913 if fb.uid == uid and fb.recurrenceid and ( 914 recurrenceids is None or 915 recurrenceids is not None and fb.recurrenceid not in recurrenceids 916 ): 917 removed.append(self.periods[i]) 918 del self.periods[i] 919 else: 920 i += 1 921 922 return removed 923 924 def remove_affected_period(self, uid, start): 925 926 """ 927 Remove from the collection the period associated with 'uid' that 928 provides an occurrence starting at the given 'start' (provided by a 929 recurrence identifier, converted to a datetime). A recurrence identifier 930 is used to provide an alternative time period whilst also acting as a 931 reference to the originally-defined occurrence. 932 933 Return any removed period in a list. 934 """ 935 936 self._check_mutable() 937 938 removed = [] 939 940 search = Period(start, start) 941 found = bisect_left(self.periods, search) 942 943 while found < len(self.periods): 944 fb = self.periods[found] 945 946 # Stop looking if the start no longer matches the recurrence identifier. 947 948 if fb.get_start_point() != search.get_start_point(): 949 break 950 951 # If the period belongs to the parent object, remove it and return. 952 953 if not fb.recurrenceid and uid == fb.uid: 954 removed.append(self.periods[found]) 955 del self.periods[found] 956 break 957 958 # Otherwise, keep looking for a matching period. 959 960 found += 1 961 962 return removed 963 964 def periods_from(self, period): 965 966 "Return the entries in the collection at or after 'period'." 967 968 first = bisect_left(self.periods, period) 969 return self.periods[first:] 970 971 def periods_until(self, period): 972 973 "Return the entries in the collection before 'period'." 974 975 last = bisect_right(self.periods, Period(period.get_end(), period.get_end(), period.get_tzid())) 976 return self.periods[:last] 977 978 def get_overlapping(self, period): 979 980 """ 981 Return the entries in the collection providing periods overlapping with 982 'period'. 983 """ 984 985 # Find the range of periods potentially overlapping the period in the 986 # free/busy collection. 987 988 startpoints = self.periods_until(period) 989 990 # Find the range of periods potentially overlapping the period in a version 991 # of the free/busy collection sorted according to end datetimes. 992 993 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 994 endpoints.sort() 995 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 996 endpoints = endpoints[first:] 997 998 overlapping = set() 999 1000 for p, fb in endpoints: 1001 if fb.overlaps(period): 1002 overlapping.add(fb) 1003 1004 overlapping = list(overlapping) 1005 overlapping.sort() 1006 return overlapping 1007 1008 def remove_overlapping(self, period): 1009 1010 "Remove all periods overlapping with 'period' from the collection." 1011 1012 self._check_mutable() 1013 1014 overlapping = self.get_overlapping(period) 1015 1016 if overlapping: 1017 for fb in overlapping: 1018 self.periods.remove(fb) 1019 1020 class FreeBusyGroupCollection(SupportAttendee, FreeBusyCollection): 1021 1022 "A collection of quota group free/busy objects." 1023 1024 pass 1025 1026 class FreeBusyOffersCollection(SupportExpires, FreeBusyCollection): 1027 1028 "A collection of offered free/busy objects." 1029 1030 pass 1031 1032 class FreeBusyDatabaseCollection(FreeBusyCollectionBase, DatabaseOperations): 1033 1034 """ 1035 An abstraction for a collection of free/busy periods stored in a database 1036 system. 1037 """ 1038 1039 def __init__(self, cursor, table_name, column_names=None, filter_values=None, 1040 mutable=True, paramstyle=None): 1041 1042 """ 1043 Initialise the collection with the given 'cursor' and with the 1044 'table_name', 'column_names' and 'filter_values' configuring the 1045 selection of data. If 'mutable' is indicated, the collection may be 1046 changed; otherwise, an exception will be raised. 1047 """ 1048 1049 FreeBusyCollectionBase.__init__(self, mutable) 1050 DatabaseOperations.__init__(self, column_names, filter_values, paramstyle) 1051 self.cursor = cursor 1052 self.table_name = table_name 1053 1054 # List emulation methods. 1055 1056 def __nonzero__(self): 1057 return len(self) and True or False 1058 1059 def __iter__(self): 1060 query, values = self.get_query( 1061 "select %(columns)s from %(table)s :condition" % { 1062 "columns" : self.columnlist(self.period_columns), 1063 "table" : self.table_name 1064 }) 1065 self.cursor.execute(query, values) 1066 return iter(map(lambda t: self.make_period(t), self.cursor.fetchall())) 1067 1068 def __len__(self): 1069 query, values = self.get_query( 1070 "select count(*) from %(table)s :condition" % { 1071 "table" : self.table_name 1072 }) 1073 self.cursor.execute(query, values) 1074 result = self.cursor.fetchone() 1075 return result and int(result[0]) or 0 1076 1077 def __getitem__(self, i): 1078 return list(iter(self))[i] 1079 1080 # Operations. 1081 1082 def insert_period(self, period): 1083 1084 "Insert the given 'period' into the collection." 1085 1086 self._check_mutable() 1087 1088 columns, values = self.period_columns, period.as_tuple(string_datetimes=True) 1089 1090 query, values = self.get_query( 1091 "insert into %(table)s (:columns) values (:values)" % { 1092 "table" : self.table_name 1093 }, 1094 columns, [to_string(v, "utf-8") for v in values]) 1095 1096 self.cursor.execute(query, values) 1097 1098 def remove_periods(self, periods): 1099 1100 "Remove the given 'periods' from the collection." 1101 1102 self._check_mutable() 1103 1104 for period in periods: 1105 values = period.as_tuple(string_datetimes=True) 1106 1107 query, values = self.get_query( 1108 "delete from %(table)s :condition" % { 1109 "table" : self.table_name 1110 }, 1111 self.period_columns, [to_string(v, "utf-8") for v in values]) 1112 1113 self.cursor.execute(query, values) 1114 1115 def remove_event_periods(self, uid, recurrenceid=None): 1116 1117 """ 1118 Remove from the collection all periods associated with 'uid' and 1119 'recurrenceid' (which if omitted causes the "parent" object's periods to 1120 be referenced). 1121 1122 Return the removed periods. 1123 """ 1124 1125 self._check_mutable() 1126 1127 if recurrenceid: 1128 columns, values = ["object_uid", "object_recurrenceid"], [uid, recurrenceid] 1129 else: 1130 columns, values = ["object_uid", "object_recurrenceid is null"], [uid] 1131 1132 query, _values = self.get_query( 1133 "select %(columns)s from %(table)s :condition" % { 1134 "columns" : self.columnlist(self.period_columns), 1135 "table" : self.table_name 1136 }, 1137 columns, values) 1138 1139 self.cursor.execute(query, _values) 1140 removed = self.cursor.fetchall() 1141 1142 query, values = self.get_query( 1143 "delete from %(table)s :condition" % { 1144 "table" : self.table_name 1145 }, 1146 columns, values) 1147 1148 self.cursor.execute(query, values) 1149 1150 return map(lambda t: self.make_period(t), removed) 1151 1152 def remove_additional_periods(self, uid, recurrenceids=None): 1153 1154 """ 1155 Remove from the collection all periods associated with 'uid' having a 1156 recurrence identifier indicating an additional or modified period. 1157 1158 If 'recurrenceids' is specified, remove all periods associated with 1159 'uid' that do not have a recurrence identifier in the given list. 1160 1161 Return the removed periods. 1162 """ 1163 1164 self._check_mutable() 1165 1166 if not recurrenceids: 1167 columns, values = ["object_uid", "object_recurrenceid is not null"], [uid] 1168 else: 1169 columns, values = ["object_uid", "object_recurrenceid not in ?", "object_recurrenceid is not null"], [uid, tuple(recurrenceids)] 1170 1171 query, _values = self.get_query( 1172 "select %(columns)s from %(table)s :condition" % { 1173 "columns" : self.columnlist(self.period_columns), 1174 "table" : self.table_name 1175 }, 1176 columns, values) 1177 1178 self.cursor.execute(query, _values) 1179 removed = self.cursor.fetchall() 1180 1181 query, values = self.get_query( 1182 "delete from %(table)s :condition" % { 1183 "table" : self.table_name 1184 }, 1185 columns, values) 1186 1187 self.cursor.execute(query, values) 1188 1189 return map(lambda t: self.make_period(t), removed) 1190 1191 def remove_affected_period(self, uid, start): 1192 1193 """ 1194 Remove from the collection the period associated with 'uid' that 1195 provides an occurrence starting at the given 'start' (provided by a 1196 recurrence identifier, converted to a datetime). A recurrence identifier 1197 is used to provide an alternative time period whilst also acting as a 1198 reference to the originally-defined occurrence. 1199 1200 Return any removed period in a list. 1201 """ 1202 1203 self._check_mutable() 1204 1205 start = format_datetime(start) 1206 1207 columns, values = ["object_uid", "start", "object_recurrenceid is null"], [uid, start] 1208 1209 query, _values = self.get_query( 1210 "select %(columns)s from %(table)s :condition" % { 1211 "columns" : self.columnlist(self.period_columns), 1212 "table" : self.table_name 1213 }, 1214 columns, values) 1215 1216 self.cursor.execute(query, _values) 1217 removed = self.cursor.fetchall() 1218 1219 query, values = self.get_query( 1220 "delete from %(table)s :condition" % { 1221 "table" : self.table_name 1222 }, 1223 columns, values) 1224 1225 self.cursor.execute(query, values) 1226 1227 return map(lambda t: self.make_period(t), removed) 1228 1229 def periods_from(self, period): 1230 1231 "Return the entries in the collection at or after 'period'." 1232 1233 start = format_datetime(period.get_start_point()) 1234 1235 columns, values = [], [] 1236 1237 if start: 1238 columns.append("start >= ?") 1239 values.append(start) 1240 1241 query, values = self.get_query( 1242 "select %(columns)s from %(table)s :condition" % { 1243 "columns" : self.columnlist(self.period_columns), 1244 "table" : self.table_name 1245 }, 1246 columns, values) 1247 1248 self.cursor.execute(query, values) 1249 1250 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1251 1252 def periods_until(self, period): 1253 1254 "Return the entries in the collection before 'period'." 1255 1256 end = format_datetime(period.get_end_point()) 1257 1258 columns, values = [], [] 1259 1260 if end: 1261 columns.append("start < ?") 1262 values.append(end) 1263 1264 query, values = self.get_query( 1265 "select %(columns)s from %(table)s :condition" % { 1266 "columns" : self.columnlist(self.period_columns), 1267 "table" : self.table_name 1268 }, 1269 columns, values) 1270 1271 self.cursor.execute(query, values) 1272 1273 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1274 1275 def get_overlapping(self, period): 1276 1277 """ 1278 Return the entries in the collection providing periods overlapping with 1279 'period'. 1280 """ 1281 1282 columns, values = self._get_period_values(period) 1283 1284 query, values = self.get_query( 1285 "select %(columns)s from %(table)s :condition" % { 1286 "columns" : self.columnlist(self.period_columns), 1287 "table" : self.table_name 1288 }, 1289 columns, values) 1290 1291 self.cursor.execute(query, values) 1292 1293 return map(lambda t: self.make_period(t), self.cursor.fetchall()) 1294 1295 def remove_overlapping(self, period): 1296 1297 "Remove all periods overlapping with 'period' from the collection." 1298 1299 self._check_mutable() 1300 1301 columns, values = self._get_period_values(period) 1302 1303 query, values = self.get_query( 1304 "delete from %(table)s :condition" % { 1305 "table" : self.table_name 1306 }, 1307 columns, values) 1308 1309 self.cursor.execute(query, values) 1310 1311 def _get_period_values(self, period): 1312 1313 start = format_datetime(period.get_start_point()) 1314 end = format_datetime(period.get_end_point()) 1315 1316 columns, values = [], [] 1317 1318 if end: 1319 columns.append("start < ?") 1320 values.append(end) 1321 if start: 1322 columns.append("end > ?") 1323 values.append(start) 1324 1325 return columns, values 1326 1327 class FreeBusyGroupDatabaseCollection(SupportAttendee, FreeBusyDatabaseCollection): 1328 1329 "A collection of quota group free/busy objects." 1330 1331 pass 1332 1333 class FreeBusyOffersDatabaseCollection(SupportExpires, FreeBusyDatabaseCollection): 1334 1335 "A collection of offered free/busy objects." 1336 1337 pass 1338 1339 # Period layout. 1340 1341 def get_scale(periods, tzid, view_period=None): 1342 1343 """ 1344 Return a time scale from the given list of 'periods'. 1345 1346 The given 'tzid' is used to make sure that the times are defined according 1347 to the chosen time zone. 1348 1349 An optional 'view_period' is used to constrain the scale to the given 1350 period. 1351 1352 The returned scale is a mapping from time to (starting, ending) tuples, 1353 where starting and ending are collections of periods. 1354 """ 1355 1356 scale = {} 1357 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 1358 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 1359 1360 for p in periods: 1361 1362 # Add a point and this event to the starting list. 1363 1364 start = to_timezone(p.get_start(), tzid) 1365 start = view_start and max(start, view_start) or start 1366 if not scale.has_key(start): 1367 scale[start] = [], [] 1368 scale[start][0].append(p) 1369 1370 # Add a point and this event to the ending list. 1371 1372 end = to_timezone(p.get_end(), tzid) 1373 end = view_end and min(end, view_end) or end 1374 if not scale.has_key(end): 1375 scale[end] = [], [] 1376 scale[end][1].append(p) 1377 1378 return scale 1379 1380 class Point: 1381 1382 "A qualified point in time." 1383 1384 PRINCIPAL, REPEATED = 0, 1 1385 1386 def __init__(self, point, indicator=None): 1387 self.point = point 1388 self.indicator = indicator or self.PRINCIPAL 1389 1390 def __hash__(self): 1391 return hash((self.point, self.indicator)) 1392 1393 def __cmp__(self, other): 1394 if isinstance(other, Point): 1395 return cmp((self.point, self.indicator), (other.point, other.indicator)) 1396 elif isinstance(other, datetime): 1397 return cmp(self.point, other) 1398 else: 1399 return 1 1400 1401 def __eq__(self, other): 1402 return self.__cmp__(other) == 0 1403 1404 def __ne__(self, other): 1405 return not self == other 1406 1407 def __lt__(self, other): 1408 return self.__cmp__(other) < 0 1409 1410 def __le__(self, other): 1411 return self.__cmp__(other) <= 0 1412 1413 def __gt__(self, other): 1414 return not self <= other 1415 1416 def __ge__(self, other): 1417 return not self < other 1418 1419 def __repr__(self): 1420 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 1421 1422 def get_slots(scale): 1423 1424 """ 1425 Return an ordered list of time slots from the given 'scale'. 1426 1427 Each slot is a tuple containing details of a point in time for the start of 1428 the slot, together with a list of parallel event periods. 1429 1430 Each point in time is described as a Point representing the actual point in 1431 time together with an indicator of the nature of the point in time (as a 1432 principal point in a time scale or as a repeated point used to terminate 1433 events occurring for an instant in time). 1434 """ 1435 1436 slots = [] 1437 active = [] 1438 1439 points = scale.items() 1440 points.sort() 1441 1442 for point, (starting, ending) in points: 1443 ending = set(ending) 1444 instants = ending.intersection(starting) 1445 1446 # Discard all active events ending at or before this start time. 1447 # Free up the position in the active list. 1448 1449 for t in ending.difference(instants): 1450 i = active.index(t) 1451 active[i] = None 1452 1453 # For each event starting at the current point, fill any newly-vacated 1454 # position or add to the end of the active list. 1455 1456 for t in starting: 1457 try: 1458 i = active.index(None) 1459 active[i] = t 1460 except ValueError: 1461 active.append(t) 1462 1463 # Discard vacant positions from the end of the active list. 1464 1465 while active and active[-1] is None: 1466 active.pop() 1467 1468 # Add an entry for the time point before "instants". 1469 1470 slots.append((Point(point), active[:])) 1471 1472 # Discard events ending at the same time as they began. 1473 1474 if instants: 1475 for t in instants: 1476 i = active.index(t) 1477 active[i] = None 1478 1479 # Discard vacant positions from the end of the active list. 1480 1481 while active and active[-1] is None: 1482 active.pop() 1483 1484 # Add another entry for the time point after "instants". 1485 1486 slots.append((Point(point, Point.REPEATED), active[:])) 1487 1488 return slots 1489 1490 def add_day_start_points(slots, tzid): 1491 1492 """ 1493 Introduce into the 'slots' any day start points required by multi-day 1494 periods. The 'tzid' is required to make sure that appropriate time zones 1495 are chosen and not necessarily those provided by the existing time points. 1496 """ 1497 1498 new_slots = [] 1499 current_date = None 1500 previously_active = [] 1501 1502 for point, active in slots: 1503 start_of_day = get_start_of_day(point.point, tzid) 1504 this_date = point.point.date() 1505 1506 # For each new day, add a slot for the start of the day where periods 1507 # are active and where no such slot already exists. 1508 1509 if this_date != current_date: 1510 1511 # Fill in days where events remain active. 1512 1513 if current_date: 1514 current_date += timedelta(1) 1515 while current_date < this_date: 1516 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 1517 current_date += timedelta(1) 1518 else: 1519 current_date = this_date 1520 1521 # Add any continuing periods. 1522 1523 if point.point != start_of_day: 1524 new_slots.append((Point(start_of_day), previously_active)) 1525 1526 # Add the currently active periods at this point in time. 1527 1528 previously_active = active 1529 1530 for t in new_slots: 1531 insort_left(slots, t) 1532 1533 def remove_end_slot(slots, view_period): 1534 1535 """ 1536 Remove from 'slots' any slot situated at the end of the given 'view_period'. 1537 """ 1538 1539 end = view_period.get_end_point() 1540 if not end or not slots: 1541 return 1542 i = bisect_left(slots, (Point(end), None)) 1543 if i < len(slots): 1544 del slots[i:] 1545 1546 def add_slots(slots, points): 1547 1548 """ 1549 Introduce into the 'slots' entries for those in 'points' that are not 1550 already present, propagating active periods from time points preceding 1551 those added. 1552 """ 1553 1554 new_slots = [] 1555 1556 for point in points: 1557 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 1558 if i < len(slots) and slots[i][0] == point: 1559 continue 1560 1561 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 1562 1563 for t in new_slots: 1564 insort_left(slots, t) 1565 1566 def partition_by_day(slots): 1567 1568 """ 1569 Return a mapping from dates to time points provided by 'slots'. 1570 """ 1571 1572 d = {} 1573 1574 for point, value in slots: 1575 day = point.point.date() 1576 if not d.has_key(day): 1577 d[day] = [] 1578 d[day].append((point, value)) 1579 1580 return d 1581 1582 def add_empty_days(days, tzid, start=None, end=None): 1583 1584 """ 1585 Add empty days to 'days' between busy days, and optionally from the given 1586 'start' day and until the given 'end' day. 1587 """ 1588 1589 last_day = start - timedelta(1) 1590 all_days = days.keys() 1591 all_days.sort() 1592 1593 for day in all_days: 1594 if last_day: 1595 empty_day = last_day + timedelta(1) 1596 while empty_day < day: 1597 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1598 empty_day += timedelta(1) 1599 last_day = day 1600 1601 if end: 1602 empty_day = last_day + timedelta(1) 1603 while empty_day < end: 1604 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1605 empty_day += timedelta(1) 1606 1607 def get_spans(slots): 1608 1609 "Inspect the given 'slots', returning a mapping of period keys to spans." 1610 1611 points = [point for point, active in slots] 1612 spans = {} 1613 1614 for _point, active in slots: 1615 for p in active: 1616 if p: 1617 key = p.get_key() 1618 start_slot = bisect_left(points, p.get_start()) 1619 end_slot = bisect_left(points, p.get_end()) 1620 spans[key] = end_slot - start_slot 1621 1622 return spans 1623 1624 # vim: tabstop=4 expandtab shiftwidth=4