#!/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, insort_left from imiptools.dates import get_datetime, get_start_of_day, to_timezone  # Time management.  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 = []     for start, end in periods:         overlapping = period_overlaps(freebusy, (start, end), get_conflicts)         if overlapping:             if get_conflicts:                 conflicts += overlapping             else:                 return True      if get_conflicts:         return conflicts     else:         return False  def insert_period(freebusy, period):     insort_left(freebusy, period)  def remove_period(freebusy, uid):     i = 0     while i < len(freebusy):         t = freebusy[i]         if len(t) >= 3 and t[2] == uid:             del freebusy[i]         else:             i += 1  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.     """      dtstart, dtend = period[:2]     found = bisect_left(freebusy, (dtstart, dtend, None, None))      overlapping = []      # Find earlier overlapping periods.      i = found      while i > 0 and freebusy[i - 1][1] > dtstart:         if get_periods:             overlapping.insert(0, freebusy[i - 1])         else:             return True         i -= 1      # Find later overlapping periods.      i = found      while i < len(freebusy) and (dtend is None or freebusy[i][0] < dtend):         if get_periods:             overlapping.append(freebusy[i])         else:             return True         i += 1      if get_periods:         return overlapping     else:         return False  # Period layout.  def convert_periods(periods, tzid):      "Convert 'periods' to use datetime objects employing the given 'tzid'."      l = []      for t in periods:         start, end = t[:2]         start = to_timezone(get_datetime(start), tzid)         end = to_timezone(get_datetime(end), tzid)         l.append((start, end) + tuple(t[2:]))      return l  def get_scale(periods):      """     Return an ordered time scale from the given list 'periods', with the first     two elements of each tuple being start and end times.      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 tuples from 'periods'.     """      scale = {}      for t in periods:         start, end = t[:2]          # Add a point and this event to the starting list.          if not scale.has_key(start):             scale[start] = [], []         scale[start][0].append(t)          # Add a point and this event to the ending list.          if not scale.has_key(end):             scale[end] = [], []         scale[end][1].append(t)      return scale  def get_slots(scale):      """     Return an ordered list of time slots from the given 'scale'.      Each slot is a tuple containing a point in time for the start of the slot,     together with a list of parallel event tuples, each tuple containing the     original details of an event.     """      slots = []     active = []      points = scale.items()     points.sort()      for point, (starting, ending) in points:          # Discard all active events ending at or before this start time.         # Free up the position in the active list.          for t in ending:             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()          slots.append((point, active[:]))      return slots  def add_day_start_points(slots):      """     Introduce into the 'slots' any day start points required by multi-day     periods.     """      new_slots = []     current_date = None     previously_active = None      for point, active in slots:         start_of_day = get_start_of_day(point)         this_date = point.date()          # For each new day, create a partition of the original collection.          if this_date != current_date:             current_date = this_date              # Add any continuing periods.              if point != start_of_day and previously_active:                 new_slots.append((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 and     succeeding those added.     """      new_slots = []      for point in points:         i = bisect_left(slots, (point, None))         if i < len(slots) and slots[i][0] == point:             continue          previously_active = i > 0 and slots[i-1] or []         subsequently_active = i < len(slots) and slots[i] or []          active = []          for p, s in zip(previously_active, subsequently_active):             if p == s:                 active.append(p)             else:                 active.append(None)          new_slots.append((point, active))      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.date()         if not d.has_key(day):             d[day] = []         d[day].append((point, value))      return d  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 t in active:             if t:                 start, end, uid = t[:3]                 try:                     start_slot = points.index(start)                 except ValueError:                     start_slot = 0                 try:                     end_slot = points.index(end)                 except ValueError:                     end_slot = len(slots)                 spans[uid] = end_slot - start_slot      return spans  # vim: tabstop=4 expandtab shiftwidth=4