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