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 format_datetime, get_datetime, get_start_of_day, \ 25 to_timezone 26 from vRecurrence import get_parameters, get_rule 27 28 # Time management with datetime strings. 29 30 def can_schedule(freebusy, periods, uid): 31 32 """ 33 Return whether the 'freebusy' list can accommodate the given 'periods' 34 employing the specified 'uid'. 35 """ 36 37 for conflict in have_conflict(freebusy, periods, True): 38 start, end, found_uid, found_transp = conflict 39 if found_uid != uid: 40 return False 41 42 return True 43 44 def have_conflict(freebusy, periods, get_conflicts=False): 45 46 """ 47 Return whether any period in 'freebusy' overlaps with the given 'periods', 48 returning a collection of such overlapping periods if 'get_conflicts' is 49 set to a true value. 50 """ 51 52 conflicts = [] 53 for start, end in periods: 54 overlapping = period_overlaps(freebusy, (start, end), get_conflicts) 55 if overlapping: 56 if get_conflicts: 57 conflicts += overlapping 58 else: 59 return True 60 61 if get_conflicts: 62 return conflicts 63 else: 64 return False 65 66 def insert_period(freebusy, period): 67 insort_left(freebusy, period) 68 69 def remove_period(freebusy, uid): 70 i = 0 71 while i < len(freebusy): 72 t = freebusy[i] 73 if len(t) >= 3 and t[2] == uid: 74 del freebusy[i] 75 else: 76 i += 1 77 78 def period_overlaps(freebusy, period, get_periods=False): 79 80 """ 81 Return whether any period in 'freebusy' overlaps with the given 'period', 82 returning a collection of overlapping periods if 'get_periods' is set to a 83 true value. 84 """ 85 86 dtstart, dtend = period[:2] 87 found = bisect_left(freebusy, (dtstart, dtend, None, None)) 88 89 overlapping = [] 90 91 # Find earlier overlapping periods. 92 93 i = found 94 95 while i > 0 and freebusy[i - 1][1] > dtstart: 96 if get_periods: 97 overlapping.insert(0, freebusy[i - 1]) 98 else: 99 return True 100 i -= 1 101 102 # Find later overlapping periods. 103 104 i = found 105 106 while i < len(freebusy) and (dtend is None or freebusy[i][0] < dtend): 107 if get_periods: 108 overlapping.append(freebusy[i]) 109 else: 110 return True 111 i += 1 112 113 if get_periods: 114 return overlapping 115 else: 116 return False 117 118 # Period layout mostly with datetime objects. 119 120 def convert_periods(periods, tzid): 121 122 "Convert 'periods' to use datetime objects employing the given 'tzid'." 123 124 l = [] 125 126 for t in periods: 127 start, end = t[:2] 128 129 # NOTE: This only really works if the datetimes are UTC already. 130 # NOTE: Since the periods should originate from the free/busy data, 131 # NOTE: and since that data should employ UTC times, this should not be 132 # NOTE: an immediate problem. 133 134 start = get_datetime(start) 135 end = get_datetime(end) 136 137 start = isinstance(start, datetime) and to_timezone(start, tzid) or get_start_of_day(start, tzid) 138 end = isinstance(end, datetime) and to_timezone(end, tzid) or get_start_of_day(end, tzid) 139 140 l.append((start, end) + tuple(t[2:])) 141 142 return l 143 144 def get_scale(periods): 145 146 """ 147 Return an ordered time scale from the given list 'periods', with the first 148 two elements of each tuple being start and end times. 149 150 The given 'tzid' is used to make sure that the times are defined according 151 to the chosen time zone. 152 153 The returned scale is a mapping from time to (starting, ending) tuples, 154 where starting and ending are collections of tuples from 'periods'. 155 """ 156 157 scale = {} 158 159 for t in periods: 160 start, end = t[:2] 161 162 # Add a point and this event to the starting list. 163 164 if not scale.has_key(start): 165 scale[start] = [], [] 166 scale[start][0].append(t) 167 168 # Add a point and this event to the ending list. 169 170 if not scale.has_key(end): 171 scale[end] = [], [] 172 scale[end][1].append(t) 173 174 return scale 175 176 def get_slots(scale): 177 178 """ 179 Return an ordered list of time slots from the given 'scale'. 180 181 Each slot is a tuple containing a point in time for the start of the slot, 182 together with a list of parallel event tuples, each tuple containing the 183 original details of an event. 184 """ 185 186 slots = [] 187 active = [] 188 189 points = scale.items() 190 points.sort() 191 192 for point, (starting, ending) in points: 193 194 # Discard all active events ending at or before this start time. 195 # Free up the position in the active list. 196 197 for t in ending: 198 i = active.index(t) 199 active[i] = None 200 201 # For each event starting at the current point, fill any newly-vacated 202 # position or add to the end of the active list. 203 204 for t in starting: 205 try: 206 i = active.index(None) 207 active[i] = t 208 except ValueError: 209 active.append(t) 210 211 # Discard vacant positions from the end of the active list. 212 213 while active and active[-1] is None: 214 active.pop() 215 216 slots.append((point, active[:])) 217 218 return slots 219 220 def add_day_start_points(slots, tzid): 221 222 """ 223 Introduce into the 'slots' any day start points required by multi-day 224 periods. The 'tzid' is required to make sure that appropriate time zones 225 are chosen and not necessarily those provided by the existing time points. 226 """ 227 228 new_slots = [] 229 current_date = None 230 previously_active = [] 231 232 for point, active in slots: 233 start_of_day = get_start_of_day(point, tzid) 234 this_date = point.date() 235 236 # For each new day, add a slot for the start of the day where periods 237 # are active and where no such slot already exists. 238 239 if this_date != current_date: 240 current_date = this_date 241 242 # Add any continuing periods. 243 244 if point != start_of_day: 245 new_slots.append((start_of_day, previously_active)) 246 247 # Add the currently active periods at this point in time. 248 249 previously_active = active 250 251 for t in new_slots: 252 insort_left(slots, t) 253 254 def add_slots(slots, points): 255 256 """ 257 Introduce into the 'slots' entries for those in 'points' that are not 258 already present, propagating active periods from time points preceding 259 those added. 260 """ 261 262 new_slots = [] 263 264 for point in points: 265 i = bisect_left(slots, (point, None)) 266 if i < len(slots) and slots[i][0] == point: 267 continue 268 269 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 270 271 for t in new_slots: 272 insort_left(slots, t) 273 274 def partition_by_day(slots): 275 276 """ 277 Return a mapping from dates to time points provided by 'slots'. 278 """ 279 280 d = {} 281 282 for point, value in slots: 283 day = point.date() 284 if not d.has_key(day): 285 d[day] = [] 286 d[day].append((point, value)) 287 288 return d 289 290 def get_spans(slots): 291 292 "Inspect the given 'slots', returning a mapping of event uids to spans." 293 294 points = [point for point, active in slots] 295 spans = {} 296 297 for point, active in slots: 298 for t in active: 299 if t and len(t) >= 2: 300 start, end, uid, key = get_freebusy_details(t) 301 302 try: 303 start_slot = points.index(start) 304 except ValueError: 305 start_slot = 0 306 try: 307 end_slot = points.index(end) 308 except ValueError: 309 end_slot = len(slots) 310 spans[key] = end_slot - start_slot 311 312 return spans 313 314 def get_freebusy_details(t): 315 316 "Return a tuple of the form (start, end, uid, key) from 't'." 317 318 # Handle both complete free/busy details... 319 320 if len(t) > 2: 321 start, end, uid = t[:3] 322 key = uid 323 324 # ...and published details without specific event details. 325 326 else: 327 start, end = t[:2] 328 uid = None 329 key = (start, end) 330 331 return start, end, uid, key 332 333 # NOTE: Need to expose the 100 day window for recurring events in the 334 # NOTE: configuration. 335 336 def get_periods(obj, window_size=100): 337 338 """ 339 Return periods for the given object 'obj', confining materialised periods 340 to the given 'window_size' in days starting from the present moment. 341 """ 342 343 dtstart = obj.get_utc_datetime("DTSTART") 344 dtend = obj.get_utc_datetime("DTEND") 345 346 # NOTE: Need also DURATION support. 347 348 duration = dtend - dtstart 349 350 # Recurrence rules create multiple instances to be checked. 351 # Conflicts may only be assessed within a period defined by policy 352 # for the agent, with instances outside that period being considered 353 # unchecked. 354 355 window_end = datetime.now() + timedelta(window_size) 356 357 # NOTE: Need also RDATE and EXDATE support. 358 359 rrule = obj.get_value("RRULE") 360 361 if rrule: 362 selector = get_rule(dtstart, rrule) 363 parameters = get_parameters(rrule) 364 periods = [] 365 for start in selector.materialise(dtstart, window_end, parameters.get("COUNT"), parameters.get("BYSETPOS")): 366 start = datetime(*start, tzinfo=timezone("UTC")) 367 end = start + duration 368 periods.append((format_datetime(start), format_datetime(end))) 369 else: 370 periods = [(format_datetime(dtstart), format_datetime(dtend))] 371 372 return periods 373 374 def remove_from_freebusy(freebusy, attendee, uid, store): 375 376 """ 377 For the given 'attendee', remove periods from 'freebusy' that are associated 378 with 'uid' in the 'store'. 379 """ 380 381 remove_period(freebusy, uid) 382 store.set_freebusy(attendee, freebusy) 383 384 def remove_from_freebusy_for_other(freebusy, user, other, uid, store): 385 386 """ 387 For the given 'user', remove for the 'other' party periods from 'freebusy' 388 that are associated with 'uid' in the 'store'. 389 """ 390 391 remove_period(freebusy, uid) 392 store.set_freebusy_for_other(user, freebusy, other) 393 394 def _update_freebusy(freebusy, periods, transp, uid): 395 396 """ 397 Update the free/busy details with the given 'periods', 'transp' setting and 398 'uid'. 399 """ 400 401 remove_period(freebusy, uid) 402 403 for start, end in periods: 404 insert_period(freebusy, (start, end, uid, transp)) 405 406 def update_freebusy(freebusy, attendee, periods, transp, uid, store): 407 408 """ 409 For the given 'attendee', update the free/busy details with the given 410 'periods', 'transp' setting and 'uid' in the 'store'. 411 """ 412 413 _update_freebusy(freebusy, periods, transp, uid) 414 store.set_freebusy(attendee, freebusy) 415 416 def update_freebusy_for_other(freebusy, user, other, periods, transp, uid, store): 417 418 """ 419 For the given 'user', update the free/busy details of 'other' with the given 420 'periods', 'transp' setting and 'uid' in the 'store'. 421 """ 422 423 _update_freebusy(freebusy, periods, transp, uid) 424 store.set_freebusy_for_other(user, freebusy, other) 425 426 427 # vim: tabstop=4 expandtab shiftwidth=4