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