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