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