#!/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 datetime, timedelta from imiptools.dates import get_datetime, get_start_of_day, to_timezone  class Period:      "A basic period abstraction."      def __init__(self, start, end=None):         self.start = start         self.end = end      def as_tuple(self):         return self.start, self.end      def __hash__(self):         return hash((self.start, self.end))      def __cmp__(self, other):         if isinstance(other, Period):             return cmp((self.start, self.end), (other.start, other.end))         else:             return 1      def get_key(self):         return self.start, self.end      def __repr__(self):         return "Period(%r, %r)" % (self.start, self.end)  class FreeBusyPeriod(Period):      "A free/busy record abstraction."      def __init__(self, start, end=None, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None):         Period.__init__(self, start, end)         self.uid = uid         self.transp = transp         self.recurrenceid = recurrenceid         self.summary = summary         self.organiser = organiser      def as_tuple(self):         return self.start, self.end, self.uid, self.transp, self.recurrenceid, self.summary, self.organiser      def __cmp__(self, other):         if isinstance(other, FreeBusyPeriod):             return cmp((self.start, self.end, self.uid), (other.start, other.end, other.uid))         else:             return Period.__cmp__(self, other)      def get_key(self):         return self.uid, self.recurrenceid, self.start      def __repr__(self):         return "FreeBusyPeriod(%r, %r, %r, %r, %r, %r, %r)" % (             self.start, self.end, self.uid, self.transp, self.recurrenceid,             self.summary, self.organiser)  # Time management with datetime strings in the UTC time zone.  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).     """      i = 0     while i < len(freebusy):         fb = freebusy[i]         if fb.uid == uid and fb.recurrenceid == recurrenceid:             del freebusy[i]         else:             i += 1  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, recurrenceid):      """     Remove from 'freebusy' a period associated with 'uid' that provides an     occurrence starting at the given 'recurrenceid', where the recurrence     identifier is used to provide an alternative time period whilst also acting     as a reference to the originally-defined occurrence.     """      found = bisect_left(freebusy, Period(recurrenceid))     while found < len(freebusy):         fb = freebusy[found]          # Stop looking if the start no longer matches the recurrence identifier.          if fb.start != recurrenceid:             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.end))     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.end, fb.start, fb) for fb in startpoints]     endpoints.sort()     first = bisect_left(endpoints, (period.start,))     endpoints = endpoints[first:]      overlapping = set()      for end, start, fb in endpoints:         if end > period.start and start < period.end:             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 mostly with datetime objects.  def convert_periods(periods, tzid):      "Convert 'periods' to use datetime objects employing the given 'tzid'."      for p in periods:          # NOTE: This only really works if the datetimes are UTC already.         # NOTE: Since the periods should originate from the free/busy data,         # NOTE: and since that data should employ UTC times, this should not be         # NOTE: an immediate problem.          start = get_datetime(p.start)         end = get_datetime(p.end)          start = isinstance(start, datetime) and to_timezone(start, tzid) or get_start_of_day(start, tzid)         end = isinstance(end, datetime) and to_timezone(end, tzid) or get_start_of_day(end, tzid)          p.start = start         p.end = end  def get_scale(periods):      """     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.          if not scale.has_key(p.start):             scale[p.start] = [], []         scale[p.start][0].append(p)          # Add a point and this event to the ending list.          if not scale.has_key(p.end):             scale[p.end] = [], []         scale[p.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 event uids 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.start)                 end_slot = bisect_left(points, p.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.start, p.end, uid, transp, recurrenceid, summary, organiser))  # vim: tabstop=4 expandtab shiftwidth=4