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