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