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