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 112 # NOTE: This only really works if the datetimes are UTC already. 113 114 start = to_timezone(get_datetime(start), tzid) 115 end = to_timezone(get_datetime(end), tzid) 116 l.append((start, end) + tuple(t[2:])) 117 118 return l 119 120 def get_scale(periods): 121 122 """ 123 Return an ordered time scale from the given list 'periods', with the first 124 two elements of each tuple being start and end times. 125 126 The given 'tzid' is used to make sure that the times are defined according 127 to the chosen time zone. 128 129 The returned scale is a mapping from time to (starting, ending) tuples, 130 where starting and ending are collections of tuples from 'periods'. 131 """ 132 133 scale = {} 134 135 for t in periods: 136 start, end = t[:2] 137 138 # Add a point and this event to the starting list. 139 140 if not scale.has_key(start): 141 scale[start] = [], [] 142 scale[start][0].append(t) 143 144 # Add a point and this event to the ending list. 145 146 if not scale.has_key(end): 147 scale[end] = [], [] 148 scale[end][1].append(t) 149 150 return scale 151 152 def get_slots(scale): 153 154 """ 155 Return an ordered list of time slots from the given 'scale'. 156 157 Each slot is a tuple containing a point in time for the start of the slot, 158 together with a list of parallel event tuples, each tuple containing the 159 original details of an event. 160 """ 161 162 slots = [] 163 active = [] 164 165 points = scale.items() 166 points.sort() 167 168 for point, (starting, ending) in points: 169 170 # Discard all active events ending at or before this start time. 171 # Free up the position in the active list. 172 173 for t in ending: 174 i = active.index(t) 175 active[i] = None 176 177 # For each event starting at the current point, fill any newly-vacated 178 # position or add to the end of the active list. 179 180 for t in starting: 181 try: 182 i = active.index(None) 183 active[i] = t 184 except ValueError: 185 active.append(t) 186 187 # Discard vacant positions from the end of the active list. 188 189 while active and active[-1] is None: 190 active.pop() 191 192 slots.append((point, active[:])) 193 194 return slots 195 196 def add_day_start_points(slots): 197 198 """ 199 Introduce into the 'slots' any day start points required by multi-day 200 periods. 201 """ 202 203 new_slots = [] 204 current_date = None 205 previously_active = [] 206 207 for point, active in slots: 208 start_of_day = get_start_of_day(point) 209 this_date = point.date() 210 211 # For each new day, add a slot for the start of the day where periods 212 # are active and where no such slot already exists. 213 214 if this_date != current_date: 215 current_date = this_date 216 217 # Add any continuing periods. 218 219 if point != start_of_day: 220 new_slots.append((start_of_day, previously_active)) 221 222 # Add the currently active periods at this point in time. 223 224 previously_active = active 225 226 for t in new_slots: 227 insort_left(slots, t) 228 229 def add_slots(slots, points): 230 231 """ 232 Introduce into the 'slots' entries for those in 'points' that are not 233 already present, propagating active periods from time points preceding 234 those added. 235 """ 236 237 new_slots = [] 238 239 for point in points: 240 i = bisect_left(slots, (point, None)) 241 if i < len(slots) and slots[i][0] == point: 242 continue 243 244 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 245 246 for t in new_slots: 247 insort_left(slots, t) 248 249 def partition_by_day(slots): 250 251 """ 252 Return a mapping from dates to time points provided by 'slots'. 253 """ 254 255 d = {} 256 257 for point, value in slots: 258 day = point.date() 259 if not d.has_key(day): 260 d[day] = [] 261 d[day].append((point, value)) 262 263 return d 264 265 def get_spans(slots): 266 267 "Inspect the given 'slots', returning a mapping of event uids to spans." 268 269 points = [point for point, active in slots] 270 spans = {} 271 272 for point, active in slots: 273 for t in active: 274 if t and len(t) >= 2: 275 start, end, uid, key = get_freebusy_details(t) 276 277 try: 278 start_slot = points.index(start) 279 except ValueError: 280 start_slot = 0 281 try: 282 end_slot = points.index(end) 283 except ValueError: 284 end_slot = len(slots) 285 spans[key] = end_slot - start_slot 286 287 return spans 288 289 def get_freebusy_details(t): 290 291 "Return a tuple of the form (start, end, uid, key) from 't'." 292 293 # Handle both complete free/busy details... 294 295 if len(t) > 2: 296 start, end, uid = t[:3] 297 key = uid 298 299 # ...and published details without specific event details. 300 301 else: 302 start, end = t[:2] 303 uid = None 304 key = (start, end) 305 306 return start, end, uid, key 307 308 # vim: tabstop=4 expandtab shiftwidth=4