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