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