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