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