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