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