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