1.1 --- a/imiptools/period.py Tue Mar 24 17:55:30 2015 +0100
1.2 +++ b/imiptools/period.py Tue Mar 24 17:56:12 2015 +0100
1.3 @@ -19,7 +19,7 @@
1.4 this program. If not, see <http://www.gnu.org/licenses/>.
1.5 """
1.6
1.7 -from bisect import bisect_left, insort_left
1.8 +from bisect import bisect_left, bisect_right, insort_left
1.9 from datetime import datetime, timedelta
1.10 from imiptools.dates import get_datetime, get_start_of_day, to_timezone
1.11
1.12 @@ -134,28 +134,36 @@
1.13 def get_overlapping(freebusy, period):
1.14
1.15 """
1.16 - Return the indexes in 'freebusy' providing periods overlapping with
1.17 + Return the entries in 'freebusy' providing periods overlapping with
1.18 'period'.
1.19 """
1.20
1.21 dtstart, dtend = period[:2]
1.22 - found = bisect_left(freebusy, (dtstart, dtend))
1.23
1.24 - # Find earlier overlapping periods.
1.25 + # Find the range of periods potentially overlapping the period in the
1.26 + # free/busy collection.
1.27
1.28 - start = found
1.29 + last = bisect_right(freebusy, (dtend,))
1.30 + startpoints = freebusy[:last]
1.31
1.32 - while start > 0 and freebusy[start - 1][1] > dtstart:
1.33 - start -= 1
1.34 + # Find the range of periods potentially overlapping the period in a version
1.35 + # of the free/busy collection sorted according to end datetimes.
1.36
1.37 - # Find later overlapping periods.
1.38 + endpoints = [((fb[1], fb[0]) + fb[2:]) for fb in startpoints]
1.39 + endpoints.sort()
1.40 + first = bisect_left(endpoints, (dtstart,))
1.41 + endpoints = endpoints[first:]
1.42
1.43 - end = found
1.44 + overlapping = set()
1.45
1.46 - while end < len(freebusy) and (dtend is None or freebusy[end][0] < dtend):
1.47 - end += 1
1.48 + for fb in endpoints:
1.49 + end, start = fb[:2]
1.50 + if end > dtstart and start < dtend:
1.51 + overlapping.add((start, end) + fb[2:])
1.52
1.53 - return start, end
1.54 + overlapping = list(overlapping)
1.55 + overlapping.sort()
1.56 + return overlapping
1.57
1.58 def period_overlaps(freebusy, period, get_periods=False):
1.59
1.60 @@ -165,12 +173,12 @@
1.61 true value.
1.62 """
1.63
1.64 - start, end = get_overlapping(freebusy, period)
1.65 + overlapping = get_overlapping(freebusy, period)
1.66
1.67 if get_periods:
1.68 - return freebusy[start:end]
1.69 + return overlapping
1.70 else:
1.71 - return start != end
1.72 + return len(overlapping) != 0
1.73
1.74 def remove_overlapping(freebusy, period):
1.75