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