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