| 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@430 | 22 | from bisect import bisect_left, bisect_right, insort_left |
| paul@529 | 23 | from datetime import date, datetime, timedelta |
| paul@529 | 24 | from imiptools.dates import format_datetime, get_datetime, \ |
| paul@563 | 25 | get_datetime_attributes, \ |
| paul@563 | 26 | get_recurrence_start, get_recurrence_start_point, \ |
| paul@563 | 27 | get_start_of_day, \ |
| paul@563 | 28 | get_tzid, \ |
| paul@563 | 29 | to_timezone, to_utc_datetime |
| paul@48 | 30 | |
| paul@874 | 31 | class Comparable: |
| paul@874 | 32 | |
| paul@874 | 33 | "A date/datetime wrapper that allows comparisons with other types." |
| paul@874 | 34 | |
| paul@874 | 35 | def __init__(self, dt): |
| paul@874 | 36 | self.dt = dt |
| paul@874 | 37 | |
| paul@874 | 38 | def __cmp__(self, other): |
| paul@874 | 39 | dt = None |
| paul@874 | 40 | odt = None |
| paul@874 | 41 | |
| paul@874 | 42 | # Find any dates/datetimes. |
| paul@874 | 43 | |
| paul@874 | 44 | if isinstance(self.dt, date): |
| paul@874 | 45 | dt = self.dt |
| paul@874 | 46 | if isinstance(other, date): |
| paul@874 | 47 | odt = other |
| paul@874 | 48 | elif isinstance(other, Comparable): |
| paul@874 | 49 | if isinstance(other.dt, date): |
| paul@874 | 50 | odt = other.dt |
| paul@874 | 51 | else: |
| paul@874 | 52 | other = other.dt |
| paul@874 | 53 | |
| paul@874 | 54 | if dt and odt: |
| paul@874 | 55 | return cmp(dt, odt) |
| paul@874 | 56 | elif dt: |
| paul@874 | 57 | return other.__rcmp__(dt) |
| paul@874 | 58 | elif odt: |
| paul@874 | 59 | return self.dt.__cmp__(odt) |
| paul@874 | 60 | else: |
| paul@874 | 61 | return self.dt.__cmp__(other) |
| paul@874 | 62 | |
| paul@874 | 63 | class PointInTime: |
| paul@874 | 64 | |
| paul@874 | 65 | "A base class for special values." |
| paul@874 | 66 | |
| paul@874 | 67 | pass |
| paul@874 | 68 | |
| paul@874 | 69 | class StartOfTime(PointInTime): |
| paul@874 | 70 | |
| paul@874 | 71 | "A special value that compares earlier than other values." |
| paul@874 | 72 | |
| paul@874 | 73 | def __cmp__(self, other): |
| paul@874 | 74 | if isinstance(other, StartOfTime): |
| paul@874 | 75 | return 0 |
| paul@874 | 76 | else: |
| paul@874 | 77 | return -1 |
| paul@874 | 78 | |
| paul@874 | 79 | def __rcmp__(self, other): |
| paul@874 | 80 | return -self.__cmp__(other) |
| paul@874 | 81 | |
| paul@874 | 82 | class EndOfTime(PointInTime): |
| paul@874 | 83 | |
| paul@874 | 84 | "A special value that compares later than other values." |
| paul@874 | 85 | |
| paul@874 | 86 | def __cmp__(self, other): |
| paul@874 | 87 | if isinstance(other, EndOfTime): |
| paul@874 | 88 | return 0 |
| paul@874 | 89 | else: |
| paul@874 | 90 | return 1 |
| paul@874 | 91 | |
| paul@874 | 92 | def __rcmp__(self, other): |
| paul@874 | 93 | return -self.__cmp__(other) |
| paul@874 | 94 | |
| paul@646 | 95 | class PeriodBase: |
| paul@458 | 96 | |
| paul@458 | 97 | "A basic period abstraction." |
| paul@458 | 98 | |
| paul@646 | 99 | def as_tuple(self): |
| paul@646 | 100 | return self.start, self.end |
| paul@646 | 101 | |
| paul@646 | 102 | def __hash__(self): |
| paul@646 | 103 | return hash((self.get_start(), self.get_end())) |
| paul@646 | 104 | |
| paul@646 | 105 | def __cmp__(self, other): |
| paul@646 | 106 | |
| paul@646 | 107 | "Return a comparison result against 'other' using points in time." |
| paul@646 | 108 | |
| paul@646 | 109 | if isinstance(other, PeriodBase): |
| paul@646 | 110 | return cmp( |
| paul@874 | 111 | (Comparable(self.get_start_point() or StartOfTime()), Comparable(self.get_end_point() or EndOfTime())), |
| paul@874 | 112 | (Comparable(other.get_start_point() or StartOfTime()), Comparable(other.get_end_point() or EndOfTime())) |
| paul@646 | 113 | ) |
| paul@646 | 114 | else: |
| paul@646 | 115 | return 1 |
| paul@646 | 116 | |
| paul@874 | 117 | def overlaps(self, other): |
| paul@874 | 118 | return Comparable(self.get_end_point()) > Comparable(other.get_start_point()) and \ |
| paul@874 | 119 | Comparable(self.get_start_point()) < Comparable(other.get_end_point()) |
| paul@874 | 120 | |
| paul@646 | 121 | def get_key(self): |
| paul@646 | 122 | return self.get_start(), self.get_end() |
| paul@646 | 123 | |
| paul@646 | 124 | # Datetime and metadata methods. |
| paul@646 | 125 | |
| paul@646 | 126 | def get_start(self): |
| paul@646 | 127 | return self.start |
| paul@646 | 128 | |
| paul@646 | 129 | def get_end(self): |
| paul@646 | 130 | return self.end |
| paul@646 | 131 | |
| paul@646 | 132 | def get_start_attr(self): |
| paul@646 | 133 | return get_datetime_attributes(self.start, self.tzid) |
| paul@646 | 134 | |
| paul@646 | 135 | def get_end_attr(self): |
| paul@646 | 136 | return get_datetime_attributes(self.end, self.tzid) |
| paul@646 | 137 | |
| paul@646 | 138 | def get_start_item(self): |
| paul@646 | 139 | return self.get_start(), self.get_start_attr() |
| paul@646 | 140 | |
| paul@646 | 141 | def get_end_item(self): |
| paul@646 | 142 | return self.get_end(), self.get_end_attr() |
| paul@646 | 143 | |
| paul@646 | 144 | def get_start_point(self): |
| paul@646 | 145 | return self.start |
| paul@646 | 146 | |
| paul@646 | 147 | def get_end_point(self): |
| paul@646 | 148 | return self.end |
| paul@646 | 149 | |
| paul@659 | 150 | def get_duration(self): |
| paul@659 | 151 | return self.get_end_point() - self.get_start_point() |
| paul@659 | 152 | |
| paul@646 | 153 | class Period(PeriodBase): |
| paul@646 | 154 | |
| paul@646 | 155 | "A simple period abstraction." |
| paul@646 | 156 | |
| paul@541 | 157 | def __init__(self, start, end, tzid=None, origin=None): |
| paul@541 | 158 | |
| paul@541 | 159 | """ |
| paul@541 | 160 | Initialise a period with the given 'start' and 'end', having a |
| paul@541 | 161 | contextual 'tzid', if specified, and an indicated 'origin'. |
| paul@620 | 162 | |
| paul@620 | 163 | All metadata from the start and end points are derived from the supplied |
| paul@620 | 164 | dates/datetimes. |
| paul@541 | 165 | """ |
| paul@541 | 166 | |
| paul@874 | 167 | self.start = isinstance(start, date) and start or isinstance(start, PointInTime) and start or get_datetime(start) or StartOfTime() |
| paul@874 | 168 | self.end = isinstance(end, date) and end or isinstance(end, PointInTime) and end or get_datetime(end) or EndOfTime() |
| paul@541 | 169 | self.tzid = tzid |
| paul@528 | 170 | self.origin = origin |
| paul@458 | 171 | |
| paul@458 | 172 | def as_tuple(self): |
| paul@541 | 173 | return self.start, self.end, self.tzid, self.origin |
| paul@458 | 174 | |
| paul@458 | 175 | def __repr__(self): |
| paul@630 | 176 | return "Period%r" % (self.as_tuple(),) |
| paul@458 | 177 | |
| paul@646 | 178 | # Datetime and metadata methods. |
| paul@528 | 179 | |
| paul@541 | 180 | def get_tzid(self): |
| paul@620 | 181 | return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid |
| paul@620 | 182 | |
| paul@557 | 183 | def get_start_point(self): |
| paul@874 | 184 | start = self.get_start() |
| paul@874 | 185 | return isinstance(start, PointInTime) and start or to_utc_datetime(start, self.get_tzid()) |
| paul@557 | 186 | |
| paul@557 | 187 | def get_end_point(self): |
| paul@874 | 188 | end = self.get_end() |
| paul@874 | 189 | return isinstance(end, PointInTime) and end or to_utc_datetime(end, self.get_tzid()) |
| paul@557 | 190 | |
| paul@633 | 191 | # Period and event recurrence logic. |
| paul@633 | 192 | |
| paul@633 | 193 | def is_replaced(self, recurrenceids): |
| paul@633 | 194 | |
| paul@633 | 195 | """ |
| paul@633 | 196 | Return whether this period refers to one of the 'recurrenceids'. |
| paul@633 | 197 | The 'recurrenceids' should be normalised to UTC datetimes according to |
| paul@633 | 198 | time zone information provided by their objects or be floating dates or |
| paul@633 | 199 | datetimes requiring conversion using contextual time zone information. |
| paul@633 | 200 | """ |
| paul@633 | 201 | |
| paul@633 | 202 | for recurrenceid in recurrenceids: |
| paul@647 | 203 | if self.is_affected(recurrenceid): |
| paul@633 | 204 | return recurrenceid |
| paul@633 | 205 | return None |
| paul@633 | 206 | |
| paul@633 | 207 | def is_affected(self, recurrenceid): |
| paul@633 | 208 | |
| paul@633 | 209 | """ |
| paul@633 | 210 | Return whether this period refers to 'recurrenceid'. The 'recurrenceid' |
| paul@633 | 211 | should be normalised to UTC datetimes according to time zone information |
| paul@633 | 212 | provided by their objects. Otherwise, this period's contextual time zone |
| paul@633 | 213 | information is used to convert any date or floating datetime |
| paul@633 | 214 | representation to a point in time. |
| paul@633 | 215 | """ |
| paul@633 | 216 | |
| paul@633 | 217 | if not recurrenceid: |
| paul@633 | 218 | return None |
| paul@633 | 219 | d = get_recurrence_start(recurrenceid) |
| paul@633 | 220 | dt = get_recurrence_start_point(recurrenceid, self.tzid) |
| paul@633 | 221 | if self.get_start() == d or self.get_start_point() == dt: |
| paul@633 | 222 | return recurrenceid |
| paul@633 | 223 | return None |
| paul@633 | 224 | |
| paul@646 | 225 | class FreeBusyPeriod(PeriodBase): |
| paul@458 | 226 | |
| paul@458 | 227 | "A free/busy record abstraction." |
| paul@458 | 228 | |
| paul@710 | 229 | def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None): |
| paul@529 | 230 | |
| paul@529 | 231 | """ |
| paul@643 | 232 | Initialise a free/busy period with the given 'start' and 'end' points, |
| paul@646 | 233 | plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' |
| paul@646 | 234 | details. |
| paul@710 | 235 | |
| paul@710 | 236 | An additional 'expires' parameter can be used to indicate an expiry |
| paul@710 | 237 | datetime in conjunction with free/busy offers made when countering |
| paul@710 | 238 | event proposals. |
| paul@529 | 239 | """ |
| paul@529 | 240 | |
| paul@646 | 241 | self.start = isinstance(start, datetime) and start or get_datetime(start) |
| paul@646 | 242 | self.end = isinstance(end, datetime) and end or get_datetime(end) |
| paul@458 | 243 | self.uid = uid |
| paul@458 | 244 | self.transp = transp |
| paul@458 | 245 | self.recurrenceid = recurrenceid |
| paul@458 | 246 | self.summary = summary |
| paul@458 | 247 | self.organiser = organiser |
| paul@710 | 248 | self.expires = expires |
| paul@458 | 249 | |
| paul@563 | 250 | def as_tuple(self, strings_only=False): |
| paul@563 | 251 | |
| paul@563 | 252 | """ |
| paul@563 | 253 | Return the initialisation parameter tuple, converting false value |
| paul@563 | 254 | parameters to strings if 'strings_only' is set to a true value. |
| paul@563 | 255 | """ |
| paul@563 | 256 | |
| paul@563 | 257 | null = lambda x: (strings_only and [""] or [x])[0] |
| paul@563 | 258 | return ( |
| paul@630 | 259 | strings_only and format_datetime(self.get_start_point()) or self.start, |
| paul@630 | 260 | strings_only and format_datetime(self.get_end_point()) or self.end, |
| paul@563 | 261 | self.uid or null(self.uid), |
| paul@563 | 262 | self.transp or strings_only and "OPAQUE" or None, |
| paul@563 | 263 | self.recurrenceid or null(self.recurrenceid), |
| paul@563 | 264 | self.summary or null(self.summary), |
| paul@710 | 265 | self.organiser or null(self.organiser), |
| paul@710 | 266 | self.expires or null(self.expires) |
| paul@563 | 267 | ) |
| paul@458 | 268 | |
| paul@458 | 269 | def __cmp__(self, other): |
| paul@541 | 270 | |
| paul@541 | 271 | """ |
| paul@541 | 272 | Compare this object to 'other', employing the uid if the periods |
| paul@541 | 273 | involved are the same. |
| paul@541 | 274 | """ |
| paul@541 | 275 | |
| paul@646 | 276 | result = PeriodBase.__cmp__(self, other) |
| paul@541 | 277 | if result == 0 and isinstance(other, FreeBusyPeriod): |
| paul@653 | 278 | return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) |
| paul@458 | 279 | else: |
| paul@541 | 280 | return result |
| paul@458 | 281 | |
| paul@458 | 282 | def get_key(self): |
| paul@541 | 283 | return self.uid, self.recurrenceid, self.get_start() |
| paul@458 | 284 | |
| paul@458 | 285 | def __repr__(self): |
| paul@630 | 286 | return "FreeBusyPeriod%r" % (self.as_tuple(),) |
| paul@458 | 287 | |
| paul@679 | 288 | # Period and event recurrence logic. |
| paul@679 | 289 | |
| paul@679 | 290 | def is_replaced(self, recurrences): |
| paul@679 | 291 | |
| paul@679 | 292 | """ |
| paul@679 | 293 | Return whether this period refers to one of the 'recurrences'. |
| paul@679 | 294 | The 'recurrences' must be UTC datetimes corresponding to the start of |
| paul@679 | 295 | the period described by a recurrence. |
| paul@679 | 296 | """ |
| paul@679 | 297 | |
| paul@679 | 298 | for recurrence in recurrences: |
| paul@679 | 299 | if self.is_affected(recurrence): |
| paul@679 | 300 | return True |
| paul@679 | 301 | return False |
| paul@679 | 302 | |
| paul@679 | 303 | def is_affected(self, recurrence): |
| paul@679 | 304 | |
| paul@679 | 305 | """ |
| paul@679 | 306 | Return whether this period refers to 'recurrence'. The 'recurrence' must |
| paul@679 | 307 | be a UTC datetime corresponding to the start of the period described by |
| paul@679 | 308 | a recurrence. |
| paul@679 | 309 | """ |
| paul@679 | 310 | |
| paul@679 | 311 | return recurrence and self.get_start_point() == recurrence |
| paul@679 | 312 | |
| paul@543 | 313 | class RecurringPeriod(Period): |
| paul@543 | 314 | |
| paul@620 | 315 | """ |
| paul@620 | 316 | A period with iCalendar metadata attributes and origin information from an |
| paul@620 | 317 | object. |
| paul@620 | 318 | """ |
| paul@543 | 319 | |
| paul@543 | 320 | def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): |
| paul@543 | 321 | Period.__init__(self, start, end, tzid, origin) |
| paul@543 | 322 | self.start_attr = start_attr |
| paul@543 | 323 | self.end_attr = end_attr |
| paul@543 | 324 | |
| paul@620 | 325 | def get_start_attr(self): |
| paul@620 | 326 | return self.start_attr |
| paul@543 | 327 | |
| paul@620 | 328 | def get_end_attr(self): |
| paul@620 | 329 | return self.end_attr |
| paul@543 | 330 | |
| paul@543 | 331 | def as_tuple(self): |
| paul@543 | 332 | return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr |
| paul@543 | 333 | |
| paul@543 | 334 | def __repr__(self): |
| paul@630 | 335 | return "RecurringPeriod%r" % (self.as_tuple(),) |
| paul@543 | 336 | |
| paul@529 | 337 | # Time and period management. |
| paul@48 | 338 | |
| paul@343 | 339 | def can_schedule(freebusy, periods, uid, recurrenceid): |
| paul@221 | 340 | |
| paul@221 | 341 | """ |
| paul@221 | 342 | Return whether the 'freebusy' list can accommodate the given 'periods' |
| paul@343 | 343 | employing the specified 'uid' and 'recurrenceid'. |
| paul@221 | 344 | """ |
| paul@221 | 345 | |
| paul@221 | 346 | for conflict in have_conflict(freebusy, periods, True): |
| paul@465 | 347 | if conflict.uid != uid or conflict.recurrenceid != recurrenceid: |
| paul@221 | 348 | return False |
| paul@221 | 349 | |
| paul@221 | 350 | return True |
| paul@221 | 351 | |
| paul@72 | 352 | def have_conflict(freebusy, periods, get_conflicts=False): |
| paul@72 | 353 | |
| paul@72 | 354 | """ |
| paul@72 | 355 | Return whether any period in 'freebusy' overlaps with the given 'periods', |
| paul@72 | 356 | returning a collection of such overlapping periods if 'get_conflicts' is |
| paul@72 | 357 | set to a true value. |
| paul@72 | 358 | """ |
| paul@72 | 359 | |
| paul@458 | 360 | conflicts = set() |
| paul@458 | 361 | for p in periods: |
| paul@458 | 362 | overlapping = period_overlaps(freebusy, p, get_conflicts) |
| paul@74 | 363 | if overlapping: |
| paul@72 | 364 | if get_conflicts: |
| paul@458 | 365 | conflicts.update(overlapping) |
| paul@72 | 366 | else: |
| paul@72 | 367 | return True |
| paul@74 | 368 | |
| paul@72 | 369 | if get_conflicts: |
| paul@72 | 370 | return conflicts |
| paul@72 | 371 | else: |
| paul@72 | 372 | return False |
| paul@72 | 373 | |
| paul@48 | 374 | def insert_period(freebusy, period): |
| paul@362 | 375 | |
| paul@362 | 376 | "Insert into 'freebusy' the given 'period'." |
| paul@362 | 377 | |
| paul@653 | 378 | i = bisect_left(freebusy, period) |
| paul@653 | 379 | if i == len(freebusy): |
| paul@653 | 380 | freebusy.append(period) |
| paul@653 | 381 | elif freebusy[i] != period: |
| paul@653 | 382 | freebusy.insert(i, period) |
| paul@48 | 383 | |
| paul@343 | 384 | def remove_period(freebusy, uid, recurrenceid=None): |
| paul@362 | 385 | |
| paul@362 | 386 | """ |
| paul@362 | 387 | Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' |
| paul@362 | 388 | (which if omitted causes the "parent" object's periods to be referenced). |
| paul@362 | 389 | """ |
| paul@362 | 390 | |
| paul@523 | 391 | removed = False |
| paul@48 | 392 | i = 0 |
| paul@48 | 393 | while i < len(freebusy): |
| paul@458 | 394 | fb = freebusy[i] |
| paul@458 | 395 | if fb.uid == uid and fb.recurrenceid == recurrenceid: |
| paul@48 | 396 | del freebusy[i] |
| paul@523 | 397 | removed = True |
| paul@48 | 398 | else: |
| paul@48 | 399 | i += 1 |
| paul@48 | 400 | |
| paul@523 | 401 | return removed |
| paul@523 | 402 | |
| paul@382 | 403 | def remove_additional_periods(freebusy, uid, recurrenceids=None): |
| paul@381 | 404 | |
| paul@381 | 405 | """ |
| paul@381 | 406 | Remove from 'freebusy' all periods associated with 'uid' having a |
| paul@381 | 407 | recurrence identifier indicating an additional or modified period. |
| paul@382 | 408 | |
| paul@382 | 409 | If 'recurrenceids' is specified, remove all periods associated with 'uid' |
| paul@382 | 410 | that do not have a recurrence identifier in the given list. |
| paul@381 | 411 | """ |
| paul@381 | 412 | |
| paul@381 | 413 | i = 0 |
| paul@381 | 414 | while i < len(freebusy): |
| paul@458 | 415 | fb = freebusy[i] |
| paul@458 | 416 | if fb.uid == uid and fb.recurrenceid and ( |
| paul@382 | 417 | recurrenceids is None or |
| paul@458 | 418 | recurrenceids is not None and fb.recurrenceid not in recurrenceids |
| paul@382 | 419 | ): |
| paul@381 | 420 | del freebusy[i] |
| paul@381 | 421 | else: |
| paul@381 | 422 | i += 1 |
| paul@381 | 423 | |
| paul@511 | 424 | def remove_affected_period(freebusy, uid, start): |
| paul@362 | 425 | |
| paul@362 | 426 | """ |
| paul@362 | 427 | Remove from 'freebusy' a period associated with 'uid' that provides an |
| paul@511 | 428 | occurrence starting at the given 'start' (provided by a recurrence |
| paul@511 | 429 | identifier, converted to a datetime). A recurrence identifier is used to |
| paul@511 | 430 | provide an alternative time period whilst also acting as a reference to the |
| paul@511 | 431 | originally-defined occurrence. |
| paul@362 | 432 | """ |
| paul@362 | 433 | |
| paul@558 | 434 | search = Period(start, start) |
| paul@558 | 435 | found = bisect_left(freebusy, search) |
| paul@558 | 436 | |
| paul@376 | 437 | while found < len(freebusy): |
| paul@458 | 438 | fb = freebusy[found] |
| paul@376 | 439 | |
| paul@376 | 440 | # Stop looking if the start no longer matches the recurrence identifier. |
| paul@376 | 441 | |
| paul@558 | 442 | if fb.get_start_point() != search.get_start_point(): |
| paul@376 | 443 | return |
| paul@376 | 444 | |
| paul@376 | 445 | # If the period belongs to the parent object, remove it and return. |
| paul@376 | 446 | |
| paul@458 | 447 | if not fb.recurrenceid and uid == fb.uid: |
| paul@361 | 448 | del freebusy[found] |
| paul@376 | 449 | break |
| paul@376 | 450 | |
| paul@376 | 451 | # Otherwise, keep looking for a matching period. |
| paul@376 | 452 | |
| paul@376 | 453 | found += 1 |
| paul@361 | 454 | |
| paul@658 | 455 | def periods_from(freebusy, period): |
| paul@658 | 456 | |
| paul@658 | 457 | "Return the entries in 'freebusy' at or after 'period'." |
| paul@658 | 458 | |
| paul@658 | 459 | first = bisect_left(freebusy, period) |
| paul@658 | 460 | return freebusy[first:] |
| paul@658 | 461 | |
| paul@658 | 462 | def periods_until(freebusy, period): |
| paul@658 | 463 | |
| paul@658 | 464 | "Return the entries in 'freebusy' before 'period'." |
| paul@658 | 465 | |
| paul@658 | 466 | last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) |
| paul@658 | 467 | return freebusy[:last] |
| paul@658 | 468 | |
| paul@327 | 469 | def get_overlapping(freebusy, period): |
| paul@327 | 470 | |
| paul@327 | 471 | """ |
| paul@430 | 472 | Return the entries in 'freebusy' providing periods overlapping with |
| paul@327 | 473 | 'period'. |
| paul@327 | 474 | """ |
| paul@327 | 475 | |
| paul@430 | 476 | # Find the range of periods potentially overlapping the period in the |
| paul@430 | 477 | # free/busy collection. |
| paul@327 | 478 | |
| paul@658 | 479 | startpoints = periods_until(freebusy, period) |
| paul@327 | 480 | |
| paul@430 | 481 | # Find the range of periods potentially overlapping the period in a version |
| paul@430 | 482 | # of the free/busy collection sorted according to end datetimes. |
| paul@327 | 483 | |
| paul@874 | 484 | endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] |
| paul@430 | 485 | endpoints.sort() |
| paul@874 | 486 | first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) |
| paul@430 | 487 | endpoints = endpoints[first:] |
| paul@327 | 488 | |
| paul@430 | 489 | overlapping = set() |
| paul@327 | 490 | |
| paul@874 | 491 | for p, fb in endpoints: |
| paul@874 | 492 | if fb.overlaps(period): |
| paul@458 | 493 | overlapping.add(fb) |
| paul@327 | 494 | |
| paul@430 | 495 | overlapping = list(overlapping) |
| paul@430 | 496 | overlapping.sort() |
| paul@430 | 497 | return overlapping |
| paul@327 | 498 | |
| paul@74 | 499 | def period_overlaps(freebusy, period, get_periods=False): |
| paul@72 | 500 | |
| paul@72 | 501 | """ |
| paul@74 | 502 | Return whether any period in 'freebusy' overlaps with the given 'period', |
| paul@74 | 503 | returning a collection of overlapping periods if 'get_periods' is set to a |
| paul@74 | 504 | true value. |
| paul@72 | 505 | """ |
| paul@72 | 506 | |
| paul@430 | 507 | overlapping = get_overlapping(freebusy, period) |
| paul@74 | 508 | |
| paul@74 | 509 | if get_periods: |
| paul@430 | 510 | return overlapping |
| paul@74 | 511 | else: |
| paul@430 | 512 | return len(overlapping) != 0 |
| paul@327 | 513 | |
| paul@327 | 514 | def remove_overlapping(freebusy, period): |
| paul@327 | 515 | |
| paul@327 | 516 | "Remove from 'freebusy' all periods overlapping with 'period'." |
| paul@327 | 517 | |
| paul@437 | 518 | overlapping = get_overlapping(freebusy, period) |
| paul@327 | 519 | |
| paul@437 | 520 | if overlapping: |
| paul@437 | 521 | for fb in overlapping: |
| paul@437 | 522 | freebusy.remove(fb) |
| paul@327 | 523 | |
| paul@327 | 524 | def replace_overlapping(freebusy, period, replacements): |
| paul@327 | 525 | |
| paul@327 | 526 | """ |
| paul@327 | 527 | Replace existing periods in 'freebusy' within the given 'period', using the |
| paul@327 | 528 | given 'replacements'. |
| paul@327 | 529 | """ |
| paul@327 | 530 | |
| paul@327 | 531 | remove_overlapping(freebusy, period) |
| paul@327 | 532 | for replacement in replacements: |
| paul@327 | 533 | insert_period(freebusy, replacement) |
| paul@48 | 534 | |
| paul@658 | 535 | def coalesce_freebusy(freebusy): |
| paul@658 | 536 | |
| paul@658 | 537 | "Coalesce the periods in 'freebusy'." |
| paul@658 | 538 | |
| paul@658 | 539 | if not freebusy: |
| paul@658 | 540 | return freebusy |
| paul@658 | 541 | |
| paul@658 | 542 | fb = [] |
| paul@658 | 543 | start = freebusy[0].get_start_point() |
| paul@658 | 544 | end = freebusy[0].get_end_point() |
| paul@658 | 545 | |
| paul@658 | 546 | for period in freebusy[1:]: |
| paul@658 | 547 | if period.get_start_point() > end: |
| paul@658 | 548 | fb.append(FreeBusyPeriod(start, end)) |
| paul@658 | 549 | start = period.get_start_point() |
| paul@658 | 550 | end = period.get_end_point() |
| paul@658 | 551 | else: |
| paul@658 | 552 | end = max(end, period.get_end_point()) |
| paul@658 | 553 | |
| paul@658 | 554 | fb.append(FreeBusyPeriod(start, end)) |
| paul@658 | 555 | return fb |
| paul@658 | 556 | |
| paul@658 | 557 | def invert_freebusy(freebusy): |
| paul@658 | 558 | |
| paul@658 | 559 | "Return the free periods from 'freebusy'." |
| paul@658 | 560 | |
| paul@658 | 561 | if not freebusy: |
| paul@658 | 562 | return None |
| paul@658 | 563 | |
| paul@658 | 564 | fb = coalesce_freebusy(freebusy) |
| paul@658 | 565 | free = [] |
| paul@658 | 566 | start = fb[0].get_end_point() |
| paul@658 | 567 | |
| paul@658 | 568 | for period in fb[1:]: |
| paul@658 | 569 | free.append(FreeBusyPeriod(start, period.get_start_point())) |
| paul@658 | 570 | start = period.get_end_point() |
| paul@658 | 571 | |
| paul@658 | 572 | return free |
| paul@658 | 573 | |
| paul@529 | 574 | # Period layout. |
| paul@204 | 575 | |
| paul@884 | 576 | def get_scale(periods, tzid, view_period=None): |
| paul@113 | 577 | |
| paul@113 | 578 | """ |
| paul@458 | 579 | Return an ordered time scale from the given list of 'periods'. |
| paul@153 | 580 | |
| paul@162 | 581 | The given 'tzid' is used to make sure that the times are defined according |
| paul@162 | 582 | to the chosen time zone. |
| paul@162 | 583 | |
| paul@884 | 584 | An optional 'view_period' is used to constrain the scale to the given |
| paul@884 | 585 | period. |
| paul@884 | 586 | |
| paul@162 | 587 | The returned scale is a mapping from time to (starting, ending) tuples, |
| paul@458 | 588 | where starting and ending are collections of periods. |
| paul@113 | 589 | """ |
| paul@113 | 590 | |
| paul@113 | 591 | scale = {} |
| paul@884 | 592 | view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None |
| paul@884 | 593 | view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None |
| paul@113 | 594 | |
| paul@458 | 595 | for p in periods: |
| paul@113 | 596 | |
| paul@113 | 597 | # Add a point and this event to the starting list. |
| paul@113 | 598 | |
| paul@536 | 599 | start = to_timezone(p.get_start(), tzid) |
| paul@884 | 600 | start = view_start and max(start, view_start) or start |
| paul@536 | 601 | if not scale.has_key(start): |
| paul@536 | 602 | scale[start] = [], [] |
| paul@536 | 603 | scale[start][0].append(p) |
| paul@113 | 604 | |
| paul@113 | 605 | # Add a point and this event to the ending list. |
| paul@113 | 606 | |
| paul@536 | 607 | end = to_timezone(p.get_end(), tzid) |
| paul@884 | 608 | end = view_end and min(end, view_end) or end |
| paul@536 | 609 | if not scale.has_key(end): |
| paul@536 | 610 | scale[end] = [], [] |
| paul@536 | 611 | scale[end][1].append(p) |
| paul@113 | 612 | |
| paul@113 | 613 | return scale |
| paul@113 | 614 | |
| paul@455 | 615 | class Point: |
| paul@455 | 616 | |
| paul@455 | 617 | "A qualified point in time." |
| paul@455 | 618 | |
| paul@455 | 619 | PRINCIPAL, REPEATED = 0, 1 |
| paul@455 | 620 | |
| paul@455 | 621 | def __init__(self, point, indicator=None): |
| paul@455 | 622 | self.point = point |
| paul@455 | 623 | self.indicator = indicator or self.PRINCIPAL |
| paul@455 | 624 | |
| paul@455 | 625 | def __hash__(self): |
| paul@455 | 626 | return hash((self.point, self.indicator)) |
| paul@455 | 627 | |
| paul@455 | 628 | def __cmp__(self, other): |
| paul@455 | 629 | if isinstance(other, Point): |
| paul@455 | 630 | return cmp((self.point, self.indicator), (other.point, other.indicator)) |
| paul@455 | 631 | elif isinstance(other, datetime): |
| paul@455 | 632 | return cmp(self.point, other) |
| paul@455 | 633 | else: |
| paul@455 | 634 | return 1 |
| paul@455 | 635 | |
| paul@455 | 636 | def __eq__(self, other): |
| paul@455 | 637 | return self.__cmp__(other) == 0 |
| paul@455 | 638 | |
| paul@455 | 639 | def __ne__(self, other): |
| paul@455 | 640 | return not self == other |
| paul@455 | 641 | |
| paul@455 | 642 | def __lt__(self, other): |
| paul@455 | 643 | return self.__cmp__(other) < 0 |
| paul@455 | 644 | |
| paul@455 | 645 | def __le__(self, other): |
| paul@455 | 646 | return self.__cmp__(other) <= 0 |
| paul@455 | 647 | |
| paul@455 | 648 | def __gt__(self, other): |
| paul@455 | 649 | return not self <= other |
| paul@455 | 650 | |
| paul@455 | 651 | def __ge__(self, other): |
| paul@455 | 652 | return not self < other |
| paul@455 | 653 | |
| paul@455 | 654 | def __repr__(self): |
| paul@455 | 655 | return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") |
| paul@452 | 656 | |
| paul@162 | 657 | def get_slots(scale): |
| paul@113 | 658 | |
| paul@113 | 659 | """ |
| paul@162 | 660 | Return an ordered list of time slots from the given 'scale'. |
| paul@113 | 661 | |
| paul@452 | 662 | Each slot is a tuple containing details of a point in time for the start of |
| paul@458 | 663 | the slot, together with a list of parallel event periods. |
| paul@452 | 664 | |
| paul@455 | 665 | Each point in time is described as a Point representing the actual point in |
| paul@455 | 666 | time together with an indicator of the nature of the point in time (as a |
| paul@455 | 667 | principal point in a time scale or as a repeated point used to terminate |
| paul@455 | 668 | events occurring for an instant in time). |
| paul@113 | 669 | """ |
| paul@113 | 670 | |
| paul@113 | 671 | slots = [] |
| paul@113 | 672 | active = [] |
| paul@113 | 673 | |
| paul@162 | 674 | points = scale.items() |
| paul@162 | 675 | points.sort() |
| paul@162 | 676 | |
| paul@162 | 677 | for point, (starting, ending) in points: |
| paul@449 | 678 | ending = set(ending) |
| paul@449 | 679 | instants = ending.intersection(starting) |
| paul@113 | 680 | |
| paul@113 | 681 | # Discard all active events ending at or before this start time. |
| paul@161 | 682 | # Free up the position in the active list. |
| paul@113 | 683 | |
| paul@449 | 684 | for t in ending.difference(instants): |
| paul@113 | 685 | i = active.index(t) |
| paul@113 | 686 | active[i] = None |
| paul@113 | 687 | |
| paul@161 | 688 | # For each event starting at the current point, fill any newly-vacated |
| paul@161 | 689 | # position or add to the end of the active list. |
| paul@161 | 690 | |
| paul@113 | 691 | for t in starting: |
| paul@113 | 692 | try: |
| paul@113 | 693 | i = active.index(None) |
| paul@113 | 694 | active[i] = t |
| paul@113 | 695 | except ValueError: |
| paul@113 | 696 | active.append(t) |
| paul@113 | 697 | |
| paul@161 | 698 | # Discard vacant positions from the end of the active list. |
| paul@161 | 699 | |
| paul@113 | 700 | while active and active[-1] is None: |
| paul@113 | 701 | active.pop() |
| paul@113 | 702 | |
| paul@452 | 703 | # Add an entry for the time point before "instants". |
| paul@452 | 704 | |
| paul@455 | 705 | slots.append((Point(point), active[:])) |
| paul@113 | 706 | |
| paul@449 | 707 | # Discard events ending at the same time as they began. |
| paul@449 | 708 | |
| paul@449 | 709 | if instants: |
| paul@449 | 710 | for t in instants: |
| paul@449 | 711 | i = active.index(t) |
| paul@449 | 712 | active[i] = None |
| paul@449 | 713 | |
| paul@449 | 714 | # Discard vacant positions from the end of the active list. |
| paul@449 | 715 | |
| paul@449 | 716 | while active and active[-1] is None: |
| paul@449 | 717 | active.pop() |
| paul@449 | 718 | |
| paul@452 | 719 | # Add another entry for the time point after "instants". |
| paul@449 | 720 | |
| paul@455 | 721 | slots.append((Point(point, Point.REPEATED), active[:])) |
| paul@449 | 722 | |
| paul@113 | 723 | return slots |
| paul@113 | 724 | |
| paul@244 | 725 | def add_day_start_points(slots, tzid): |
| paul@153 | 726 | |
| paul@153 | 727 | """ |
| paul@162 | 728 | Introduce into the 'slots' any day start points required by multi-day |
| paul@244 | 729 | periods. The 'tzid' is required to make sure that appropriate time zones |
| paul@244 | 730 | are chosen and not necessarily those provided by the existing time points. |
| paul@153 | 731 | """ |
| paul@153 | 732 | |
| paul@162 | 733 | new_slots = [] |
| paul@153 | 734 | current_date = None |
| paul@200 | 735 | previously_active = [] |
| paul@153 | 736 | |
| paul@455 | 737 | for point, active in slots: |
| paul@455 | 738 | start_of_day = get_start_of_day(point.point, tzid) |
| paul@455 | 739 | this_date = point.point.date() |
| paul@153 | 740 | |
| paul@198 | 741 | # For each new day, add a slot for the start of the day where periods |
| paul@198 | 742 | # are active and where no such slot already exists. |
| paul@153 | 743 | |
| paul@153 | 744 | if this_date != current_date: |
| paul@414 | 745 | |
| paul@414 | 746 | # Fill in days where events remain active. |
| paul@414 | 747 | |
| paul@414 | 748 | if current_date: |
| paul@414 | 749 | current_date += timedelta(1) |
| paul@414 | 750 | while current_date < this_date: |
| paul@455 | 751 | new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) |
| paul@414 | 752 | current_date += timedelta(1) |
| paul@414 | 753 | else: |
| paul@414 | 754 | current_date = this_date |
| paul@153 | 755 | |
| paul@153 | 756 | # Add any continuing periods. |
| paul@153 | 757 | |
| paul@455 | 758 | if point.point != start_of_day: |
| paul@455 | 759 | new_slots.append((Point(start_of_day), previously_active)) |
| paul@153 | 760 | |
| paul@153 | 761 | # Add the currently active periods at this point in time. |
| paul@153 | 762 | |
| paul@153 | 763 | previously_active = active |
| paul@153 | 764 | |
| paul@162 | 765 | for t in new_slots: |
| paul@162 | 766 | insort_left(slots, t) |
| paul@162 | 767 | |
| paul@162 | 768 | def add_slots(slots, points): |
| paul@162 | 769 | |
| paul@162 | 770 | """ |
| paul@162 | 771 | Introduce into the 'slots' entries for those in 'points' that are not |
| paul@170 | 772 | already present, propagating active periods from time points preceding |
| paul@170 | 773 | those added. |
| paul@162 | 774 | """ |
| paul@162 | 775 | |
| paul@162 | 776 | new_slots = [] |
| paul@162 | 777 | |
| paul@162 | 778 | for point in points: |
| paul@452 | 779 | i = bisect_left(slots, (point,)) # slots is [(point, active)...] |
| paul@162 | 780 | if i < len(slots) and slots[i][0] == point: |
| paul@162 | 781 | continue |
| paul@162 | 782 | |
| paul@170 | 783 | new_slots.append((point, i > 0 and slots[i-1][1] or [])) |
| paul@162 | 784 | |
| paul@162 | 785 | for t in new_slots: |
| paul@162 | 786 | insort_left(slots, t) |
| paul@162 | 787 | |
| paul@162 | 788 | def partition_by_day(slots): |
| paul@162 | 789 | |
| paul@162 | 790 | """ |
| paul@162 | 791 | Return a mapping from dates to time points provided by 'slots'. |
| paul@162 | 792 | """ |
| paul@162 | 793 | |
| paul@162 | 794 | d = {} |
| paul@162 | 795 | |
| paul@455 | 796 | for point, value in slots: |
| paul@455 | 797 | day = point.point.date() |
| paul@162 | 798 | if not d.has_key(day): |
| paul@162 | 799 | d[day] = [] |
| paul@455 | 800 | d[day].append((point, value)) |
| paul@162 | 801 | |
| paul@162 | 802 | return d |
| paul@153 | 803 | |
| paul@876 | 804 | def add_empty_days(days, tzid, start=None, end=None): |
| paul@279 | 805 | |
| paul@876 | 806 | """ |
| paul@876 | 807 | Add empty days to 'days' between busy days, and optionally from the given |
| paul@876 | 808 | 'start' day and until the given 'end' day. |
| paul@876 | 809 | """ |
| paul@279 | 810 | |
| paul@876 | 811 | last_day = start |
| paul@279 | 812 | all_days = days.keys() |
| paul@279 | 813 | all_days.sort() |
| paul@279 | 814 | |
| paul@279 | 815 | for day in all_days: |
| paul@279 | 816 | if last_day: |
| paul@279 | 817 | empty_day = last_day + timedelta(1) |
| paul@279 | 818 | while empty_day < day: |
| paul@455 | 819 | days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] |
| paul@279 | 820 | empty_day += timedelta(1) |
| paul@876 | 821 | last_day = day |
| paul@876 | 822 | |
| paul@876 | 823 | if end: |
| paul@876 | 824 | empty_day = last_day + timedelta(1) |
| paul@876 | 825 | while empty_day < end: |
| paul@876 | 826 | days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] |
| paul@876 | 827 | empty_day += timedelta(1) |
| paul@279 | 828 | |
| paul@114 | 829 | def get_spans(slots): |
| paul@114 | 830 | |
| paul@533 | 831 | "Inspect the given 'slots', returning a mapping of period keys to spans." |
| paul@114 | 832 | |
| paul@455 | 833 | points = [point for point, active in slots] |
| paul@114 | 834 | spans = {} |
| paul@114 | 835 | |
| paul@449 | 836 | for _point, active in slots: |
| paul@458 | 837 | for p in active: |
| paul@458 | 838 | if p: |
| paul@458 | 839 | key = p.get_key() |
| paul@529 | 840 | start_slot = bisect_left(points, p.get_start()) |
| paul@529 | 841 | end_slot = bisect_left(points, p.get_end()) |
| paul@185 | 842 | spans[key] = end_slot - start_slot |
| paul@114 | 843 | |
| paul@114 | 844 | return spans |
| paul@114 | 845 | |
| paul@740 | 846 | def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None): |
| paul@250 | 847 | |
| paul@250 | 848 | """ |
| paul@395 | 849 | Update the free/busy details with the given 'periods', 'transp' setting, |
| paul@395 | 850 | 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. |
| paul@740 | 851 | |
| paul@740 | 852 | An optional 'expires' datetime string indicates the expiry time of any |
| paul@740 | 853 | free/busy offer. |
| paul@250 | 854 | """ |
| paul@250 | 855 | |
| paul@343 | 856 | remove_period(freebusy, uid, recurrenceid) |
| paul@250 | 857 | |
| paul@458 | 858 | for p in periods: |
| paul@740 | 859 | insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) |
| paul@250 | 860 | |
| paul@48 | 861 | # vim: tabstop=4 expandtab shiftwidth=4 |
