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