#!/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_start_of_day, \                             get_tzid, to_timezone, to_utc_datetime  class Period:      "A basic 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'.         """          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 __hash__(self):         return hash((self.get_start(), self.get_end()))      def __cmp__(self, other):          """         Return a comparison result against 'other' using points in time,         employing the time zone context to convert dates.         """          if isinstance(other, Period):             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()      def __repr__(self):         return "Period(%r)" % (self.as_tuple(),)      # Datetime metadata methods.      def get_start(self):         return self.start      def get_end(self):         return self.end      def get_tzid(self):         return self.tzid      def get_start_item(self):         return self.start, get_datetime_attributes(self.start)      def get_end_item(self):         return self.end, get_datetime_attributes(self.end)      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())  class FreeBusyPeriod(Period):      "A free/busy record abstraction."      def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, tzid=None):          """         Initialise a free/busy period with the given 'start' and 'end' limits,         with an optional 'tzid', plus any 'uid', 'transp', 'recurrenceid',         'summary' and 'organiser' details.         """          Period.__init__(self, start, end, tzid)         self.uid = uid         self.transp = transp         self.recurrenceid = recurrenceid         self.summary = summary         self.organiser = organiser      def as_tuple(self):         return format_datetime(self.get_start_point()), \                format_datetime(self.get_end_point()), \                self.uid, self.transp, self.recurrenceid, self.summary, self.organiser      def __cmp__(self, other):          """         Compare this object to 'other', employing the uid if the periods         involved are the same.         """          result = Period.__cmp__(self, other)         if result == 0 and isinstance(other, FreeBusyPeriod):             return cmp(self.uid, other.uid)         else:             return result      def get_key(self):         return self.uid, self.recurrenceid, self.get_start()      def __repr__(self):         return "FreeBusyPeriod(%r)" % (self.as_tuple(),)  class RecurringPeriod(Period):          "A period with iCalendar attribute and origin information from the 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_item(self):         return self.get_start(), self.start_attr      def get_end_item(self):         return self.get_end(), self.end_attr      def get_tzid(self):         return get_tzid(self.start_attr, self.end_attr) or self.tzid      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'."      insort_left(freebusy, 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 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.      last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid()))     startpoints = freebusy[:last]      # 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)  # 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):      """     Update the free/busy details with the given 'periods', 'transp' setting,     'uid' plus 'recurrenceid' and 'summary' and 'organiser' details.     """      remove_period(freebusy, uid, recurrenceid)      for p in periods:         insert_period(freebusy, FreeBusyPeriod(p.get_start(), p.get_end(), uid, transp, recurrenceid, summary, organiser, p.get_tzid()))  # vim: tabstop=4 expandtab shiftwidth=4