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 get_scale(l): 104 105 """ 106 Return an ordered time scale from the given list 'l' of tuples, with the 107 first two elements of each tuple being start and end times. 108 109 The returned scale is a collection of (time, (starting, ending)) tuples, 110 where starting and ending are collections of tuples from 'l'. 111 """ 112 113 scale = {} 114 115 for t in l: 116 start, end = t[:2] 117 118 # Add a point and this event to the starting list. 119 120 if not scale.has_key(start): 121 scale[start] = [], [] 122 scale[start][0].append(t) 123 124 # Add a point and this event to the ending list. 125 126 if not scale.has_key(end): 127 scale[end] = [], [] 128 scale[end][1].append(t) 129 130 scale = scale.items() 131 scale.sort() 132 return scale 133 134 def get_slots(l): 135 136 """ 137 Return an ordered list of time slots from the given list 'l' of tuples, with 138 the first two elements of each tuple being start and end times. 139 140 Each slot is a tuple containing a point in time for the start of the slot, 141 together with a list of parallel event tuples, each tuple containing the 142 original details of an event. 143 """ 144 145 slots = [] 146 active = [] 147 148 for point, (starting, ending) in get_scale(l): 149 150 # Discard all active events ending at or before this start time. 151 # Free up the position in the active list. 152 153 for t in ending: 154 i = active.index(t) 155 active[i] = None 156 157 # For each event starting at the current point, fill any newly-vacated 158 # position or add to the end of the active list. 159 160 for t in starting: 161 try: 162 i = active.index(None) 163 active[i] = t 164 except ValueError: 165 active.append(t) 166 167 # Discard vacant positions from the end of the active list. 168 169 while active and active[-1] is None: 170 active.pop() 171 172 slots.append((point, active[:])) 173 174 return slots 175 176 def partition_slots(slots, tzid): 177 178 """ 179 Partition the given 'slots' into separate collections having a date-level 180 resolution, using the given 'tzid' to make sure that the day boundaries are 181 defined according to the chosen time zone. 182 183 Return a collection of (date, slots) tuples. 184 """ 185 186 partitioned = {} 187 current = None 188 current_date = None 189 previously_active = None 190 191 for point, active in slots: 192 dt = to_timezone(get_datetime(point), tzid) 193 start_of_day = get_start_of_day(dt) 194 this_date = dt.date() 195 196 # For each new day, create a partition of the original collection. 197 198 if this_date != current_date: 199 current_date = this_date 200 partitioned[current_date] = current = [] 201 202 # Add any continuing periods. 203 204 if dt != start_of_day and previously_active: 205 current.append((start_of_day, previously_active)) 206 207 # Add the currently active periods at this point in time. 208 209 current.append((point, active)) 210 previously_active = active 211 212 partitioned = partitioned.items() 213 partitioned.sort() 214 return partitioned 215 216 def get_spans(slots): 217 218 "Inspect the given 'slots', returning a mapping of event uids to spans." 219 220 points = [point for point, active in slots] 221 spans = {} 222 223 for point, active in slots: 224 for t in active: 225 if t: 226 start, end, uid = t[:3] 227 try: 228 start_slot = points.index(start) 229 except ValueError: 230 start_slot = 0 231 try: 232 end_slot = points.index(end) 233 except ValueError: 234 end_slot = len(slots) 235 spans[uid] = end_slot - start_slot 236 237 return spans 238 239 # vim: tabstop=4 expandtab shiftwidth=4