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. 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. 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): 219 220 """ 221 Introduce into the 'slots' any day start points required by multi-day 222 periods. 223 """ 224 225 new_slots = [] 226 current_date = None 227 previously_active = [] 228 229 for point, active in slots: 230 start_of_day = get_start_of_day(point) 231 this_date = point.date() 232 233 # For each new day, add a slot for the start of the day where periods 234 # are active and where no such slot already exists. 235 236 if this_date != current_date: 237 current_date = this_date 238 239 # Add any continuing periods. 240 241 if point != start_of_day: 242 new_slots.append((start_of_day, previously_active)) 243 244 # Add the currently active periods at this point in time. 245 246 previously_active = active 247 248 for t in new_slots: 249 insort_left(slots, t) 250 251 def add_slots(slots, points): 252 253 """ 254 Introduce into the 'slots' entries for those in 'points' that are not 255 already present, propagating active periods from time points preceding 256 those added. 257 """ 258 259 new_slots = [] 260 261 for point in points: 262 i = bisect_left(slots, (point, None)) 263 if i < len(slots) and slots[i][0] == point: 264 continue 265 266 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 267 268 for t in new_slots: 269 insort_left(slots, t) 270 271 def partition_by_day(slots): 272 273 """ 274 Return a mapping from dates to time points provided by 'slots'. 275 """ 276 277 d = {} 278 279 for point, value in slots: 280 day = point.date() 281 if not d.has_key(day): 282 d[day] = [] 283 d[day].append((point, value)) 284 285 return d 286 287 def get_spans(slots): 288 289 "Inspect the given 'slots', returning a mapping of event uids to spans." 290 291 points = [point for point, active in slots] 292 spans = {} 293 294 for point, active in slots: 295 for t in active: 296 if t and len(t) >= 2: 297 start, end, uid, key = get_freebusy_details(t) 298 299 try: 300 start_slot = points.index(start) 301 except ValueError: 302 start_slot = 0 303 try: 304 end_slot = points.index(end) 305 except ValueError: 306 end_slot = len(slots) 307 spans[key] = end_slot - start_slot 308 309 return spans 310 311 def get_freebusy_details(t): 312 313 "Return a tuple of the form (start, end, uid, key) from 't'." 314 315 # Handle both complete free/busy details... 316 317 if len(t) > 2: 318 start, end, uid = t[:3] 319 key = uid 320 321 # ...and published details without specific event details. 322 323 else: 324 start, end = t[:2] 325 uid = None 326 key = (start, end) 327 328 return start, end, uid, key 329 330 # vim: tabstop=4 expandtab shiftwidth=4