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 containing a point in time for the start of the slot, 155 together with a list of parallel event tuples, each tuple containing the 156 original details of an event. 157 """ 158 159 slots = [] 160 active = [] 161 162 points = scale.items() 163 points.sort() 164 165 for point, (starting, ending) in points: 166 167 # Discard all active events ending at or before this start time. 168 # Free up the position in the active list. 169 170 for t in ending: 171 i = active.index(t) 172 active[i] = None 173 174 # For each event starting at the current point, fill any newly-vacated 175 # position or add to the end of the active list. 176 177 for t in starting: 178 try: 179 i = active.index(None) 180 active[i] = t 181 except ValueError: 182 active.append(t) 183 184 # Discard vacant positions from the end of the active list. 185 186 while active and active[-1] is None: 187 active.pop() 188 189 slots.append((point, active[:])) 190 191 return slots 192 193 def add_day_start_points(slots): 194 195 """ 196 Introduce into the 'slots' any day start points required by multi-day 197 periods. 198 """ 199 200 new_slots = [] 201 current_date = None 202 previously_active = None 203 204 for point, active in slots: 205 start_of_day = get_start_of_day(point) 206 this_date = point.date() 207 208 # For each new day, create a partition of the original collection. 209 210 if this_date != current_date: 211 current_date = this_date 212 213 # Add any continuing periods. 214 215 if point != start_of_day and previously_active: 216 new_slots.append((start_of_day, previously_active)) 217 218 # Add the currently active periods at this point in time. 219 220 previously_active = active 221 222 for t in new_slots: 223 insort_left(slots, t) 224 225 def add_slots(slots, points): 226 227 """ 228 Introduce into the 'slots' entries for those in 'points' that are not 229 already present, propagating active periods from time points preceding 230 those added. 231 """ 232 233 new_slots = [] 234 235 for point in points: 236 i = bisect_left(slots, (point, None)) 237 if i < len(slots) and slots[i][0] == point: 238 continue 239 240 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 241 242 for t in new_slots: 243 insort_left(slots, t) 244 245 def partition_by_day(slots): 246 247 """ 248 Return a mapping from dates to time points provided by 'slots'. 249 """ 250 251 d = {} 252 253 for point, value in slots: 254 day = point.date() 255 if not d.has_key(day): 256 d[day] = [] 257 d[day].append((point, value)) 258 259 return d 260 261 def get_spans(slots): 262 263 "Inspect the given 'slots', returning a mapping of event uids to spans." 264 265 points = [point for point, active in slots] 266 spans = {} 267 268 for point, active in slots: 269 for t in active: 270 if t and len(t) >= 2: 271 start, end, uid, key = get_freebusy_details(t) 272 273 try: 274 start_slot = points.index(start) 275 except ValueError: 276 start_slot = 0 277 try: 278 end_slot = points.index(end) 279 except ValueError: 280 end_slot = len(slots) 281 spans[key] = end_slot - start_slot 282 283 return spans 284 285 def get_freebusy_details(t): 286 287 "Return a tuple of the form (start, end, uid, key) from 't'." 288 289 # Handle both complete free/busy details... 290 291 if len(t) > 2: 292 start, end, uid = t[:3] 293 key = uid 294 295 # ...and published details without specific event details. 296 297 else: 298 start, end = t[:2] 299 uid = None 300 key = (start, end) 301 302 return start, end, uid, key 303 304 # vim: tabstop=4 expandtab shiftwidth=4