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 152 for t in ending: 153 i = active.index(t) 154 active[i] = None 155 156 for t in starting: 157 try: 158 i = active.index(None) 159 active[i] = t 160 except ValueError: 161 active.append(t) 162 163 while active and active[-1] is None: 164 active.pop() 165 166 slots.append((point, active[:])) 167 168 return slots 169 170 def partition_slots(slots, tzid): 171 172 """ 173 Partition the given 'slots' into separate collections having a date-level 174 resolution, using the given 'tzid' to make sure that the day boundaries are 175 defined according to the chosen time zone. 176 177 Return a collection of (date, slots) tuples. 178 """ 179 180 partitioned = {} 181 current = None 182 current_date = None 183 previously_active = None 184 185 for point, active in slots: 186 dt = to_timezone(get_datetime(point), tzid) 187 start_of_day = get_start_of_day(dt) 188 this_date = dt.date() 189 190 # For each new day, create a partition of the original collection. 191 192 if this_date != current_date: 193 current_date = this_date 194 partitioned[current_date] = current = [] 195 196 # Add any continuing periods. 197 198 if dt != start_of_day and previously_active: 199 current.append((start_of_day, previously_active)) 200 201 # Add the currently active periods at this point in time. 202 203 current.append((point, active)) 204 previously_active = active 205 206 partitioned = partitioned.items() 207 partitioned.sort() 208 return partitioned 209 210 def get_spans(slots): 211 212 "Inspect the given 'slots', returning a mapping of event uids to spans." 213 214 points = [point for point, active in slots] 215 spans = {} 216 217 for point, active in slots: 218 for t in active: 219 if t: 220 start, end, uid = t[:3] 221 try: 222 start_slot = points.index(start) 223 except ValueError: 224 start_slot = 0 225 try: 226 end_slot = points.index(end) 227 except ValueError: 228 end_slot = len(slots) 229 spans[uid] = end_slot - start_slot 230 231 return spans 232 233 # vim: tabstop=4 expandtab shiftwidth=4