1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from bisect import bisect_left, bisect_right, insort_left 23 from datetime import date, datetime, timedelta 24 from imiptools.dates import check_permitted_values, correct_datetime, \ 25 format_datetime, get_datetime, \ 26 get_datetime_attributes, \ 27 get_recurrence_start, get_recurrence_start_point, \ 28 get_start_of_day, \ 29 get_tzid, \ 30 to_timezone, to_utc_datetime 31 32 def ifnone(x, y): 33 if x is None: return y 34 else: return x 35 36 class Comparable: 37 38 "A date/datetime wrapper that allows comparisons with other types." 39 40 def __init__(self, dt): 41 self.dt = dt 42 43 def __cmp__(self, other): 44 dt = None 45 odt = None 46 47 # Find any dates/datetimes. 48 49 if isinstance(self.dt, date): 50 dt = self.dt 51 if isinstance(other, date): 52 odt = other 53 elif isinstance(other, Comparable): 54 if isinstance(other.dt, date): 55 odt = other.dt 56 else: 57 other = other.dt 58 59 if dt and odt: 60 return cmp(dt, odt) 61 elif dt: 62 return other.__rcmp__(dt) 63 elif odt: 64 return self.dt.__cmp__(odt) 65 else: 66 return self.dt.__cmp__(other) 67 68 class PointInTime: 69 70 "A base class for special values." 71 72 pass 73 74 class StartOfTime(PointInTime): 75 76 "A special value that compares earlier than other values." 77 78 def __cmp__(self, other): 79 if isinstance(other, StartOfTime): 80 return 0 81 else: 82 return -1 83 84 def __rcmp__(self, other): 85 return -self.__cmp__(other) 86 87 def __nonzero__(self): 88 return False 89 90 def __hash__(self): 91 return 0 92 93 class EndOfTime(PointInTime): 94 95 "A special value that compares later than other values." 96 97 def __cmp__(self, other): 98 if isinstance(other, EndOfTime): 99 return 0 100 else: 101 return 1 102 103 def __rcmp__(self, other): 104 return -self.__cmp__(other) 105 106 def __nonzero__(self): 107 return False 108 109 def __hash__(self): 110 return 0 111 112 class Endless: 113 114 "A special value indicating an endless period." 115 116 def __cmp__(self, other): 117 if isinstance(other, Endless): 118 return 0 119 else: 120 return 1 121 122 def __rcmp__(self, other): 123 return -self.__cmp__(other) 124 125 def __nonzero__(self): 126 return True 127 128 class PeriodBase: 129 130 "A basic period abstraction." 131 132 def __init__(self, start, end): 133 if isinstance(start, (date, PointInTime)): 134 self.start = start 135 else: 136 self.start = get_datetime(start) or StartOfTime() 137 if isinstance(end, (date, PointInTime)): 138 self.end = end 139 else: 140 self.end = get_datetime(end) or EndOfTime() 141 142 def as_tuple(self): 143 return self.start, self.end 144 145 def __hash__(self): 146 return hash((self.get_start(), self.get_end())) 147 148 def __cmp__(self, other): 149 150 "Return a comparison result against 'other' using points in time." 151 152 if isinstance(other, PeriodBase): 153 return cmp( 154 (Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(self.get_end_point(), EndOfTime()))), 155 (Comparable(ifnone(other.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 156 ) 157 else: 158 return 1 159 160 def overlaps(self, other): 161 return Comparable(ifnone(self.get_end_point(), EndOfTime())) > Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 162 Comparable(ifnone(self.get_start_point(), StartOfTime())) < Comparable(ifnone(other.get_end_point(), EndOfTime())) 163 164 def within(self, other): 165 return Comparable(ifnone(self.get_start_point(), StartOfTime())) >= Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 166 Comparable(ifnone(self.get_end_point(), EndOfTime())) <= Comparable(ifnone(other.get_end_point(), EndOfTime())) 167 168 def common(self, other): 169 start = max(Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_start_point(), StartOfTime()))) 170 end = min(Comparable(ifnone(self.get_end_point(), EndOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 171 if start <= end: 172 return self.make_corrected(start.dt, end.dt) 173 else: 174 return None 175 176 def get_key(self): 177 return self.get_start(), self.get_end() 178 179 # Datetime and metadata methods. 180 181 def get_start(self): 182 return self.start 183 184 def get_end(self): 185 return self.end 186 187 def get_start_attr(self): 188 return get_datetime_attributes(self.start, self.tzid) 189 190 def get_end_attr(self): 191 return get_datetime_attributes(self.end, self.tzid) 192 193 def get_start_item(self): 194 return self.get_start(), self.get_start_attr() 195 196 def get_end_item(self): 197 return self.get_end(), self.get_end_attr() 198 199 def get_start_point(self): 200 return self.start 201 202 def get_end_point(self): 203 return self.end 204 205 def get_duration(self): 206 start = self.get_start_point() 207 end = self.get_end_point() 208 if start and end: 209 return end - start 210 else: 211 return Endless() 212 213 class Period(PeriodBase): 214 215 "A simple period abstraction." 216 217 def __init__(self, start, end, tzid=None, origin=None): 218 219 """ 220 Initialise a period with the given 'start' and 'end', having a 221 contextual 'tzid', if specified, and an indicated 'origin'. 222 223 All metadata from the start and end points are derived from the supplied 224 dates/datetimes. 225 """ 226 227 PeriodBase.__init__(self, start, end) 228 self.tzid = tzid 229 self.origin = origin 230 231 def as_tuple(self): 232 return self.start, self.end, self.tzid, self.origin 233 234 def __repr__(self): 235 return "Period%r" % (self.as_tuple(),) 236 237 # Datetime and metadata methods. 238 239 def get_tzid(self): 240 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 241 242 def get_start_point(self): 243 start = self.get_start() 244 if isinstance(start, PointInTime): return start 245 else: return to_utc_datetime(start, self.get_tzid()) 246 247 def get_end_point(self): 248 end = self.get_end() 249 if isinstance(end, PointInTime): return end 250 else: return to_utc_datetime(end, self.get_tzid()) 251 252 # Period and event recurrence logic. 253 254 def is_replaced(self, recurrenceids): 255 256 """ 257 Return whether this period refers to one of the 'recurrenceids'. 258 The 'recurrenceids' should be normalised to UTC datetimes according to 259 time zone information provided by their objects or be floating dates or 260 datetimes requiring conversion using contextual time zone information. 261 """ 262 263 for recurrenceid in recurrenceids: 264 if self.is_affected(recurrenceid): 265 return recurrenceid 266 return None 267 268 def is_affected(self, recurrenceid): 269 270 """ 271 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 272 should be normalised to UTC datetimes according to time zone information 273 provided by their objects. Otherwise, this period's contextual time zone 274 information is used to convert any date or floating datetime 275 representation to a point in time. 276 """ 277 278 if not recurrenceid: 279 return None 280 d = get_recurrence_start(recurrenceid) 281 dt = get_recurrence_start_point(recurrenceid, self.tzid) 282 if self.get_start() == d or self.get_start_point() == dt: 283 return recurrenceid 284 return None 285 286 # Value correction methods. 287 288 def with_duration(self, duration): 289 290 """ 291 Return a version of this period with the same start point but with the 292 given 'duration'. 293 """ 294 295 return self.make_corrected(self.get_start(), self.get_start() + duration) 296 297 def check_permitted(self, permitted_values): 298 299 "Check the period against the given 'permitted_values'." 300 301 start = self.get_start() 302 end = self.get_end() 303 start_errors = check_permitted_values(start, permitted_values) 304 end_errors = check_permitted_values(end, permitted_values) 305 306 if not (start_errors or end_errors): 307 return None 308 309 return start_errors, end_errors 310 311 def get_corrected(self, permitted_values): 312 313 "Return a corrected version of this period." 314 315 errors = self.check_permitted(permitted_values) 316 317 if not errors: 318 return self 319 320 start_errors, end_errors = errors 321 322 start = self.get_start() 323 end = self.get_end() 324 325 if start_errors: 326 start = correct_datetime(start, permitted_values) 327 if end_errors: 328 end = correct_datetime(end, permitted_values) 329 330 return self.make_corrected(start, end) 331 332 def make_corrected(self, start, end): 333 return self.__class__(start, end, self.tzid, self.origin) 334 335 class FreeBusyPeriod(PeriodBase): 336 337 "A free/busy record abstraction." 338 339 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None): 340 341 """ 342 Initialise a free/busy period with the given 'start' and 'end' points, 343 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 344 details. 345 346 An additional 'expires' parameter can be used to indicate an expiry 347 datetime in conjunction with free/busy offers made when countering 348 event proposals. 349 """ 350 351 PeriodBase.__init__(self, start, end) 352 self.uid = uid 353 self.transp = transp 354 self.recurrenceid = recurrenceid 355 self.summary = summary 356 self.organiser = organiser 357 self.expires = expires 358 359 def as_tuple(self, strings_only=False): 360 361 """ 362 Return the initialisation parameter tuple, converting false value 363 parameters to strings if 'strings_only' is set to a true value. 364 """ 365 366 null = lambda x: (strings_only and [""] or [x])[0] 367 return ( 368 strings_only and format_datetime(self.get_start_point()) or self.start, 369 strings_only and format_datetime(self.get_end_point()) or self.end, 370 self.uid or null(self.uid), 371 self.transp or strings_only and "OPAQUE" or None, 372 self.recurrenceid or null(self.recurrenceid), 373 self.summary or null(self.summary), 374 self.organiser or null(self.organiser), 375 self.expires or null(self.expires) 376 ) 377 378 def __cmp__(self, other): 379 380 """ 381 Compare this object to 'other', employing the uid if the periods 382 involved are the same. 383 """ 384 385 result = PeriodBase.__cmp__(self, other) 386 if result == 0 and isinstance(other, FreeBusyPeriod): 387 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 388 else: 389 return result 390 391 def get_key(self): 392 return self.uid, self.recurrenceid, self.get_start() 393 394 def __repr__(self): 395 return "FreeBusyPeriod%r" % (self.as_tuple(),) 396 397 def get_tzid(self): 398 return "UTC" 399 400 # Period and event recurrence logic. 401 402 def is_replaced(self, recurrences): 403 404 """ 405 Return whether this period refers to one of the 'recurrences'. 406 The 'recurrences' must be UTC datetimes corresponding to the start of 407 the period described by a recurrence. 408 """ 409 410 for recurrence in recurrences: 411 if self.is_affected(recurrence): 412 return True 413 return False 414 415 def is_affected(self, recurrence): 416 417 """ 418 Return whether this period refers to 'recurrence'. The 'recurrence' must 419 be a UTC datetime corresponding to the start of the period described by 420 a recurrence. 421 """ 422 423 return recurrence and self.get_start_point() == recurrence 424 425 # Value correction methods. 426 427 def make_corrected(self, start, end): 428 return self.__class__(start, end) 429 430 class RecurringPeriod(Period): 431 432 """ 433 A period with iCalendar metadata attributes and origin information from an 434 object. 435 """ 436 437 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 438 Period.__init__(self, start, end, tzid, origin) 439 self.start_attr = start_attr 440 self.end_attr = end_attr 441 442 def get_start_attr(self): 443 return self.start_attr 444 445 def get_end_attr(self): 446 return self.end_attr 447 448 def as_tuple(self): 449 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 450 451 def __repr__(self): 452 return "RecurringPeriod%r" % (self.as_tuple(),) 453 454 def make_corrected(self, start, end): 455 return self.__class__(start, end, self.tzid, self.origin, self.get_start_attr(), self.get_end_attr()) 456 457 class FreeBusyCollectionBase: 458 459 "Common operations on free/busy period collections." 460 461 # List emulation methods. 462 463 def __iadd__(self, other): 464 for period in other: 465 self.insert_period(period) 466 return self 467 468 # Operations. 469 470 def can_schedule(self, periods, uid, recurrenceid): 471 472 """ 473 Return whether the collection can accommodate the given 'periods' 474 employing the specified 'uid' and 'recurrenceid'. 475 """ 476 477 for conflict in self.have_conflict(periods, True): 478 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 479 return False 480 481 return True 482 483 def have_conflict(self, periods, get_conflicts=False): 484 485 """ 486 Return whether any period in the collection overlaps with the given 487 'periods', returning a collection of such overlapping periods if 488 'get_conflicts' is set to a true value. 489 """ 490 491 conflicts = set() 492 for p in periods: 493 overlapping = self.period_overlaps(p, get_conflicts) 494 if overlapping: 495 if get_conflicts: 496 conflicts.update(overlapping) 497 else: 498 return True 499 500 if get_conflicts: 501 return conflicts 502 else: 503 return False 504 505 def period_overlaps(self, period, get_periods=False): 506 507 """ 508 Return whether any period in the collection overlaps with the given 509 'period', returning a collection of overlapping periods if 'get_periods' 510 is set to a true value. 511 """ 512 513 overlapping = self.get_overlapping(period) 514 515 if get_periods: 516 return overlapping 517 else: 518 return len(overlapping) != 0 519 520 def replace_overlapping(self, period, replacements): 521 522 """ 523 Replace existing periods in the collection within the given 'period', 524 using the given 'replacements'. 525 """ 526 527 self.remove_overlapping(period) 528 for replacement in replacements: 529 self.insert_period(replacement) 530 531 def coalesce_freebusy(self): 532 533 "Coalesce the periods in the collection, returning a new collection." 534 535 if not self: 536 return FreeBusyCollection() 537 538 fb = [] 539 540 it = iter(self) 541 period = it.next() 542 543 start = period.get_start_point() 544 end = period.get_end_point() 545 546 try: 547 while True: 548 period = it.next() 549 if period.get_start_point() > end: 550 fb.append(FreeBusyPeriod(start, end)) 551 start = period.get_start_point() 552 end = period.get_end_point() 553 else: 554 end = max(end, period.get_end_point()) 555 except StopIteration: 556 pass 557 558 fb.append(FreeBusyPeriod(start, end)) 559 return FreeBusyCollection(fb) 560 561 def invert_freebusy(self): 562 563 "Return the free periods from the collection as a new collection." 564 565 if not self: 566 return FreeBusyCollection([FreeBusyPeriod(None, None)]) 567 568 # Coalesce periods that overlap or are adjacent. 569 570 fb = self.coalesce_freebusy() 571 free = [] 572 573 # Add a start-of-time period if appropriate. 574 575 first = fb[0].get_start_point() 576 if first: 577 free.append(FreeBusyPeriod(None, first)) 578 579 start = fb[0].get_end_point() 580 581 for period in fb[1:]: 582 free.append(FreeBusyPeriod(start, period.get_start_point())) 583 start = period.get_end_point() 584 585 # Add an end-of-time period if appropriate. 586 587 if start: 588 free.append(FreeBusyPeriod(start, None)) 589 590 return FreeBusyCollection(free) 591 592 def update_freebusy(self, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 593 594 """ 595 Update the free/busy details with the given 'periods', 'transp' setting, 596 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 597 598 An optional 'expires' datetime string indicates the expiry time of any 599 free/busy offer. 600 """ 601 602 self.remove_event_periods(uid, recurrenceid) 603 604 for p in periods: 605 self.insert_period(FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 606 607 class FreeBusyCollection(FreeBusyCollectionBase): 608 609 "An abstraction for a collection of free/busy periods." 610 611 def __init__(self, periods=None): 612 613 """ 614 Initialise the collection with the given list of 'periods', or start an 615 empty collection if no list is given. 616 """ 617 618 self.periods = periods or [] 619 620 # List emulation methods. 621 622 def __nonzero__(self): 623 return bool(self.periods) 624 625 def __iter__(self): 626 return iter(self.periods) 627 628 def __len__(self): 629 return len(self.periods) 630 631 def __getitem__(self, i): 632 return self.periods[i] 633 634 # Operations. 635 636 def insert_period(self, period): 637 638 "Insert the given 'period' into the collection." 639 640 i = bisect_left(self.periods, period) 641 if i == len(self.periods): 642 self.periods.append(period) 643 elif self.periods[i] != period: 644 self.periods.insert(i, period) 645 646 def remove_periods(self, periods): 647 648 "Remove the given 'periods' from the collection." 649 650 for period in periods: 651 i = bisect_left(self.periods, period) 652 if i < len(self.periods) and self.periods[i] == period: 653 del self.periods[i] 654 655 def remove_event_periods(self, uid, recurrenceid=None): 656 657 """ 658 Remove from the collection all periods associated with 'uid' and 659 'recurrenceid' (which if omitted causes the "parent" object's periods to 660 be referenced). 661 662 Return the removed periods. 663 """ 664 665 removed = [] 666 i = 0 667 while i < len(self.periods): 668 fb = self.periods[i] 669 if fb.uid == uid and fb.recurrenceid == recurrenceid: 670 removed.append(self.periods[i]) 671 del self.periods[i] 672 else: 673 i += 1 674 675 return removed 676 677 def remove_additional_periods(self, uid, recurrenceids=None): 678 679 """ 680 Remove from the collection all periods associated with 'uid' having a 681 recurrence identifier indicating an additional or modified period. 682 683 If 'recurrenceids' is specified, remove all periods associated with 684 'uid' that do not have a recurrence identifier in the given list. 685 686 Return the removed periods. 687 """ 688 689 removed = [] 690 i = 0 691 while i < len(self.periods): 692 fb = self.periods[i] 693 if fb.uid == uid and fb.recurrenceid and ( 694 recurrenceids is None or 695 recurrenceids is not None and fb.recurrenceid not in recurrenceids 696 ): 697 removed.append(self.periods[i]) 698 del self.periods[i] 699 else: 700 i += 1 701 702 return removed 703 704 def remove_affected_period(self, uid, start): 705 706 """ 707 Remove from the collection the period associated with 'uid' that 708 provides an occurrence starting at the given 'start' (provided by a 709 recurrence identifier, converted to a datetime). A recurrence identifier 710 is used to provide an alternative time period whilst also acting as a 711 reference to the originally-defined occurrence. 712 713 Return any removed period in a list. 714 """ 715 716 removed = [] 717 718 search = Period(start, start) 719 found = bisect_left(self.periods, search) 720 721 while found < len(self.periods): 722 fb = self.periods[found] 723 724 # Stop looking if the start no longer matches the recurrence identifier. 725 726 if fb.get_start_point() != search.get_start_point(): 727 break 728 729 # If the period belongs to the parent object, remove it and return. 730 731 if not fb.recurrenceid and uid == fb.uid: 732 removed.append(self.periods[found]) 733 del self.periods[found] 734 break 735 736 # Otherwise, keep looking for a matching period. 737 738 found += 1 739 740 return removed 741 742 def periods_from(self, period): 743 744 "Return the entries in the collection at or after 'period'." 745 746 first = bisect_left(self.periods, period) 747 return self.periods[first:] 748 749 def periods_until(self, period): 750 751 "Return the entries in the collection before 'period'." 752 753 last = bisect_right(self.periods, Period(period.get_end(), period.get_end(), period.get_tzid())) 754 return self.periods[:last] 755 756 def get_overlapping(self, period): 757 758 """ 759 Return the entries in the collection providing periods overlapping with 760 'period'. 761 """ 762 763 # Find the range of periods potentially overlapping the period in the 764 # free/busy collection. 765 766 startpoints = self.periods_until(period) 767 768 # Find the range of periods potentially overlapping the period in a version 769 # of the free/busy collection sorted according to end datetimes. 770 771 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 772 endpoints.sort() 773 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 774 endpoints = endpoints[first:] 775 776 overlapping = set() 777 778 for p, fb in endpoints: 779 if fb.overlaps(period): 780 overlapping.add(fb) 781 782 overlapping = list(overlapping) 783 overlapping.sort() 784 return overlapping 785 786 def remove_overlapping(self, period): 787 788 "Remove all periods overlapping with 'period' from the collection." 789 790 overlapping = self.get_overlapping(period) 791 792 if overlapping: 793 for fb in overlapping: 794 self.periods.remove(fb) 795 796 class FreeBusyDatabaseCollection(FreeBusyCollectionBase): 797 798 """ 799 An abstraction for a collection of free/busy periods stored in a database 800 system. 801 """ 802 803 def __init__(self, cursor, table_name): 804 805 """ 806 Initialise the collection with the given 'cursor' and 'table_name'. 807 """ 808 809 self.cursor = cursor 810 self.table_name = table_name 811 812 # Special database-related operations. 813 814 def placeholders(self, values): 815 return ", ".join(["?"] * len(values)) 816 817 def initialise(self): 818 819 "Create the database table required to hold the collection." 820 821 query = """\ 822 create table %(table)s ( 823 start varchar not null, 824 end varchar not null, 825 uid varchar, 826 transp varchar, 827 recurrenceid varchar, 828 summary varchar, 829 organiser varchar, 830 expires varchar 831 )""" % {"table" : self.table_name} 832 833 self.cursor.execute(query) 834 835 # List emulation methods. 836 837 def __nonzero__(self): 838 query = "select count(*) from %(table)s" % {"table" : self.table_name} 839 self.cursor.execute(query) 840 result = self.cursor.fetchone() 841 return result[0] 842 843 def __iter__(self): 844 query = "select * from %(table)s" % {"table" : self.table_name} 845 self.cursor.execute(query) 846 return iter(map(lambda t: FreeBusyPeriod(*t), self.cursor.fetchall())) 847 848 def __len__(self): 849 return len(list(iter(self))) 850 851 def __getitem__(self, i): 852 return list(iter(self))[i] 853 854 # Operations. 855 856 def insert_period(self, period): 857 858 "Insert the given 'period' into the collection." 859 860 values = period.as_tuple(strings_only=True) 861 query = "insert into %(table)s values (%(columns)s)" % { 862 "table" : self.table_name, 863 "columns" : self.placeholders(values) 864 } 865 self.cursor.execute(query, values) 866 867 def remove_periods(self, periods): 868 869 "Remove the given 'periods' from the collection." 870 871 for period in periods: 872 values = period.as_tuple(strings_only=True) 873 query = """\ 874 delete from %(table)s 875 where start = ? and end = ? and uid = ? and transp = ? and recurrenceid = ? and summary = ? and organiser = ? and expires = ? 876 """ % {"table" : self.table_name} 877 self.cursor.execute(query, values) 878 879 def remove_event_periods(self, uid, recurrenceid=None): 880 881 """ 882 Remove from the collection all periods associated with 'uid' and 883 'recurrenceid' (which if omitted causes the "parent" object's periods to 884 be referenced). 885 886 Return the removed periods. 887 """ 888 889 if recurrenceid: 890 condition = "where uid = ? and recurrenceid = ?" 891 values = (uid, recurrenceid) 892 else: 893 condition = "where uid = ?" 894 values = (uid,) 895 896 query = "select * from %(table)s for update %(condition)s" % { 897 "table" : self.table_name, 898 "condition" : condition 899 } 900 self.cursor.execute(query, values) 901 removed = self.cursor.fetchall() 902 903 query = "delete from %(table)s %(condition)s" % { 904 "table" : self.table_name, 905 "condition" : condition 906 } 907 self.cursor.execute(query, values) 908 909 return map(lambda t: FreeBusyPeriod(*t), removed) 910 911 def remove_additional_periods(self, uid, recurrenceids=None): 912 913 """ 914 Remove from the collection all periods associated with 'uid' having a 915 recurrence identifier indicating an additional or modified period. 916 917 If 'recurrenceids' is specified, remove all periods associated with 918 'uid' that do not have a recurrence identifier in the given list. 919 920 Return the removed periods. 921 """ 922 923 if recurrenceids is None: 924 condition = "where uid = ? and recurrenceid is not null" 925 values = (uid,) 926 else: 927 condition = "where uid = ? and recurrenceid is not null and recurrenceid not in ?" 928 values = (uid, recurrenceid) 929 930 query = "select * from %(table)s for update %(condition)s" % { 931 "table" : self.table_name, 932 "condition" : condition 933 } 934 self.cursor.execute(query, values) 935 removed = self.cursor.fetchall() 936 937 query = "delete from %(table)s %(condition)s" % { 938 "table" : self.table_name, 939 "condition" : condition 940 } 941 self.cursor.execute(query, values) 942 943 return map(lambda t: FreeBusyPeriod(*t), removed) 944 945 def remove_affected_period(self, uid, start): 946 947 """ 948 Remove from the collection the period associated with 'uid' that 949 provides an occurrence starting at the given 'start' (provided by a 950 recurrence identifier, converted to a datetime). A recurrence identifier 951 is used to provide an alternative time period whilst also acting as a 952 reference to the originally-defined occurrence. 953 954 Return any removed period in a list. 955 """ 956 957 condition = "where uid = ? and start = ? and recurrenceid is null" 958 values = (uid, start) 959 960 query = "select * from %(table)s %(condition)s" % { 961 "table" : self.table_name, 962 "condition" : condition 963 } 964 self.cursor.execute(query, values) 965 removed = self.cursor.fetchall() 966 967 query = "delete from %(table)s %(condition)s" % { 968 "table" : self.table_name, 969 "condition" : condition 970 } 971 self.cursor.execute(query, values) 972 973 return map(lambda t: FreeBusyPeriod(*t), removed) 974 975 def periods_from(self, period): 976 977 "Return the entries in the collection at or after 'period'." 978 979 condition = "where start >= ?" 980 values = (format_datetime(period.get_start_point()),) 981 982 query = "select * from %(table)s %(condition)s" % { 983 "table" : self.table_name, 984 "condition" : condition 985 } 986 self.cursor.execute(query, values) 987 988 return map(lambda t: FreeBusyPeriod(*t), self.cursor.fetchall()) 989 990 def periods_until(self, period): 991 992 "Return the entries in the collection before 'period'." 993 994 condition = "where start < ?" 995 values = (format_datetime(period.get_end_point()),) 996 997 query = "select * from %(table)s %(condition)s" % { 998 "table" : self.table_name, 999 "condition" : condition 1000 } 1001 self.cursor.execute(query, values) 1002 1003 return map(lambda t: FreeBusyPeriod(*t), self.cursor.fetchall()) 1004 1005 def get_overlapping(self, period): 1006 1007 """ 1008 Return the entries in the collection providing periods overlapping with 1009 'period'. 1010 """ 1011 1012 condition = "where start < ? and end > ?" 1013 values = (format_datetime(period.get_end_point()), format_datetime(period.get_start_point())) 1014 1015 query = "select * from %(table)s %(condition)s" % { 1016 "table" : self.table_name, 1017 "condition" : condition 1018 } 1019 self.cursor.execute(query, values) 1020 1021 return map(lambda t: FreeBusyPeriod(*t), self.cursor.fetchall()) 1022 1023 def remove_overlapping(self, period): 1024 1025 "Remove all periods overlapping with 'period' from the collection." 1026 1027 condition = "where start < ? and end > ?" 1028 values = (format_datetime(period.get_end_point()), format_datetime(period.get_start_point())) 1029 1030 query = "delete from %(table)s %(condition)s" % { 1031 "table" : self.table_name, 1032 "condition" : condition 1033 } 1034 self.cursor.execute(query, values) 1035 1036 # Period layout. 1037 1038 def get_scale(periods, tzid, view_period=None): 1039 1040 """ 1041 Return a time scale from the given list of 'periods'. 1042 1043 The given 'tzid' is used to make sure that the times are defined according 1044 to the chosen time zone. 1045 1046 An optional 'view_period' is used to constrain the scale to the given 1047 period. 1048 1049 The returned scale is a mapping from time to (starting, ending) tuples, 1050 where starting and ending are collections of periods. 1051 """ 1052 1053 scale = {} 1054 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 1055 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 1056 1057 for p in periods: 1058 1059 # Add a point and this event to the starting list. 1060 1061 start = to_timezone(p.get_start(), tzid) 1062 start = view_start and max(start, view_start) or start 1063 if not scale.has_key(start): 1064 scale[start] = [], [] 1065 scale[start][0].append(p) 1066 1067 # Add a point and this event to the ending list. 1068 1069 end = to_timezone(p.get_end(), tzid) 1070 end = view_end and min(end, view_end) or end 1071 if not scale.has_key(end): 1072 scale[end] = [], [] 1073 scale[end][1].append(p) 1074 1075 return scale 1076 1077 class Point: 1078 1079 "A qualified point in time." 1080 1081 PRINCIPAL, REPEATED = 0, 1 1082 1083 def __init__(self, point, indicator=None): 1084 self.point = point 1085 self.indicator = indicator or self.PRINCIPAL 1086 1087 def __hash__(self): 1088 return hash((self.point, self.indicator)) 1089 1090 def __cmp__(self, other): 1091 if isinstance(other, Point): 1092 return cmp((self.point, self.indicator), (other.point, other.indicator)) 1093 elif isinstance(other, datetime): 1094 return cmp(self.point, other) 1095 else: 1096 return 1 1097 1098 def __eq__(self, other): 1099 return self.__cmp__(other) == 0 1100 1101 def __ne__(self, other): 1102 return not self == other 1103 1104 def __lt__(self, other): 1105 return self.__cmp__(other) < 0 1106 1107 def __le__(self, other): 1108 return self.__cmp__(other) <= 0 1109 1110 def __gt__(self, other): 1111 return not self <= other 1112 1113 def __ge__(self, other): 1114 return not self < other 1115 1116 def __repr__(self): 1117 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 1118 1119 def get_slots(scale): 1120 1121 """ 1122 Return an ordered list of time slots from the given 'scale'. 1123 1124 Each slot is a tuple containing details of a point in time for the start of 1125 the slot, together with a list of parallel event periods. 1126 1127 Each point in time is described as a Point representing the actual point in 1128 time together with an indicator of the nature of the point in time (as a 1129 principal point in a time scale or as a repeated point used to terminate 1130 events occurring for an instant in time). 1131 """ 1132 1133 slots = [] 1134 active = [] 1135 1136 points = scale.items() 1137 points.sort() 1138 1139 for point, (starting, ending) in points: 1140 ending = set(ending) 1141 instants = ending.intersection(starting) 1142 1143 # Discard all active events ending at or before this start time. 1144 # Free up the position in the active list. 1145 1146 for t in ending.difference(instants): 1147 i = active.index(t) 1148 active[i] = None 1149 1150 # For each event starting at the current point, fill any newly-vacated 1151 # position or add to the end of the active list. 1152 1153 for t in starting: 1154 try: 1155 i = active.index(None) 1156 active[i] = t 1157 except ValueError: 1158 active.append(t) 1159 1160 # Discard vacant positions from the end of the active list. 1161 1162 while active and active[-1] is None: 1163 active.pop() 1164 1165 # Add an entry for the time point before "instants". 1166 1167 slots.append((Point(point), active[:])) 1168 1169 # Discard events ending at the same time as they began. 1170 1171 if instants: 1172 for t in instants: 1173 i = active.index(t) 1174 active[i] = None 1175 1176 # Discard vacant positions from the end of the active list. 1177 1178 while active and active[-1] is None: 1179 active.pop() 1180 1181 # Add another entry for the time point after "instants". 1182 1183 slots.append((Point(point, Point.REPEATED), active[:])) 1184 1185 return slots 1186 1187 def add_day_start_points(slots, tzid): 1188 1189 """ 1190 Introduce into the 'slots' any day start points required by multi-day 1191 periods. The 'tzid' is required to make sure that appropriate time zones 1192 are chosen and not necessarily those provided by the existing time points. 1193 """ 1194 1195 new_slots = [] 1196 current_date = None 1197 previously_active = [] 1198 1199 for point, active in slots: 1200 start_of_day = get_start_of_day(point.point, tzid) 1201 this_date = point.point.date() 1202 1203 # For each new day, add a slot for the start of the day where periods 1204 # are active and where no such slot already exists. 1205 1206 if this_date != current_date: 1207 1208 # Fill in days where events remain active. 1209 1210 if current_date: 1211 current_date += timedelta(1) 1212 while current_date < this_date: 1213 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 1214 current_date += timedelta(1) 1215 else: 1216 current_date = this_date 1217 1218 # Add any continuing periods. 1219 1220 if point.point != start_of_day: 1221 new_slots.append((Point(start_of_day), previously_active)) 1222 1223 # Add the currently active periods at this point in time. 1224 1225 previously_active = active 1226 1227 for t in new_slots: 1228 insort_left(slots, t) 1229 1230 def remove_end_slot(slots, view_period): 1231 1232 """ 1233 Remove from 'slots' any slot situated at the end of the given 'view_period'. 1234 """ 1235 1236 end = view_period.get_end_point() 1237 if not end or not slots: 1238 return 1239 i = bisect_left(slots, (Point(end), None)) 1240 if i < len(slots): 1241 del slots[i:] 1242 1243 def add_slots(slots, points): 1244 1245 """ 1246 Introduce into the 'slots' entries for those in 'points' that are not 1247 already present, propagating active periods from time points preceding 1248 those added. 1249 """ 1250 1251 new_slots = [] 1252 1253 for point in points: 1254 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 1255 if i < len(slots) and slots[i][0] == point: 1256 continue 1257 1258 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 1259 1260 for t in new_slots: 1261 insort_left(slots, t) 1262 1263 def partition_by_day(slots): 1264 1265 """ 1266 Return a mapping from dates to time points provided by 'slots'. 1267 """ 1268 1269 d = {} 1270 1271 for point, value in slots: 1272 day = point.point.date() 1273 if not d.has_key(day): 1274 d[day] = [] 1275 d[day].append((point, value)) 1276 1277 return d 1278 1279 def add_empty_days(days, tzid, start=None, end=None): 1280 1281 """ 1282 Add empty days to 'days' between busy days, and optionally from the given 1283 'start' day and until the given 'end' day. 1284 """ 1285 1286 last_day = start - timedelta(1) 1287 all_days = days.keys() 1288 all_days.sort() 1289 1290 for day in all_days: 1291 if last_day: 1292 empty_day = last_day + timedelta(1) 1293 while empty_day < day: 1294 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1295 empty_day += timedelta(1) 1296 last_day = day 1297 1298 if end: 1299 empty_day = last_day + timedelta(1) 1300 while empty_day < end: 1301 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 1302 empty_day += timedelta(1) 1303 1304 def get_spans(slots): 1305 1306 "Inspect the given 'slots', returning a mapping of period keys to spans." 1307 1308 points = [point for point, active in slots] 1309 spans = {} 1310 1311 for _point, active in slots: 1312 for p in active: 1313 if p: 1314 key = p.get_key() 1315 start_slot = bisect_left(points, p.get_start()) 1316 end_slot = bisect_left(points, p.get_end()) 1317 spans[key] = end_slot - start_slot 1318 1319 return spans 1320 1321 # vim: tabstop=4 expandtab shiftwidth=4