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