paul@48 | 1 | #!/usr/bin/env python |
paul@48 | 2 | |
paul@146 | 3 | """ |
paul@146 | 4 | Managing and presenting periods of time. |
paul@146 | 5 | |
paul@146 | 6 | Copyright (C) 2014, 2015 Paul Boddie <paul@boddie.org.uk> |
paul@146 | 7 | |
paul@146 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@146 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@146 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@146 | 11 | version. |
paul@146 | 12 | |
paul@146 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@146 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@146 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@146 | 16 | details. |
paul@146 | 17 | |
paul@146 | 18 | You should have received a copy of the GNU General Public License along with |
paul@146 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@146 | 20 | """ |
paul@146 | 21 | |
paul@48 | 22 | from bisect import bisect_left, insort_left |
paul@48 | 23 | |
paul@48 | 24 | # Time management. |
paul@48 | 25 | |
paul@72 | 26 | def have_conflict(freebusy, periods, get_conflicts=False): |
paul@72 | 27 | |
paul@72 | 28 | """ |
paul@72 | 29 | Return whether any period in 'freebusy' overlaps with the given 'periods', |
paul@72 | 30 | returning a collection of such overlapping periods if 'get_conflicts' is |
paul@72 | 31 | set to a true value. |
paul@72 | 32 | """ |
paul@72 | 33 | |
paul@72 | 34 | conflicts = [] |
paul@72 | 35 | for start, end in periods: |
paul@74 | 36 | overlapping = period_overlaps(freebusy, (start, end), get_conflicts) |
paul@74 | 37 | if overlapping: |
paul@72 | 38 | if get_conflicts: |
paul@74 | 39 | conflicts += overlapping |
paul@72 | 40 | else: |
paul@72 | 41 | return True |
paul@74 | 42 | |
paul@72 | 43 | if get_conflicts: |
paul@72 | 44 | return conflicts |
paul@72 | 45 | else: |
paul@72 | 46 | return False |
paul@72 | 47 | |
paul@48 | 48 | def insert_period(freebusy, period): |
paul@48 | 49 | insort_left(freebusy, period) |
paul@48 | 50 | |
paul@48 | 51 | def remove_period(freebusy, uid): |
paul@48 | 52 | i = 0 |
paul@48 | 53 | while i < len(freebusy): |
paul@48 | 54 | t = freebusy[i] |
paul@48 | 55 | if len(t) >= 3 and t[2] == uid: |
paul@48 | 56 | del freebusy[i] |
paul@48 | 57 | else: |
paul@48 | 58 | i += 1 |
paul@48 | 59 | |
paul@74 | 60 | def period_overlaps(freebusy, period, get_periods=False): |
paul@72 | 61 | |
paul@72 | 62 | """ |
paul@74 | 63 | Return whether any period in 'freebusy' overlaps with the given 'period', |
paul@74 | 64 | returning a collection of overlapping periods if 'get_periods' is set to a |
paul@74 | 65 | true value. |
paul@72 | 66 | """ |
paul@72 | 67 | |
paul@48 | 68 | dtstart, dtend = period[:2] |
paul@112 | 69 | found = bisect_left(freebusy, (dtstart, dtend, None, None)) |
paul@74 | 70 | |
paul@74 | 71 | overlapping = [] |
paul@74 | 72 | |
paul@74 | 73 | # Find earlier overlapping periods. |
paul@74 | 74 | |
paul@74 | 75 | i = found |
paul@74 | 76 | |
paul@74 | 77 | while i > 0 and freebusy[i - 1][1] > dtstart: |
paul@74 | 78 | if get_periods: |
paul@74 | 79 | overlapping.insert(0, freebusy[i - 1]) |
paul@74 | 80 | else: |
paul@74 | 81 | return True |
paul@74 | 82 | i -= 1 |
paul@74 | 83 | |
paul@74 | 84 | # Find later overlapping periods. |
paul@74 | 85 | |
paul@74 | 86 | i = found |
paul@74 | 87 | |
paul@74 | 88 | while i < len(freebusy) and (dtend is None or freebusy[i][0] < dtend): |
paul@74 | 89 | if get_periods: |
paul@74 | 90 | overlapping.append(freebusy[i]) |
paul@74 | 91 | else: |
paul@74 | 92 | return True |
paul@74 | 93 | i += 1 |
paul@74 | 94 | |
paul@74 | 95 | if get_periods: |
paul@74 | 96 | return overlapping |
paul@74 | 97 | else: |
paul@74 | 98 | return False |
paul@48 | 99 | |
paul@113 | 100 | # Period layout. |
paul@113 | 101 | |
paul@113 | 102 | def get_scale(l): |
paul@113 | 103 | |
paul@113 | 104 | """ |
paul@113 | 105 | Return an ordered time scale from the given list 'l' of tuples, with the |
paul@113 | 106 | first two elements of each tuple being start and end times. |
paul@113 | 107 | """ |
paul@113 | 108 | |
paul@113 | 109 | scale = {} |
paul@113 | 110 | |
paul@113 | 111 | for t in l: |
paul@113 | 112 | start, end = t[:2] |
paul@113 | 113 | |
paul@113 | 114 | # Add a point and this event to the starting list. |
paul@113 | 115 | |
paul@113 | 116 | if not scale.has_key(start): |
paul@113 | 117 | scale[start] = [], [] |
paul@113 | 118 | scale[start][0].append(t) |
paul@113 | 119 | |
paul@113 | 120 | # Add a point and this event to the ending list. |
paul@113 | 121 | |
paul@113 | 122 | if not scale.has_key(end): |
paul@113 | 123 | scale[end] = [], [] |
paul@113 | 124 | scale[end][1].append(t) |
paul@113 | 125 | |
paul@113 | 126 | scale = scale.items() |
paul@113 | 127 | scale.sort() |
paul@113 | 128 | return scale |
paul@113 | 129 | |
paul@113 | 130 | def get_slots(l): |
paul@113 | 131 | |
paul@113 | 132 | """ |
paul@113 | 133 | Return an ordered list of time slots from the given list 'l' of tuples, with |
paul@113 | 134 | the first two elements of each tuple being start and end times. |
paul@113 | 135 | |
paul@113 | 136 | Each slot is a tuple containing a point in time for the start of the slot, |
paul@113 | 137 | together with a list of parallel event tuples, each tuple containing the |
paul@113 | 138 | original details of an event. |
paul@113 | 139 | """ |
paul@113 | 140 | |
paul@113 | 141 | slots = [] |
paul@113 | 142 | active = [] |
paul@113 | 143 | |
paul@113 | 144 | for point, (starting, ending) in get_scale(l): |
paul@113 | 145 | |
paul@113 | 146 | # Discard all active events ending at or before this start time. |
paul@113 | 147 | |
paul@113 | 148 | for t in ending: |
paul@113 | 149 | i = active.index(t) |
paul@113 | 150 | active[i] = None |
paul@113 | 151 | |
paul@113 | 152 | for t in starting: |
paul@113 | 153 | try: |
paul@113 | 154 | i = active.index(None) |
paul@113 | 155 | active[i] = t |
paul@113 | 156 | except ValueError: |
paul@113 | 157 | active.append(t) |
paul@113 | 158 | |
paul@113 | 159 | while active and active[-1] is None: |
paul@113 | 160 | active.pop() |
paul@113 | 161 | |
paul@113 | 162 | slots.append((point, active[:])) |
paul@113 | 163 | |
paul@113 | 164 | return slots |
paul@113 | 165 | |
paul@114 | 166 | def get_spans(slots): |
paul@114 | 167 | |
paul@114 | 168 | "Inspect the given 'slots', returning a mapping of event uids to spans." |
paul@114 | 169 | |
paul@114 | 170 | points = [point for point, active in slots] |
paul@114 | 171 | spans = {} |
paul@114 | 172 | |
paul@114 | 173 | for point, active in slots: |
paul@114 | 174 | for t in active: |
paul@114 | 175 | if t: |
paul@115 | 176 | start, end, uid = t[:3] |
paul@114 | 177 | start_slot = points.index(start) |
paul@114 | 178 | end_slot = points.index(end) |
paul@114 | 179 | spans[uid] = end_slot - start_slot |
paul@114 | 180 | |
paul@114 | 181 | return spans |
paul@114 | 182 | |
paul@48 | 183 | # vim: tabstop=4 expandtab shiftwidth=4 |