#!/usr/bin/env python  """ Managing and presenting periods of time.  Copyright (C) 2014, 2015 Paul Boddie <paul@boddie.org.uk>  This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.  This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.  You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>. """  from bisect import bisect_left, bisect_right, insort_left from datetime import date, datetime, timedelta from imiptools.dates import format_datetime, get_datetime, \                             get_datetime_attributes, \                             get_recurrence_start, get_recurrence_start_point, \                             get_start_of_day, \                             get_tzid, \                             to_timezone, to_utc_datetime  class PeriodBase:      "A basic period abstraction."      def as_tuple(self):         return self.start, self.end      def __hash__(self):         return hash((self.get_start(), self.get_end()))      def __cmp__(self, other):          "Return a comparison result against 'other' using points in time."          if isinstance(other, PeriodBase):             return cmp(                 (self.get_start_point(), self.get_end_point()),                 (other.get_start_point(), other.get_end_point())                 )         else:             return 1      def get_key(self):         return self.get_start(), self.get_end()      # Datetime and metadata methods.      def get_start(self):         return self.start      def get_end(self):         return self.end      def get_start_attr(self):         return get_datetime_attributes(self.start, self.tzid)      def get_end_attr(self):         return get_datetime_attributes(self.end, self.tzid)      def get_start_item(self):         return self.get_start(), self.get_start_attr()      def get_end_item(self):         return self.get_end(), self.get_end_attr()      def get_start_point(self):         return self.start      def get_end_point(self):         return self.end      def get_duration(self):         return self.get_end_point() - self.get_start_point()  class Period(PeriodBase):      "A simple period abstraction."      def __init__(self, start, end, tzid=None, origin=None):          """         Initialise a period with the given 'start' and 'end', having a         contextual 'tzid', if specified, and an indicated 'origin'.          All metadata from the start and end points are derived from the supplied         dates/datetimes.         """          self.start = isinstance(start, date) and start or get_datetime(start)         self.end = isinstance(end, date) and end or get_datetime(end)         self.tzid = tzid         self.origin = origin      def as_tuple(self):         return self.start, self.end, self.tzid, self.origin      def __repr__(self):         return "Period%r" % (self.as_tuple(),)      # Datetime and metadata methods.      def get_tzid(self):         return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid      def get_start_point(self):         return to_utc_datetime(self.get_start(), self.get_tzid())      def get_end_point(self):         return to_utc_datetime(self.get_end(), self.get_tzid())      # Period and event recurrence logic.      def is_replaced(self, recurrenceids):          """         Return whether this period refers to one of the 'recurrenceids'.         The 'recurrenceids' should be normalised to UTC datetimes according to         time zone information provided by their objects or be floating dates or         datetimes requiring conversion using contextual time zone information.         """          for recurrenceid in recurrenceids:             if self.is_affected(recurrenceid):                 return recurrenceid         return None      def is_affected(self, recurrenceid):          """         Return whether this period refers to 'recurrenceid'. The 'recurrenceid'         should be normalised to UTC datetimes according to time zone information         provided by their objects. Otherwise, this period's contextual time zone         information is used to convert any date or floating datetime         representation to a point in time.         """          if not recurrenceid:             return None         d = get_recurrence_start(recurrenceid)         dt = get_recurrence_start_point(recurrenceid, self.tzid)         if self.get_start() == d or self.get_start_point() == dt:             return recurrenceid         return None  class FreeBusyPeriod(PeriodBase):      "A free/busy record abstraction."      def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None):          """         Initialise a free/busy period with the given 'start' and 'end' points,         plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser'         details.          An additional 'expires' parameter can be used to indicate an expiry         datetime in conjunction with free/busy offers made when countering         event proposals.         """          self.start = isinstance(start, datetime) and start or get_datetime(start)         self.end = isinstance(end, datetime) and end or get_datetime(end)         self.uid = uid         self.transp = transp         self.recurrenceid = recurrenceid         self.summary = summary         self.organiser = organiser         self.expires = expires      def as_tuple(self, strings_only=False):          """         Return the initialisation parameter tuple, converting false value         parameters to strings if 'strings_only' is set to a true value.         """          null = lambda x: (strings_only and [""] or [x])[0]         return (             strings_only and format_datetime(self.get_start_point()) or self.start,             strings_only and format_datetime(self.get_end_point()) or self.end,             self.uid or null(self.uid),             self.transp or strings_only and "OPAQUE" or None,             self.recurrenceid or null(self.recurrenceid),             self.summary or null(self.summary),             self.organiser or null(self.organiser),             self.expires or null(self.expires)             )      def __cmp__(self, other):          """         Compare this object to 'other', employing the uid if the periods         involved are the same.         """          result = PeriodBase.__cmp__(self, other)         if result == 0 and isinstance(other, FreeBusyPeriod):             return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid))         else:             return result      def get_key(self):         return self.uid, self.recurrenceid, self.get_start()      def __repr__(self):         return "FreeBusyPeriod%r" % (self.as_tuple(),)      # Period and event recurrence logic.      def is_replaced(self, recurrences):          """         Return whether this period refers to one of the 'recurrences'.         The 'recurrences' must be UTC datetimes corresponding to the start of         the period described by a recurrence.         """          for recurrence in recurrences:             if self.is_affected(recurrence):                 return True         return False      def is_affected(self, recurrence):          """         Return whether this period refers to 'recurrence'. The 'recurrence' must         be a UTC datetime corresponding to the start of the period described by         a recurrence.         """          return recurrence and self.get_start_point() == recurrence  class RecurringPeriod(Period):          """     A period with iCalendar metadata attributes and origin information from an     object.     """          def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None):         Period.__init__(self, start, end, tzid, origin)         self.start_attr = start_attr         self.end_attr = end_attr      def get_start_attr(self):         return self.start_attr      def get_end_attr(self):         return self.end_attr      def as_tuple(self):         return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr          def __repr__(self):         return "RecurringPeriod%r" % (self.as_tuple(),)  # Time and period management.  def can_schedule(freebusy, periods, uid, recurrenceid):      """     Return whether the 'freebusy' list can accommodate the given 'periods'     employing the specified 'uid' and 'recurrenceid'.     """      for conflict in have_conflict(freebusy, periods, True):         if conflict.uid != uid or conflict.recurrenceid != recurrenceid:             return False      return True  def have_conflict(freebusy, periods, get_conflicts=False):      """     Return whether any period in 'freebusy' overlaps with the given 'periods',     returning a collection of such overlapping periods if 'get_conflicts' is     set to a true value.     """      conflicts = set()     for p in periods:         overlapping = period_overlaps(freebusy, p, get_conflicts)         if overlapping:             if get_conflicts:                 conflicts.update(overlapping)             else:                 return True      if get_conflicts:         return conflicts     else:         return False  def insert_period(freebusy, period):      "Insert into 'freebusy' the given 'period'."      i = bisect_left(freebusy, period)     if i == len(freebusy):         freebusy.append(period)     elif freebusy[i] != period:         freebusy.insert(i, period)  def remove_period(freebusy, uid, recurrenceid=None):      """     Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid'     (which if omitted causes the "parent" object's periods to be referenced).     """      removed = False     i = 0     while i < len(freebusy):         fb = freebusy[i]         if fb.uid == uid and fb.recurrenceid == recurrenceid:             del freebusy[i]             removed = True         else:             i += 1      return removed  def remove_additional_periods(freebusy, uid, recurrenceids=None):      """     Remove from 'freebusy' all periods associated with 'uid' having a     recurrence identifier indicating an additional or modified period.      If 'recurrenceids' is specified, remove all periods associated with 'uid'     that do not have a recurrence identifier in the given list.     """      i = 0     while i < len(freebusy):         fb = freebusy[i]         if fb.uid == uid and fb.recurrenceid and (             recurrenceids is None or             recurrenceids is not None and fb.recurrenceid not in recurrenceids             ):             del freebusy[i]         else:             i += 1  def remove_affected_period(freebusy, uid, start):      """     Remove from 'freebusy' a period associated with 'uid' that provides an     occurrence starting at the given 'start' (provided by a recurrence     identifier, converted to a datetime). A recurrence identifier is used to     provide an alternative time period whilst also acting as a reference to the     originally-defined occurrence.     """      search = Period(start, start)     found = bisect_left(freebusy, search)      while found < len(freebusy):         fb = freebusy[found]          # Stop looking if the start no longer matches the recurrence identifier.          if fb.get_start_point() != search.get_start_point():             return          # If the period belongs to the parent object, remove it and return.          if not fb.recurrenceid and uid == fb.uid:             del freebusy[found]             break          # Otherwise, keep looking for a matching period.          found += 1  def periods_from(freebusy, period):      "Return the entries in 'freebusy' at or after 'period'."      first = bisect_left(freebusy, period)     return freebusy[first:]  def periods_until(freebusy, period):      "Return the entries in 'freebusy' before 'period'."      last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid()))     return freebusy[:last]  def get_overlapping(freebusy, period):      """     Return the entries in 'freebusy' providing periods overlapping with     'period'.     """      # Find the range of periods potentially overlapping the period in the     # free/busy collection.      startpoints = periods_until(freebusy, period)      # Find the range of periods potentially overlapping the period in a version     # of the free/busy collection sorted according to end datetimes.      endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints]     endpoints.sort()     first = bisect_left(endpoints, (period.get_start_point(),))     endpoints = endpoints[first:]      overlapping = set()      for end, start, fb in endpoints:         if end > period.get_start_point() and start < period.get_end_point():             overlapping.add(fb)      overlapping = list(overlapping)     overlapping.sort()     return overlapping  def period_overlaps(freebusy, period, get_periods=False):      """     Return whether any period in 'freebusy' overlaps with the given 'period',     returning a collection of overlapping periods if 'get_periods' is set to a     true value.     """      overlapping = get_overlapping(freebusy, period)      if get_periods:         return overlapping     else:         return len(overlapping) != 0  def remove_overlapping(freebusy, period):      "Remove from 'freebusy' all periods overlapping with 'period'."      overlapping = get_overlapping(freebusy, period)      if overlapping:         for fb in overlapping:             freebusy.remove(fb)  def replace_overlapping(freebusy, period, replacements):      """     Replace existing periods in 'freebusy' within the given 'period', using the     given 'replacements'.     """      remove_overlapping(freebusy, period)     for replacement in replacements:         insert_period(freebusy, replacement)  def coalesce_freebusy(freebusy):      "Coalesce the periods in 'freebusy'."      if not freebusy:         return freebusy      fb = []     start = freebusy[0].get_start_point()     end = freebusy[0].get_end_point()      for period in freebusy[1:]:         if period.get_start_point() > end:             fb.append(FreeBusyPeriod(start, end))             start = period.get_start_point()             end = period.get_end_point()         else:             end = max(end, period.get_end_point())      fb.append(FreeBusyPeriod(start, end))     return fb  def invert_freebusy(freebusy):      "Return the free periods from 'freebusy'."      if not freebusy:         return None      fb = coalesce_freebusy(freebusy)     free = []     start = fb[0].get_end_point()      for period in fb[1:]:         free.append(FreeBusyPeriod(start, period.get_start_point()))         start = period.get_end_point()      return free  # Period layout.  def get_scale(periods, tzid):      """     Return an ordered time scale from the given list of 'periods'.      The given 'tzid' is used to make sure that the times are defined according     to the chosen time zone.      The returned scale is a mapping from time to (starting, ending) tuples,     where starting and ending are collections of periods.     """      scale = {}      for p in periods:          # Add a point and this event to the starting list.          start = to_timezone(p.get_start(), tzid)         if not scale.has_key(start):             scale[start] = [], []         scale[start][0].append(p)          # Add a point and this event to the ending list.          end = to_timezone(p.get_end(), tzid)         if not scale.has_key(end):             scale[end] = [], []         scale[end][1].append(p)      return scale  class Point:      "A qualified point in time."      PRINCIPAL, REPEATED = 0, 1      def __init__(self, point, indicator=None):         self.point = point         self.indicator = indicator or self.PRINCIPAL      def __hash__(self):         return hash((self.point, self.indicator))      def __cmp__(self, other):         if isinstance(other, Point):             return cmp((self.point, self.indicator), (other.point, other.indicator))         elif isinstance(other, datetime):             return cmp(self.point, other)         else:             return 1      def __eq__(self, other):         return self.__cmp__(other) == 0      def __ne__(self, other):         return not self == other      def __lt__(self, other):         return self.__cmp__(other) < 0      def __le__(self, other):         return self.__cmp__(other) <= 0      def __gt__(self, other):         return not self <= other      def __ge__(self, other):         return not self < other      def __repr__(self):         return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL")  def get_slots(scale):      """     Return an ordered list of time slots from the given 'scale'.      Each slot is a tuple containing details of a point in time for the start of     the slot, together with a list of parallel event periods.      Each point in time is described as a Point representing the actual point in     time together with an indicator of the nature of the point in time (as a     principal point in a time scale or as a repeated point used to terminate     events occurring for an instant in time).     """      slots = []     active = []      points = scale.items()     points.sort()      for point, (starting, ending) in points:         ending = set(ending)         instants = ending.intersection(starting)          # Discard all active events ending at or before this start time.         # Free up the position in the active list.          for t in ending.difference(instants):             i = active.index(t)             active[i] = None          # For each event starting at the current point, fill any newly-vacated         # position or add to the end of the active list.          for t in starting:             try:                 i = active.index(None)                 active[i] = t             except ValueError:                 active.append(t)          # Discard vacant positions from the end of the active list.          while active and active[-1] is None:             active.pop()          # Add an entry for the time point before "instants".          slots.append((Point(point), active[:]))          # Discard events ending at the same time as they began.          if instants:             for t in instants:                 i = active.index(t)                 active[i] = None              # Discard vacant positions from the end of the active list.              while active and active[-1] is None:                 active.pop()              # Add another entry for the time point after "instants".              slots.append((Point(point, Point.REPEATED), active[:]))      return slots  def add_day_start_points(slots, tzid):      """     Introduce into the 'slots' any day start points required by multi-day     periods. The 'tzid' is required to make sure that appropriate time zones     are chosen and not necessarily those provided by the existing time points.     """      new_slots = []     current_date = None     previously_active = []      for point, active in slots:         start_of_day = get_start_of_day(point.point, tzid)         this_date = point.point.date()          # For each new day, add a slot for the start of the day where periods         # are active and where no such slot already exists.          if this_date != current_date:              # Fill in days where events remain active.              if current_date:                 current_date += timedelta(1)                 while current_date < this_date:                     new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active))                     current_date += timedelta(1)             else:                 current_date = this_date              # Add any continuing periods.              if point.point != start_of_day:                 new_slots.append((Point(start_of_day), previously_active))          # Add the currently active periods at this point in time.          previously_active = active      for t in new_slots:         insort_left(slots, t)  def add_slots(slots, points):      """     Introduce into the 'slots' entries for those in 'points' that are not     already present, propagating active periods from time points preceding     those added.     """      new_slots = []      for point in points:         i = bisect_left(slots, (point,)) # slots is [(point, active)...]         if i < len(slots) and slots[i][0] == point:             continue          new_slots.append((point, i > 0 and slots[i-1][1] or []))      for t in new_slots:         insort_left(slots, t)  def partition_by_day(slots):      """     Return a mapping from dates to time points provided by 'slots'.     """      d = {}      for point, value in slots:         day = point.point.date()         if not d.has_key(day):             d[day] = []         d[day].append((point, value))      return d  def add_empty_days(days, tzid):      "Add empty days to 'days' between busy days."      last_day = None     all_days = days.keys()     all_days.sort()      for day in all_days:         if last_day:             empty_day = last_day + timedelta(1)             while empty_day < day:                 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)]                 empty_day += timedelta(1)         last_day = day   def get_spans(slots):      "Inspect the given 'slots', returning a mapping of period keys to spans."      points = [point for point, active in slots]     spans = {}      for _point, active in slots:         for p in active:             if p:                 key = p.get_key()                 start_slot = bisect_left(points, p.get_start())                 end_slot = bisect_left(points, p.get_end())                 spans[key] = end_slot - start_slot      return spans  def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None):      """     Update the free/busy details with the given 'periods', 'transp' setting,     'uid' plus 'recurrenceid' and 'summary' and 'organiser' details.      An optional 'expires' datetime string indicates the expiry time of any     free/busy offer.     """      remove_period(freebusy, uid, recurrenceid)      for p in periods:         insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires))  # vim: tabstop=4 expandtab shiftwidth=4