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 POINT, REPEATED = 0, 1 263 264 def get_slots(scale): 265 266 """ 267 Return an ordered list of time slots from the given 'scale'. 268 269 Each slot is a tuple containing details of a point in time for the start of 270 the slot, together with a list of parallel event tuples, each tuple 271 containing the original details of an event. 272 273 Each point in time is described as a tuple containing the actual time point 274 plus an indicator (0 as POINT or 1 as REPEATED), with REPEATED being used to 275 indicate repeated points used for the end of "instant" events. 276 """ 277 278 slots = [] 279 active = [] 280 281 points = scale.items() 282 points.sort() 283 284 for point, (starting, ending) in points: 285 ending = set(ending) 286 instants = ending.intersection(starting) 287 288 # Discard all active events ending at or before this start time. 289 # Free up the position in the active list. 290 291 for t in ending.difference(instants): 292 i = active.index(t) 293 active[i] = None 294 295 # For each event starting at the current point, fill any newly-vacated 296 # position or add to the end of the active list. 297 298 for t in starting: 299 try: 300 i = active.index(None) 301 active[i] = t 302 except ValueError: 303 active.append(t) 304 305 # Discard vacant positions from the end of the active list. 306 307 while active and active[-1] is None: 308 active.pop() 309 310 # Add an entry for the time point before "instants". 311 312 slots.append(((point, POINT), active[:])) 313 314 # Discard events ending at the same time as they began. 315 316 if instants: 317 for t in instants: 318 i = active.index(t) 319 active[i] = None 320 321 # Discard vacant positions from the end of the active list. 322 323 while active and active[-1] is None: 324 active.pop() 325 326 # Add another entry for the time point after "instants". 327 328 slots.append(((point, REPEATED), active[:])) 329 330 return slots 331 332 def add_day_start_points(slots, tzid): 333 334 """ 335 Introduce into the 'slots' any day start points required by multi-day 336 periods. The 'tzid' is required to make sure that appropriate time zones 337 are chosen and not necessarily those provided by the existing time points. 338 """ 339 340 new_slots = [] 341 current_date = None 342 previously_active = [] 343 344 for (point, indicator), active in slots: 345 start_of_day = get_start_of_day(point, tzid) 346 this_date = point.date() 347 348 # For each new day, add a slot for the start of the day where periods 349 # are active and where no such slot already exists. 350 351 if this_date != current_date: 352 353 # Fill in days where events remain active. 354 355 if current_date: 356 current_date += timedelta(1) 357 while current_date < this_date: 358 new_slots.append(((get_start_of_day(current_date, tzid), POINT), previously_active)) 359 current_date += timedelta(1) 360 else: 361 current_date = this_date 362 363 # Add any continuing periods. 364 365 if point != start_of_day: 366 new_slots.append(((start_of_day, POINT), previously_active)) 367 368 # Add the currently active periods at this point in time. 369 370 previously_active = active 371 372 for t in new_slots: 373 insort_left(slots, t) 374 375 def add_slots(slots, points): 376 377 """ 378 Introduce into the 'slots' entries for those in 'points' that are not 379 already present, propagating active periods from time points preceding 380 those added. 381 """ 382 383 new_slots = [] 384 385 for point in points: 386 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 387 if i < len(slots) and slots[i][0] == point: 388 continue 389 390 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 391 392 for t in new_slots: 393 insort_left(slots, t) 394 395 def partition_by_day(slots): 396 397 """ 398 Return a mapping from dates to time points provided by 'slots'. 399 """ 400 401 d = {} 402 403 for (point, indicator), value in slots: 404 day = point.date() 405 if not d.has_key(day): 406 d[day] = [] 407 d[day].append(((point, indicator), value)) 408 409 return d 410 411 def add_empty_days(days, tzid): 412 413 "Add empty days to 'days' between busy days." 414 415 last_day = None 416 all_days = days.keys() 417 all_days.sort() 418 419 for day in all_days: 420 if last_day: 421 empty_day = last_day + timedelta(1) 422 while empty_day < day: 423 days[empty_day] = [((get_start_of_day(empty_day, tzid), POINT), None)] 424 empty_day += timedelta(1) 425 last_day = day 426 427 def get_spans(slots): 428 429 "Inspect the given 'slots', returning a mapping of event uids to spans." 430 431 all_point_details = [point_details for point_details, active in slots] 432 spans = {} 433 434 for _point, active in slots: 435 for t in active: 436 if t and len(t) >= 2: 437 start, end, uid, recurrenceid, summary, organiser, key = get_freebusy_details(t) 438 439 start_slot = bisect_left(all_point_details, (start,)) 440 end_slot = bisect_left(all_point_details, (end,)) 441 spans[key] = end_slot - start_slot 442 443 return spans 444 445 def get_freebusy_details(t): 446 447 """ 448 Return a tuple of the form (start, end, uid, recurrenceid, summary, 449 organiser, key) from 't'. 450 """ 451 452 # Handle both complete free/busy details... 453 454 if len(t) >= 7: 455 start, end, uid, transp, recurrenceid, summary, organiser = t[:7] 456 key = uid, recurrenceid, start 457 458 # ...and published details without specific event details. 459 460 else: 461 start, end = t[:2] 462 uid = None 463 recurrenceid = None 464 summary = None 465 organiser = None 466 key = (start, end) 467 468 return start, end, uid, recurrenceid, summary, organiser, key 469 470 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 471 472 """ 473 Update the free/busy details with the given 'periods', 'transp' setting, 474 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 475 """ 476 477 remove_period(freebusy, uid, recurrenceid) 478 479 for start, end in periods: 480 insert_period(freebusy, (start, end, uid, transp, recurrenceid, summary, organiser)) 481 482 # vim: tabstop=4 expandtab shiftwidth=4