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 24 # Time management. 25 26 def have_conflict(freebusy, periods, get_conflicts=False): 27 28 """ 29 Return whether any period in 'freebusy' overlaps with the given 'periods', 30 returning a collection of such overlapping periods if 'get_conflicts' is 31 set to a true value. 32 """ 33 34 conflicts = [] 35 for start, end in periods: 36 overlapping = period_overlaps(freebusy, (start, end), get_conflicts) 37 if overlapping: 38 if get_conflicts: 39 conflicts += overlapping 40 else: 41 return True 42 43 if get_conflicts: 44 return conflicts 45 else: 46 return False 47 48 def insert_period(freebusy, period): 49 insort_left(freebusy, period) 50 51 def remove_period(freebusy, uid): 52 i = 0 53 while i < len(freebusy): 54 t = freebusy[i] 55 if len(t) >= 3 and t[2] == uid: 56 del freebusy[i] 57 else: 58 i += 1 59 60 def period_overlaps(freebusy, period, get_periods=False): 61 62 """ 63 Return whether any period in 'freebusy' overlaps with the given 'period', 64 returning a collection of overlapping periods if 'get_periods' is set to a 65 true value. 66 """ 67 68 dtstart, dtend = period[:2] 69 found = bisect_left(freebusy, (dtstart, dtend, None, None)) 70 71 overlapping = [] 72 73 # Find earlier overlapping periods. 74 75 i = found 76 77 while i > 0 and freebusy[i - 1][1] > dtstart: 78 if get_periods: 79 overlapping.insert(0, freebusy[i - 1]) 80 else: 81 return True 82 i -= 1 83 84 # Find later overlapping periods. 85 86 i = found 87 88 while i < len(freebusy) and (dtend is None or freebusy[i][0] < dtend): 89 if get_periods: 90 overlapping.append(freebusy[i]) 91 else: 92 return True 93 i += 1 94 95 if get_periods: 96 return overlapping 97 else: 98 return False 99 100 # Period layout. 101 102 def get_scale(l): 103 104 """ 105 Return an ordered time scale from the given list 'l' of tuples, with the 106 first two elements of each tuple being start and end times. 107 """ 108 109 scale = {} 110 111 for t in l: 112 start, end = t[:2] 113 114 # Add a point and this event to the starting list. 115 116 if not scale.has_key(start): 117 scale[start] = [], [] 118 scale[start][0].append(t) 119 120 # Add a point and this event to the ending list. 121 122 if not scale.has_key(end): 123 scale[end] = [], [] 124 scale[end][1].append(t) 125 126 scale = scale.items() 127 scale.sort() 128 return scale 129 130 def get_slots(l): 131 132 """ 133 Return an ordered list of time slots from the given list 'l' of tuples, with 134 the first two elements of each tuple being start and end times. 135 136 Each slot is a tuple containing a point in time for the start of the slot, 137 together with a list of parallel event tuples, each tuple containing the 138 original details of an event. 139 """ 140 141 slots = [] 142 active = [] 143 144 for point, (starting, ending) in get_scale(l): 145 146 # Discard all active events ending at or before this start time. 147 148 for t in ending: 149 i = active.index(t) 150 active[i] = None 151 152 for t in starting: 153 try: 154 i = active.index(None) 155 active[i] = t 156 except ValueError: 157 active.append(t) 158 159 while active and active[-1] is None: 160 active.pop() 161 162 slots.append((point, active[:])) 163 164 return slots 165 166 def get_spans(slots): 167 168 "Inspect the given 'slots', returning a mapping of event uids to spans." 169 170 points = [point for point, active in slots] 171 spans = {} 172 173 for point, active in slots: 174 for t in active: 175 if t: 176 start, end, uid = t[:3] 177 start_slot = points.index(start) 178 end_slot = points.index(end) 179 spans[uid] = end_slot - start_slot 180 181 return spans 182 183 # vim: tabstop=4 expandtab shiftwidth=4