# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1427216172 -3600
# Node ID cbf1c8cf9bdfb1ff7cc3ef350aeb17316810eb78
# Parent  63025c6fa6e82625d92ccb92ea5f949f0ce37163
Fixed overlapping period detection where periods fully enclose others.

diff -r 63025c6fa6e8 -r cbf1c8cf9bdf imiptools/period.py
--- a/imiptools/period.py	Tue Mar 24 17:55:30 2015 +0100
+++ b/imiptools/period.py	Tue Mar 24 17:56:12 2015 +0100
@@ -19,7 +19,7 @@
 this program.  If not, see <http://www.gnu.org/licenses/>.
 """
 
-from bisect import bisect_left, insort_left
+from bisect import bisect_left, bisect_right, insort_left
 from datetime import datetime, timedelta
 from imiptools.dates import get_datetime, get_start_of_day, to_timezone
 
@@ -134,28 +134,36 @@
 def get_overlapping(freebusy, period):
 
     """
-    Return the indexes in 'freebusy' providing periods overlapping with
+    Return the entries in 'freebusy' providing periods overlapping with
     'period'.
     """
 
     dtstart, dtend = period[:2]
-    found = bisect_left(freebusy, (dtstart, dtend))
 
-    # Find earlier overlapping periods.
+    # Find the range of periods potentially overlapping the period in the
+    # free/busy collection.
 
-    start = found
+    last = bisect_right(freebusy, (dtend,))
+    startpoints = freebusy[:last]
 
-    while start > 0 and freebusy[start - 1][1] > dtstart:
-        start -= 1
+    # Find the range of periods potentially overlapping the period in a version
+    # of the free/busy collection sorted according to end datetimes.
 
-    # Find later overlapping periods.
+    endpoints = [((fb[1], fb[0]) + fb[2:]) for fb in startpoints]
+    endpoints.sort()
+    first = bisect_left(endpoints, (dtstart,))
+    endpoints = endpoints[first:]
 
-    end = found
+    overlapping = set()
 
-    while end < len(freebusy) and (dtend is None or freebusy[end][0] < dtend):
-        end += 1
+    for fb in endpoints:
+        end, start = fb[:2]
+        if end > dtstart and start < dtend:
+            overlapping.add((start, end) + fb[2:])
 
-    return start, end
+    overlapping = list(overlapping)
+    overlapping.sort()
+    return overlapping
 
 def period_overlaps(freebusy, period, get_periods=False):
 
@@ -165,12 +173,12 @@
     true value.
     """
 
-    start, end = get_overlapping(freebusy, period)
+    overlapping = get_overlapping(freebusy, period)
 
     if get_periods:
-        return freebusy[start:end]
+        return overlapping
     else:
-        return start != end
+        return len(overlapping) != 0
 
 def remove_overlapping(freebusy, period):