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