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 current_date = this_date 318 319 # Add any continuing periods. 320 321 if point != start_of_day: 322 new_slots.append((start_of_day, previously_active)) 323 324 # Add the currently active periods at this point in time. 325 326 previously_active = active 327 328 for t in new_slots: 329 insort_left(slots, t) 330 331 def add_slots(slots, points): 332 333 """ 334 Introduce into the 'slots' entries for those in 'points' that are not 335 already present, propagating active periods from time points preceding 336 those added. 337 """ 338 339 new_slots = [] 340 341 for point in points: 342 i = bisect_left(slots, (point, None)) 343 if i < len(slots) and slots[i][0] == point: 344 continue 345 346 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 347 348 for t in new_slots: 349 insort_left(slots, t) 350 351 def partition_by_day(slots): 352 353 """ 354 Return a mapping from dates to time points provided by 'slots'. 355 """ 356 357 d = {} 358 359 for point, value in slots: 360 day = point.date() 361 if not d.has_key(day): 362 d[day] = [] 363 d[day].append((point, value)) 364 365 return d 366 367 def add_empty_days(days, tzid): 368 369 "Add empty days to 'days' between busy days." 370 371 last_day = None 372 all_days = days.keys() 373 all_days.sort() 374 375 for day in all_days: 376 if last_day: 377 empty_day = last_day + timedelta(1) 378 while empty_day < day: 379 days[empty_day] = [(get_start_of_day(empty_day, tzid), None)] 380 empty_day += timedelta(1) 381 last_day = day 382 383 def get_spans(slots): 384 385 "Inspect the given 'slots', returning a mapping of event uids to spans." 386 387 points = [point for point, active in slots] 388 spans = {} 389 390 for point, active in slots: 391 for t in active: 392 if t and len(t) >= 2: 393 start, end, uid, recurrenceid, summary, organiser, key = get_freebusy_details(t) 394 395 try: 396 start_slot = points.index(start) 397 except ValueError: 398 start_slot = 0 399 try: 400 end_slot = points.index(end) 401 except ValueError: 402 end_slot = len(slots) 403 spans[key] = end_slot - start_slot 404 405 return spans 406 407 def get_freebusy_details(t): 408 409 """ 410 Return a tuple of the form (start, end, uid, recurrenceid, summary, 411 organiser, key) from 't'. 412 """ 413 414 # Handle both complete free/busy details... 415 416 if len(t) >= 7: 417 start, end, uid, transp, recurrenceid, summary, organiser = t[:7] 418 key = uid, recurrenceid 419 420 # ...and published details without specific event details. 421 422 else: 423 start, end = t[:2] 424 uid = None 425 recurrenceid = None 426 summary = None 427 organiser = None 428 key = (start, end) 429 430 return start, end, uid, recurrenceid, summary, organiser, key 431 432 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser): 433 434 """ 435 Update the free/busy details with the given 'periods', 'transp' setting, 436 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 437 """ 438 439 remove_period(freebusy, uid, recurrenceid) 440 441 for start, end in periods: 442 insert_period(freebusy, (start, end, uid, transp, recurrenceid, summary, organiser)) 443 444 # vim: tabstop=4 expandtab shiftwidth=4