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, insort_left 23 from datetime import datetime 24 from imiptools.dates import get_datetime, get_start_of_day, to_timezone 25 26 # Time management with datetime strings. 27 28 def can_schedule(freebusy, periods, uid): 29 30 """ 31 Return whether the 'freebusy' list can accommodate the given 'periods' 32 employing the specified 'uid'. 33 """ 34 35 for conflict in have_conflict(freebusy, periods, True): 36 start, end, found_uid, found_transp = conflict 37 if found_uid != uid: 38 return False 39 40 return True 41 42 def have_conflict(freebusy, periods, get_conflicts=False): 43 44 """ 45 Return whether any period in 'freebusy' overlaps with the given 'periods', 46 returning a collection of such overlapping periods if 'get_conflicts' is 47 set to a true value. 48 """ 49 50 conflicts = [] 51 for start, end in periods: 52 overlapping = period_overlaps(freebusy, (start, end), get_conflicts) 53 if overlapping: 54 if get_conflicts: 55 conflicts += overlapping 56 else: 57 return True 58 59 if get_conflicts: 60 return conflicts 61 else: 62 return False 63 64 def insert_period(freebusy, period): 65 insort_left(freebusy, period) 66 67 def remove_period(freebusy, uid): 68 i = 0 69 while i < len(freebusy): 70 t = freebusy[i] 71 if len(t) >= 3 and t[2] == uid: 72 del freebusy[i] 73 else: 74 i += 1 75 76 def period_overlaps(freebusy, period, get_periods=False): 77 78 """ 79 Return whether any period in 'freebusy' overlaps with the given 'period', 80 returning a collection of overlapping periods if 'get_periods' is set to a 81 true value. 82 """ 83 84 dtstart, dtend = period[:2] 85 found = bisect_left(freebusy, (dtstart, dtend, None, None)) 86 87 overlapping = [] 88 89 # Find earlier overlapping periods. 90 91 i = found 92 93 while i > 0 and freebusy[i - 1][1] > dtstart: 94 if get_periods: 95 overlapping.insert(0, freebusy[i - 1]) 96 else: 97 return True 98 i -= 1 99 100 # Find later overlapping periods. 101 102 i = found 103 104 while i < len(freebusy) and (dtend is None or freebusy[i][0] < dtend): 105 if get_periods: 106 overlapping.append(freebusy[i]) 107 else: 108 return True 109 i += 1 110 111 if get_periods: 112 return overlapping 113 else: 114 return False 115 116 # Period layout mostly with datetime objects. 117 118 def convert_periods(periods, tzid): 119 120 "Convert 'periods' to use datetime objects employing the given 'tzid'." 121 122 l = [] 123 124 for t in periods: 125 start, end = t[:2] 126 127 # NOTE: This only really works if the datetimes are UTC already. 128 # NOTE: Since the periods should originate from the free/busy data, 129 # NOTE: and since that data should employ UTC times, this should not be 130 # NOTE: an immediate problem. 131 132 start = get_datetime(start) 133 end = get_datetime(end) 134 135 start = isinstance(start, datetime) and to_timezone(start, tzid) or get_start_of_day(start, tzid) 136 end = isinstance(end, datetime) and to_timezone(end, tzid) or get_start_of_day(end, tzid) 137 138 l.append((start, end) + tuple(t[2:])) 139 140 return l 141 142 def get_scale(periods): 143 144 """ 145 Return an ordered time scale from the given list 'periods', with the first 146 two elements of each tuple being start and end times. 147 148 The given 'tzid' is used to make sure that the times are defined according 149 to the chosen time zone. 150 151 The returned scale is a mapping from time to (starting, ending) tuples, 152 where starting and ending are collections of tuples from 'periods'. 153 """ 154 155 scale = {} 156 157 for t in periods: 158 start, end = t[:2] 159 160 # Add a point and this event to the starting list. 161 162 if not scale.has_key(start): 163 scale[start] = [], [] 164 scale[start][0].append(t) 165 166 # Add a point and this event to the ending list. 167 168 if not scale.has_key(end): 169 scale[end] = [], [] 170 scale[end][1].append(t) 171 172 return scale 173 174 def get_slots(scale): 175 176 """ 177 Return an ordered list of time slots from the given 'scale'. 178 179 Each slot is a tuple containing a point in time for the start of the slot, 180 together with a list of parallel event tuples, each tuple containing the 181 original details of an event. 182 """ 183 184 slots = [] 185 active = [] 186 187 points = scale.items() 188 points.sort() 189 190 for point, (starting, ending) in points: 191 192 # Discard all active events ending at or before this start time. 193 # Free up the position in the active list. 194 195 for t in ending: 196 i = active.index(t) 197 active[i] = None 198 199 # For each event starting at the current point, fill any newly-vacated 200 # position or add to the end of the active list. 201 202 for t in starting: 203 try: 204 i = active.index(None) 205 active[i] = t 206 except ValueError: 207 active.append(t) 208 209 # Discard vacant positions from the end of the active list. 210 211 while active and active[-1] is None: 212 active.pop() 213 214 slots.append((point, active[:])) 215 216 return slots 217 218 def add_day_start_points(slots, tzid): 219 220 """ 221 Introduce into the 'slots' any day start points required by multi-day 222 periods. The 'tzid' is required to make sure that appropriate time zones 223 are chosen and not necessarily those provided by the existing time points. 224 """ 225 226 new_slots = [] 227 current_date = None 228 previously_active = [] 229 230 for point, active in slots: 231 start_of_day = get_start_of_day(point, tzid) 232 this_date = point.date() 233 234 # For each new day, add a slot for the start of the day where periods 235 # are active and where no such slot already exists. 236 237 if this_date != current_date: 238 current_date = this_date 239 240 # Add any continuing periods. 241 242 if point != start_of_day: 243 new_slots.append((start_of_day, previously_active)) 244 245 # Add the currently active periods at this point in time. 246 247 previously_active = active 248 249 for t in new_slots: 250 insort_left(slots, t) 251 252 def add_slots(slots, points): 253 254 """ 255 Introduce into the 'slots' entries for those in 'points' that are not 256 already present, propagating active periods from time points preceding 257 those added. 258 """ 259 260 new_slots = [] 261 262 for point in points: 263 i = bisect_left(slots, (point, None)) 264 if i < len(slots) and slots[i][0] == point: 265 continue 266 267 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 268 269 for t in new_slots: 270 insort_left(slots, t) 271 272 def partition_by_day(slots): 273 274 """ 275 Return a mapping from dates to time points provided by 'slots'. 276 """ 277 278 d = {} 279 280 for point, value in slots: 281 day = point.date() 282 if not d.has_key(day): 283 d[day] = [] 284 d[day].append((point, value)) 285 286 return d 287 288 def get_spans(slots): 289 290 "Inspect the given 'slots', returning a mapping of event uids to spans." 291 292 points = [point for point, active in slots] 293 spans = {} 294 295 for point, active in slots: 296 for t in active: 297 if t and len(t) >= 2: 298 start, end, uid, key = get_freebusy_details(t) 299 300 try: 301 start_slot = points.index(start) 302 except ValueError: 303 start_slot = 0 304 try: 305 end_slot = points.index(end) 306 except ValueError: 307 end_slot = len(slots) 308 spans[key] = end_slot - start_slot 309 310 return spans 311 312 def get_freebusy_details(t): 313 314 "Return a tuple of the form (start, end, uid, key) from 't'." 315 316 # Handle both complete free/busy details... 317 318 if len(t) > 2: 319 start, end, uid = t[:3] 320 key = uid 321 322 # ...and published details without specific event details. 323 324 else: 325 start, end = t[:2] 326 uid = None 327 key = (start, end) 328 329 return start, end, uid, key 330 331 # vim: tabstop=4 expandtab shiftwidth=4