1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015 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 format_datetime, get_datetime, \ 25 get_datetime_attributes, \ 26 get_recurrence_start, get_recurrence_start_point, \ 27 get_start_of_day, \ 28 get_tzid, \ 29 to_timezone, to_utc_datetime 30 31 class PeriodBase: 32 33 "A basic period abstraction." 34 35 def as_tuple(self): 36 return self.start, self.end 37 38 def __hash__(self): 39 return hash((self.get_start(), self.get_end())) 40 41 def __cmp__(self, other): 42 43 "Return a comparison result against 'other' using points in time." 44 45 if isinstance(other, PeriodBase): 46 return cmp( 47 (self.get_start_point(), self.get_end_point()), 48 (other.get_start_point(), other.get_end_point()) 49 ) 50 else: 51 return 1 52 53 def get_key(self): 54 return self.get_start(), self.get_end() 55 56 # Datetime and metadata methods. 57 58 def get_start(self): 59 return self.start 60 61 def get_end(self): 62 return self.end 63 64 def get_start_attr(self): 65 return get_datetime_attributes(self.start, self.tzid) 66 67 def get_end_attr(self): 68 return get_datetime_attributes(self.end, self.tzid) 69 70 def get_start_item(self): 71 return self.get_start(), self.get_start_attr() 72 73 def get_end_item(self): 74 return self.get_end(), self.get_end_attr() 75 76 def get_start_point(self): 77 return self.start 78 79 def get_end_point(self): 80 return self.end 81 82 class Period(PeriodBase): 83 84 "A simple period abstraction." 85 86 def __init__(self, start, end, tzid=None, origin=None): 87 88 """ 89 Initialise a period with the given 'start' and 'end', having a 90 contextual 'tzid', if specified, and an indicated 'origin'. 91 92 All metadata from the start and end points are derived from the supplied 93 dates/datetimes. 94 """ 95 96 self.start = isinstance(start, date) and start or get_datetime(start) 97 self.end = isinstance(end, date) and end or get_datetime(end) 98 self.tzid = tzid 99 self.origin = origin 100 101 def as_tuple(self): 102 return self.start, self.end, self.tzid, self.origin 103 104 def __repr__(self): 105 return "Period%r" % (self.as_tuple(),) 106 107 # Datetime and metadata methods. 108 109 def get_tzid(self): 110 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 111 112 def get_start_point(self): 113 return to_utc_datetime(self.get_start(), self.get_tzid()) 114 115 def get_end_point(self): 116 return to_utc_datetime(self.get_end(), self.get_tzid()) 117 118 # Period and event recurrence logic. 119 120 def is_replaced(self, recurrenceids): 121 122 """ 123 Return whether this period refers to one of the 'recurrenceids'. 124 The 'recurrenceids' should be normalised to UTC datetimes according to 125 time zone information provided by their objects or be floating dates or 126 datetimes requiring conversion using contextual time zone information. 127 """ 128 129 for recurrenceid in recurrenceids: 130 if self.is_affected(period, recurrenceid): 131 return recurrenceid 132 return None 133 134 def is_affected(self, recurrenceid): 135 136 """ 137 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 138 should be normalised to UTC datetimes according to time zone information 139 provided by their objects. Otherwise, this period's contextual time zone 140 information is used to convert any date or floating datetime 141 representation to a point in time. 142 """ 143 144 if not recurrenceid: 145 return None 146 d = get_recurrence_start(recurrenceid) 147 dt = get_recurrence_start_point(recurrenceid, self.tzid) 148 if self.get_start() == d or self.get_start_point() == dt: 149 return recurrenceid 150 return None 151 152 class FreeBusyPeriod(PeriodBase): 153 154 "A free/busy record abstraction." 155 156 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None): 157 158 """ 159 Initialise a free/busy period with the given 'start' and 'end' points, 160 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 161 details. 162 """ 163 164 self.start = isinstance(start, datetime) and start or get_datetime(start) 165 self.end = isinstance(end, datetime) and end or get_datetime(end) 166 self.uid = uid 167 self.transp = transp 168 self.recurrenceid = recurrenceid 169 self.summary = summary 170 self.organiser = organiser 171 172 def as_tuple(self, strings_only=False): 173 174 """ 175 Return the initialisation parameter tuple, converting false value 176 parameters to strings if 'strings_only' is set to a true value. 177 """ 178 179 null = lambda x: (strings_only and [""] or [x])[0] 180 return ( 181 strings_only and format_datetime(self.get_start_point()) or self.start, 182 strings_only and format_datetime(self.get_end_point()) or self.end, 183 self.uid or null(self.uid), 184 self.transp or strings_only and "OPAQUE" or None, 185 self.recurrenceid or null(self.recurrenceid), 186 self.summary or null(self.summary), 187 self.organiser or null(self.organiser) 188 ) 189 190 def __cmp__(self, other): 191 192 """ 193 Compare this object to 'other', employing the uid if the periods 194 involved are the same. 195 """ 196 197 result = PeriodBase.__cmp__(self, other) 198 if result == 0 and isinstance(other, FreeBusyPeriod): 199 return cmp(self.uid, other.uid) 200 else: 201 return result 202 203 def get_key(self): 204 return self.uid, self.recurrenceid, self.get_start() 205 206 def __repr__(self): 207 return "FreeBusyPeriod%r" % (self.as_tuple(),) 208 209 class RecurringPeriod(Period): 210 211 """ 212 A period with iCalendar metadata attributes and origin information from an 213 object. 214 """ 215 216 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 217 Period.__init__(self, start, end, tzid, origin) 218 self.start_attr = start_attr 219 self.end_attr = end_attr 220 221 def get_start_attr(self): 222 return self.start_attr 223 224 def get_end_attr(self): 225 return self.end_attr 226 227 def as_tuple(self): 228 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 229 230 def __repr__(self): 231 return "RecurringPeriod%r" % (self.as_tuple(),) 232 233 # Time and period management. 234 235 def can_schedule(freebusy, periods, uid, recurrenceid): 236 237 """ 238 Return whether the 'freebusy' list can accommodate the given 'periods' 239 employing the specified 'uid' and 'recurrenceid'. 240 """ 241 242 for conflict in have_conflict(freebusy, periods, True): 243 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 244 return False 245 246 return True 247 248 def have_conflict(freebusy, periods, get_conflicts=False): 249 250 """ 251 Return whether any period in 'freebusy' overlaps with the given 'periods', 252 returning a collection of such overlapping periods if 'get_conflicts' is 253 set to a true value. 254 """ 255 256 conflicts = set() 257 for p in periods: 258 overlapping = period_overlaps(freebusy, p, get_conflicts) 259 if overlapping: 260 if get_conflicts: 261 conflicts.update(overlapping) 262 else: 263 return True 264 265 if get_conflicts: 266 return conflicts 267 else: 268 return False 269 270 def insert_period(freebusy, period): 271 272 "Insert into 'freebusy' the given 'period'." 273 274 insort_left(freebusy, period) 275 276 def remove_period(freebusy, uid, recurrenceid=None): 277 278 """ 279 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 280 (which if omitted causes the "parent" object's periods to be referenced). 281 """ 282 283 removed = False 284 i = 0 285 while i < len(freebusy): 286 fb = freebusy[i] 287 if fb.uid == uid and fb.recurrenceid == recurrenceid: 288 del freebusy[i] 289 removed = True 290 else: 291 i += 1 292 293 return removed 294 295 def remove_additional_periods(freebusy, uid, recurrenceids=None): 296 297 """ 298 Remove from 'freebusy' all periods associated with 'uid' having a 299 recurrence identifier indicating an additional or modified period. 300 301 If 'recurrenceids' is specified, remove all periods associated with 'uid' 302 that do not have a recurrence identifier in the given list. 303 """ 304 305 i = 0 306 while i < len(freebusy): 307 fb = freebusy[i] 308 if fb.uid == uid and fb.recurrenceid and ( 309 recurrenceids is None or 310 recurrenceids is not None and fb.recurrenceid not in recurrenceids 311 ): 312 del freebusy[i] 313 else: 314 i += 1 315 316 def remove_affected_period(freebusy, uid, start): 317 318 """ 319 Remove from 'freebusy' a period associated with 'uid' that provides an 320 occurrence starting at the given 'start' (provided by a recurrence 321 identifier, converted to a datetime). A recurrence identifier is used to 322 provide an alternative time period whilst also acting as a reference to the 323 originally-defined occurrence. 324 """ 325 326 search = Period(start, start) 327 found = bisect_left(freebusy, search) 328 329 while found < len(freebusy): 330 fb = freebusy[found] 331 332 # Stop looking if the start no longer matches the recurrence identifier. 333 334 if fb.get_start_point() != search.get_start_point(): 335 return 336 337 # If the period belongs to the parent object, remove it and return. 338 339 if not fb.recurrenceid and uid == fb.uid: 340 del freebusy[found] 341 break 342 343 # Otherwise, keep looking for a matching period. 344 345 found += 1 346 347 def get_overlapping(freebusy, period): 348 349 """ 350 Return the entries in 'freebusy' providing periods overlapping with 351 'period'. 352 """ 353 354 # Find the range of periods potentially overlapping the period in the 355 # free/busy collection. 356 357 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.tzid)) 358 startpoints = freebusy[:last] 359 360 # Find the range of periods potentially overlapping the period in a version 361 # of the free/busy collection sorted according to end datetimes. 362 363 endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints] 364 endpoints.sort() 365 first = bisect_left(endpoints, (period.get_start_point(),)) 366 endpoints = endpoints[first:] 367 368 overlapping = set() 369 370 for end, start, fb in endpoints: 371 if end > period.get_start_point() and start < period.get_end_point(): 372 overlapping.add(fb) 373 374 overlapping = list(overlapping) 375 overlapping.sort() 376 return overlapping 377 378 def period_overlaps(freebusy, period, get_periods=False): 379 380 """ 381 Return whether any period in 'freebusy' overlaps with the given 'period', 382 returning a collection of overlapping periods if 'get_periods' is set to a 383 true value. 384 """ 385 386 overlapping = get_overlapping(freebusy, period) 387 388 if get_periods: 389 return overlapping 390 else: 391 return len(overlapping) != 0 392 393 def remove_overlapping(freebusy, period): 394 395 "Remove from 'freebusy' all periods overlapping with 'period'." 396 397 overlapping = get_overlapping(freebusy, period) 398 399 if overlapping: 400 for fb in overlapping: 401 freebusy.remove(fb) 402 403 def replace_overlapping(freebusy, period, replacements): 404 405 """ 406 Replace existing periods in 'freebusy' within the given 'period', using the 407 given 'replacements'. 408 """ 409 410 remove_overlapping(freebusy, period) 411 for replacement in replacements: 412 insert_period(freebusy, replacement) 413 414 # Period layout. 415 416 def get_scale(periods, tzid): 417 418 """ 419 Return an ordered time scale from the given list of 'periods'. 420 421 The given 'tzid' is used to make sure that the times are defined according 422 to the chosen time zone. 423 424 The returned scale is a mapping from time to (starting, ending) tuples, 425 where starting and ending are collections of periods. 426 """ 427 428 scale = {} 429 430 for p in periods: 431 432 # Add a point and this event to the starting list. 433 434 start = to_timezone(p.get_start(), tzid) 435 if not scale.has_key(start): 436 scale[start] = [], [] 437 scale[start][0].append(p) 438 439 # Add a point and this event to the ending list. 440 441 end = to_timezone(p.get_end(), tzid) 442 if not scale.has_key(end): 443 scale[end] = [], [] 444 scale[end][1].append(p) 445 446 return scale 447 448 class Point: 449 450 "A qualified point in time." 451 452 PRINCIPAL, REPEATED = 0, 1 453 454 def __init__(self, point, indicator=None): 455 self.point = point 456 self.indicator = indicator or self.PRINCIPAL 457 458 def __hash__(self): 459 return hash((self.point, self.indicator)) 460 461 def __cmp__(self, other): 462 if isinstance(other, Point): 463 return cmp((self.point, self.indicator), (other.point, other.indicator)) 464 elif isinstance(other, datetime): 465 return cmp(self.point, other) 466 else: 467 return 1 468 469 def __eq__(self, other): 470 return self.__cmp__(other) == 0 471 472 def __ne__(self, other): 473 return not self == other 474 475 def __lt__(self, other): 476 return self.__cmp__(other) < 0 477 478 def __le__(self, other): 479 return self.__cmp__(other) <= 0 480 481 def __gt__(self, other): 482 return not self <= other 483 484 def __ge__(self, other): 485 return not self < other 486 487 def __repr__(self): 488 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 489 490 def get_slots(scale): 491 492 """ 493 Return an ordered list of time slots from the given 'scale'. 494 495 Each slot is a tuple containing details of a point in time for the start of 496 the slot, together with a list of parallel event periods. 497 498 Each point in time is described as a Point representing the actual point in 499 time together with an indicator of the nature of the point in time (as a 500 principal point in a time scale or as a repeated point used to terminate 501 events occurring for an instant in time). 502 """ 503 504 slots = [] 505 active = [] 506 507 points = scale.items() 508 points.sort() 509 510 for point, (starting, ending) in points: 511 ending = set(ending) 512 instants = ending.intersection(starting) 513 514 # Discard all active events ending at or before this start time. 515 # Free up the position in the active list. 516 517 for t in ending.difference(instants): 518 i = active.index(t) 519 active[i] = None 520 521 # For each event starting at the current point, fill any newly-vacated 522 # position or add to the end of the active list. 523 524 for t in starting: 525 try: 526 i = active.index(None) 527 active[i] = t 528 except ValueError: 529 active.append(t) 530 531 # Discard vacant positions from the end of the active list. 532 533 while active and active[-1] is None: 534 active.pop() 535 536 # Add an entry for the time point before "instants". 537 538 slots.append((Point(point), active[:])) 539 540 # Discard events ending at the same time as they began. 541 542 if instants: 543 for t in instants: 544 i = active.index(t) 545 active[i] = None 546 547 # Discard vacant positions from the end of the active list. 548 549 while active and active[-1] is None: 550 active.pop() 551 552 # Add another entry for the time point after "instants". 553 554 slots.append((Point(point, Point.REPEATED), active[:])) 555 556 return slots 557 558 def add_day_start_points(slots, tzid): 559 560 """ 561 Introduce into the 'slots' any day start points required by multi-day 562 periods. The 'tzid' is required to make sure that appropriate time zones 563 are chosen and not necessarily those provided by the existing time points. 564 """ 565 566 new_slots = [] 567 current_date = None 568 previously_active = [] 569 570 for point, active in slots: 571 start_of_day = get_start_of_day(point.point, tzid) 572 this_date = point.point.date() 573 574 # For each new day, add a slot for the start of the day where periods 575 # are active and where no such slot already exists. 576 577 if this_date != current_date: 578 579 # Fill in days where events remain active. 580 581 if current_date: 582 current_date += timedelta(1) 583 while current_date < this_date: 584 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 585 current_date += timedelta(1) 586 else: 587 current_date = this_date 588 589 # Add any continuing periods. 590 591 if point.point != start_of_day: 592 new_slots.append((Point(start_of_day), previously_active)) 593 594 # Add the currently active periods at this point in time. 595 596 previously_active = active 597 598 for t in new_slots: 599 insort_left(slots, t) 600 601 def add_slots(slots, points): 602 603 """ 604 Introduce into the 'slots' entries for those in 'points' that are not 605 already present, propagating active periods from time points preceding 606 those added. 607 """ 608 609 new_slots = [] 610 611 for point in points: 612 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 613 if i < len(slots) and slots[i][0] == point: 614 continue 615 616 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 617 618 for t in new_slots: 619 insort_left(slots, t) 620 621 def partition_by_day(slots): 622 623 """ 624 Return a mapping from dates to time points provided by 'slots'. 625 """ 626 627 d = {} 628 629 for point, value in slots: 630 day = point.point.date() 631 if not d.has_key(day): 632 d[day] = [] 633 d[day].append((point, value)) 634 635 return d 636 637 def add_empty_days(days, tzid): 638 639 "Add empty days to 'days' between busy days." 640 641 last_day = None 642 all_days = days.keys() 643 all_days.sort() 644 645 for day in all_days: 646 if last_day: 647 empty_day = last_day + timedelta(1) 648 while empty_day < day: 649 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 650 empty_day += timedelta(1) 651 last_day = day 652 653 def get_spans(slots): 654 655 "Inspect the given 'slots', returning a mapping of period keys to spans." 656 657 points = [point for point, active in slots] 658 spans = {} 659 660 for _point, active in slots: 661 for p in active: 662 if p: 663 key = p.get_key() 664 start_slot = bisect_left(points, p.get_start()) 665 end_slot = bisect_left(points, p.get_end()) 666 spans[key] = end_slot - start_slot 667 668 return spans 669 670 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 671 672 """ 673 Update the free/busy details with the given 'periods', 'transp' setting, 674 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 675 """ 676 677 remove_period(freebusy, uid, recurrenceid) 678 679 for p in periods: 680 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser)) 681 682 # vim: tabstop=4 expandtab shiftwidth=4