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