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