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