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