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