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