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' limits, 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 class RecurringPeriod(Period): 197 198 """ 199 A period with iCalendar metadata attributes and origin information from an 200 object. 201 """ 202 203 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 204 Period.__init__(self, start, end, tzid, origin) 205 self.start_attr = start_attr 206 self.end_attr = end_attr 207 208 def get_start_attr(self): 209 return self.start_attr 210 211 def get_end_attr(self): 212 return self.end_attr 213 214 def as_tuple(self): 215 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 216 217 def __repr__(self): 218 return "RecurringPeriod%r" % (self.as_tuple(),) 219 220 # Time and period management. 221 222 def can_schedule(freebusy, periods, uid, recurrenceid): 223 224 """ 225 Return whether the 'freebusy' list can accommodate the given 'periods' 226 employing the specified 'uid' and 'recurrenceid'. 227 """ 228 229 for conflict in have_conflict(freebusy, periods, True): 230 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 231 return False 232 233 return True 234 235 def have_conflict(freebusy, periods, get_conflicts=False): 236 237 """ 238 Return whether any period in 'freebusy' overlaps with the given 'periods', 239 returning a collection of such overlapping periods if 'get_conflicts' is 240 set to a true value. 241 """ 242 243 conflicts = set() 244 for p in periods: 245 overlapping = period_overlaps(freebusy, p, get_conflicts) 246 if overlapping: 247 if get_conflicts: 248 conflicts.update(overlapping) 249 else: 250 return True 251 252 if get_conflicts: 253 return conflicts 254 else: 255 return False 256 257 def insert_period(freebusy, period): 258 259 "Insert into 'freebusy' the given 'period'." 260 261 insort_left(freebusy, period) 262 263 def remove_period(freebusy, uid, recurrenceid=None): 264 265 """ 266 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 267 (which if omitted causes the "parent" object's periods to be referenced). 268 """ 269 270 removed = False 271 i = 0 272 while i < len(freebusy): 273 fb = freebusy[i] 274 if fb.uid == uid and fb.recurrenceid == recurrenceid: 275 del freebusy[i] 276 removed = True 277 else: 278 i += 1 279 280 return removed 281 282 def remove_additional_periods(freebusy, uid, recurrenceids=None): 283 284 """ 285 Remove from 'freebusy' all periods associated with 'uid' having a 286 recurrence identifier indicating an additional or modified period. 287 288 If 'recurrenceids' is specified, remove all periods associated with 'uid' 289 that do not have a recurrence identifier in the given list. 290 """ 291 292 i = 0 293 while i < len(freebusy): 294 fb = freebusy[i] 295 if fb.uid == uid and fb.recurrenceid and ( 296 recurrenceids is None or 297 recurrenceids is not None and fb.recurrenceid not in recurrenceids 298 ): 299 del freebusy[i] 300 else: 301 i += 1 302 303 def remove_affected_period(freebusy, uid, start): 304 305 """ 306 Remove from 'freebusy' a period associated with 'uid' that provides an 307 occurrence starting at the given 'start' (provided by a recurrence 308 identifier, converted to a datetime). A recurrence identifier is used to 309 provide an alternative time period whilst also acting as a reference to the 310 originally-defined occurrence. 311 """ 312 313 search = Period(start, start) 314 found = bisect_left(freebusy, search) 315 316 while found < len(freebusy): 317 fb = freebusy[found] 318 319 # Stop looking if the start no longer matches the recurrence identifier. 320 321 if fb.get_start_point() != search.get_start_point(): 322 return 323 324 # If the period belongs to the parent object, remove it and return. 325 326 if not fb.recurrenceid and uid == fb.uid: 327 del freebusy[found] 328 break 329 330 # Otherwise, keep looking for a matching period. 331 332 found += 1 333 334 def get_overlapping(freebusy, period): 335 336 """ 337 Return the entries in 'freebusy' providing periods overlapping with 338 'period'. 339 """ 340 341 # Find the range of periods potentially overlapping the period in the 342 # free/busy collection. 343 344 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.tzid)) 345 startpoints = freebusy[:last] 346 347 # Find the range of periods potentially overlapping the period in a version 348 # of the free/busy collection sorted according to end datetimes. 349 350 endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints] 351 endpoints.sort() 352 first = bisect_left(endpoints, (period.get_start_point(),)) 353 endpoints = endpoints[first:] 354 355 overlapping = set() 356 357 for end, start, fb in endpoints: 358 if end > period.get_start_point() and start < period.get_end_point(): 359 overlapping.add(fb) 360 361 overlapping = list(overlapping) 362 overlapping.sort() 363 return overlapping 364 365 def period_overlaps(freebusy, period, get_periods=False): 366 367 """ 368 Return whether any period in 'freebusy' overlaps with the given 'period', 369 returning a collection of overlapping periods if 'get_periods' is set to a 370 true value. 371 """ 372 373 overlapping = get_overlapping(freebusy, period) 374 375 if get_periods: 376 return overlapping 377 else: 378 return len(overlapping) != 0 379 380 def remove_overlapping(freebusy, period): 381 382 "Remove from 'freebusy' all periods overlapping with 'period'." 383 384 overlapping = get_overlapping(freebusy, period) 385 386 if overlapping: 387 for fb in overlapping: 388 freebusy.remove(fb) 389 390 def replace_overlapping(freebusy, period, replacements): 391 392 """ 393 Replace existing periods in 'freebusy' within the given 'period', using the 394 given 'replacements'. 395 """ 396 397 remove_overlapping(freebusy, period) 398 for replacement in replacements: 399 insert_period(freebusy, replacement) 400 401 # Period layout. 402 403 def get_scale(periods, tzid): 404 405 """ 406 Return an ordered time scale from the given list of 'periods'. 407 408 The given 'tzid' is used to make sure that the times are defined according 409 to the chosen time zone. 410 411 The returned scale is a mapping from time to (starting, ending) tuples, 412 where starting and ending are collections of periods. 413 """ 414 415 scale = {} 416 417 for p in periods: 418 419 # Add a point and this event to the starting list. 420 421 start = to_timezone(p.get_start(), tzid) 422 if not scale.has_key(start): 423 scale[start] = [], [] 424 scale[start][0].append(p) 425 426 # Add a point and this event to the ending list. 427 428 end = to_timezone(p.get_end(), tzid) 429 if not scale.has_key(end): 430 scale[end] = [], [] 431 scale[end][1].append(p) 432 433 return scale 434 435 class Point: 436 437 "A qualified point in time." 438 439 PRINCIPAL, REPEATED = 0, 1 440 441 def __init__(self, point, indicator=None): 442 self.point = point 443 self.indicator = indicator or self.PRINCIPAL 444 445 def __hash__(self): 446 return hash((self.point, self.indicator)) 447 448 def __cmp__(self, other): 449 if isinstance(other, Point): 450 return cmp((self.point, self.indicator), (other.point, other.indicator)) 451 elif isinstance(other, datetime): 452 return cmp(self.point, other) 453 else: 454 return 1 455 456 def __eq__(self, other): 457 return self.__cmp__(other) == 0 458 459 def __ne__(self, other): 460 return not self == other 461 462 def __lt__(self, other): 463 return self.__cmp__(other) < 0 464 465 def __le__(self, other): 466 return self.__cmp__(other) <= 0 467 468 def __gt__(self, other): 469 return not self <= other 470 471 def __ge__(self, other): 472 return not self < other 473 474 def __repr__(self): 475 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 476 477 def get_slots(scale): 478 479 """ 480 Return an ordered list of time slots from the given 'scale'. 481 482 Each slot is a tuple containing details of a point in time for the start of 483 the slot, together with a list of parallel event periods. 484 485 Each point in time is described as a Point representing the actual point in 486 time together with an indicator of the nature of the point in time (as a 487 principal point in a time scale or as a repeated point used to terminate 488 events occurring for an instant in time). 489 """ 490 491 slots = [] 492 active = [] 493 494 points = scale.items() 495 points.sort() 496 497 for point, (starting, ending) in points: 498 ending = set(ending) 499 instants = ending.intersection(starting) 500 501 # Discard all active events ending at or before this start time. 502 # Free up the position in the active list. 503 504 for t in ending.difference(instants): 505 i = active.index(t) 506 active[i] = None 507 508 # For each event starting at the current point, fill any newly-vacated 509 # position or add to the end of the active list. 510 511 for t in starting: 512 try: 513 i = active.index(None) 514 active[i] = t 515 except ValueError: 516 active.append(t) 517 518 # Discard vacant positions from the end of the active list. 519 520 while active and active[-1] is None: 521 active.pop() 522 523 # Add an entry for the time point before "instants". 524 525 slots.append((Point(point), active[:])) 526 527 # Discard events ending at the same time as they began. 528 529 if instants: 530 for t in instants: 531 i = active.index(t) 532 active[i] = None 533 534 # Discard vacant positions from the end of the active list. 535 536 while active and active[-1] is None: 537 active.pop() 538 539 # Add another entry for the time point after "instants". 540 541 slots.append((Point(point, Point.REPEATED), active[:])) 542 543 return slots 544 545 def add_day_start_points(slots, tzid): 546 547 """ 548 Introduce into the 'slots' any day start points required by multi-day 549 periods. The 'tzid' is required to make sure that appropriate time zones 550 are chosen and not necessarily those provided by the existing time points. 551 """ 552 553 new_slots = [] 554 current_date = None 555 previously_active = [] 556 557 for point, active in slots: 558 start_of_day = get_start_of_day(point.point, tzid) 559 this_date = point.point.date() 560 561 # For each new day, add a slot for the start of the day where periods 562 # are active and where no such slot already exists. 563 564 if this_date != current_date: 565 566 # Fill in days where events remain active. 567 568 if current_date: 569 current_date += timedelta(1) 570 while current_date < this_date: 571 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 572 current_date += timedelta(1) 573 else: 574 current_date = this_date 575 576 # Add any continuing periods. 577 578 if point.point != start_of_day: 579 new_slots.append((Point(start_of_day), previously_active)) 580 581 # Add the currently active periods at this point in time. 582 583 previously_active = active 584 585 for t in new_slots: 586 insort_left(slots, t) 587 588 def add_slots(slots, points): 589 590 """ 591 Introduce into the 'slots' entries for those in 'points' that are not 592 already present, propagating active periods from time points preceding 593 those added. 594 """ 595 596 new_slots = [] 597 598 for point in points: 599 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 600 if i < len(slots) and slots[i][0] == point: 601 continue 602 603 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 604 605 for t in new_slots: 606 insort_left(slots, t) 607 608 def partition_by_day(slots): 609 610 """ 611 Return a mapping from dates to time points provided by 'slots'. 612 """ 613 614 d = {} 615 616 for point, value in slots: 617 day = point.point.date() 618 if not d.has_key(day): 619 d[day] = [] 620 d[day].append((point, value)) 621 622 return d 623 624 def add_empty_days(days, tzid): 625 626 "Add empty days to 'days' between busy days." 627 628 last_day = None 629 all_days = days.keys() 630 all_days.sort() 631 632 for day in all_days: 633 if last_day: 634 empty_day = last_day + timedelta(1) 635 while empty_day < day: 636 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 637 empty_day += timedelta(1) 638 last_day = day 639 640 def get_spans(slots): 641 642 "Inspect the given 'slots', returning a mapping of period keys to spans." 643 644 points = [point for point, active in slots] 645 spans = {} 646 647 for _point, active in slots: 648 for p in active: 649 if p: 650 key = p.get_key() 651 start_slot = bisect_left(points, p.get_start()) 652 end_slot = bisect_left(points, p.get_end()) 653 spans[key] = end_slot - start_slot 654 655 return spans 656 657 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 658 659 """ 660 Update the free/busy details with the given 'periods', 'transp' setting, 661 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 662 """ 663 664 remove_period(freebusy, uid, recurrenceid) 665 666 for p in periods: 667 insert_period(freebusy, FreeBusyPeriod(p.get_start(), p.get_end(), uid, transp, recurrenceid, summary, organiser, p.tzid)) 668 669 # vim: tabstop=4 expandtab shiftwidth=4