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