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 start, end = get_overlapping(freebusy, period) 188 189 if start != end: 190 del freebusy[start:end] 191 192 def replace_overlapping(freebusy, period, replacements): 193 194 """ 195 Replace existing periods in 'freebusy' within the given 'period', using the 196 given 'replacements'. 197 """ 198 199 remove_overlapping(freebusy, period) 200 for replacement in replacements: 201 insert_period(freebusy, replacement) 202 203 # Period layout mostly with datetime objects. 204 205 def convert_periods(periods, tzid): 206 207 "Convert 'periods' to use datetime objects employing the given 'tzid'." 208 209 l = [] 210 211 for t in periods: 212 start, end = t[:2] 213 214 # NOTE: This only really works if the datetimes are UTC already. 215 # NOTE: Since the periods should originate from the free/busy data, 216 # NOTE: and since that data should employ UTC times, this should not be 217 # NOTE: an immediate problem. 218 219 start = get_datetime(start) 220 end = get_datetime(end) 221 222 start = isinstance(start, datetime) and to_timezone(start, tzid) or get_start_of_day(start, tzid) 223 end = isinstance(end, datetime) and to_timezone(end, tzid) or get_start_of_day(end, tzid) 224 225 l.append((start, end) + tuple(t[2:])) 226 227 return l 228 229 def get_scale(periods): 230 231 """ 232 Return an ordered time scale from the given list 'periods', with the first 233 two elements of each tuple being start and end times. 234 235 The given 'tzid' is used to make sure that the times are defined according 236 to the chosen time zone. 237 238 The returned scale is a mapping from time to (starting, ending) tuples, 239 where starting and ending are collections of tuples from 'periods'. 240 """ 241 242 scale = {} 243 244 for t in periods: 245 start, end = t[:2] 246 247 # Add a point and this event to the starting list. 248 249 if not scale.has_key(start): 250 scale[start] = [], [] 251 scale[start][0].append(t) 252 253 # Add a point and this event to the ending list. 254 255 if not scale.has_key(end): 256 scale[end] = [], [] 257 scale[end][1].append(t) 258 259 return scale 260 261 def get_slots(scale): 262 263 """ 264 Return an ordered list of time slots from the given 'scale'. 265 266 Each slot is a tuple containing a point in time for the start of the slot, 267 together with a list of parallel event tuples, each tuple containing the 268 original details of an event. 269 """ 270 271 slots = [] 272 active = [] 273 274 points = scale.items() 275 points.sort() 276 277 for point, (starting, ending) in points: 278 279 # Discard all active events ending at or before this start time. 280 # Free up the position in the active list. 281 282 for t in ending: 283 i = active.index(t) 284 active[i] = None 285 286 # For each event starting at the current point, fill any newly-vacated 287 # position or add to the end of the active list. 288 289 for t in starting: 290 try: 291 i = active.index(None) 292 active[i] = t 293 except ValueError: 294 active.append(t) 295 296 # Discard vacant positions from the end of the active list. 297 298 while active and active[-1] is None: 299 active.pop() 300 301 slots.append((point, active[:])) 302 303 return slots 304 305 def add_day_start_points(slots, tzid): 306 307 """ 308 Introduce into the 'slots' any day start points required by multi-day 309 periods. The 'tzid' is required to make sure that appropriate time zones 310 are chosen and not necessarily those provided by the existing time points. 311 """ 312 313 new_slots = [] 314 current_date = None 315 previously_active = [] 316 317 for point, active in slots: 318 start_of_day = get_start_of_day(point, tzid) 319 this_date = point.date() 320 321 # For each new day, add a slot for the start of the day where periods 322 # are active and where no such slot already exists. 323 324 if this_date != current_date: 325 326 # Fill in days where events remain active. 327 328 if current_date: 329 current_date += timedelta(1) 330 while current_date < this_date: 331 new_slots.append((get_start_of_day(current_date, tzid), previously_active)) 332 current_date += timedelta(1) 333 else: 334 current_date = this_date 335 336 # Add any continuing periods. 337 338 if point != start_of_day: 339 new_slots.append((start_of_day, previously_active)) 340 341 # Add the currently active periods at this point in time. 342 343 previously_active = active 344 345 for t in new_slots: 346 insort_left(slots, t) 347 348 def add_slots(slots, points): 349 350 """ 351 Introduce into the 'slots' entries for those in 'points' that are not 352 already present, propagating active periods from time points preceding 353 those added. 354 """ 355 356 new_slots = [] 357 358 for point in points: 359 i = bisect_left(slots, (point,)) 360 if i < len(slots) and slots[i][0] == point: 361 continue 362 363 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 364 365 for t in new_slots: 366 insort_left(slots, t) 367 368 def partition_by_day(slots): 369 370 """ 371 Return a mapping from dates to time points provided by 'slots'. 372 """ 373 374 d = {} 375 376 for point, value in slots: 377 day = point.date() 378 if not d.has_key(day): 379 d[day] = [] 380 d[day].append((point, value)) 381 382 return d 383 384 def add_empty_days(days, tzid): 385 386 "Add empty days to 'days' between busy days." 387 388 last_day = None 389 all_days = days.keys() 390 all_days.sort() 391 392 for day in all_days: 393 if last_day: 394 empty_day = last_day + timedelta(1) 395 while empty_day < day: 396 days[empty_day] = [(get_start_of_day(empty_day, tzid), None)] 397 empty_day += timedelta(1) 398 last_day = day 399 400 def get_spans(slots): 401 402 "Inspect the given 'slots', returning a mapping of event uids to spans." 403 404 points = [point for point, active in slots] 405 spans = {} 406 407 for point, active in slots: 408 for t in active: 409 if t and len(t) >= 2: 410 start, end, uid, recurrenceid, summary, organiser, key = get_freebusy_details(t) 411 412 try: 413 start_slot = points.index(start) 414 except ValueError: 415 start_slot = 0 416 try: 417 end_slot = points.index(end) 418 except ValueError: 419 end_slot = len(slots) 420 spans[key] = end_slot - start_slot 421 422 return spans 423 424 def get_freebusy_details(t): 425 426 """ 427 Return a tuple of the form (start, end, uid, recurrenceid, summary, 428 organiser, key) from 't'. 429 """ 430 431 # Handle both complete free/busy details... 432 433 if len(t) >= 7: 434 start, end, uid, transp, recurrenceid, summary, organiser = t[:7] 435 key = uid, recurrenceid, start 436 437 # ...and published details without specific event details. 438 439 else: 440 start, end = t[:2] 441 uid = None 442 recurrenceid = None 443 summary = None 444 organiser = None 445 key = (start, end) 446 447 return start, end, uid, recurrenceid, summary, organiser, key 448 449 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 450 451 """ 452 Update the free/busy details with the given 'periods', 'transp' setting, 453 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 454 """ 455 456 remove_period(freebusy, uid, recurrenceid) 457 458 for start, end in periods: 459 insert_period(freebusy, (start, end, uid, transp, recurrenceid, summary, organiser)) 460 461 # vim: tabstop=4 expandtab shiftwidth=4