imip-agent

imiptools/period.py

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