# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1508880515 -7200
# Node ID b35e8d4f7742759113d25866ef3cc5eab62c7992
# Parent  177816f89852e652b56dc970134e9e4d78715f74# Parent  aa6e36ed60eb17cc212e6e22439399c75b454581
Merged changes from the default branch.

diff -r 177816f89852 -r b35e8d4f7742 imiptools/data.py
--- a/imiptools/data.py	Tue Oct 24 20:33:02 2017 +0200
+++ b/imiptools/data.py	Tue Oct 24 23:28:35 2017 +0200
@@ -19,7 +19,7 @@
 this program.  If not, see <http://www.gnu.org/licenses/>.
 """
 
-from bisect import bisect_left
+from bisect import bisect_left, insort_left
 from datetime import date, datetime, timedelta
 from email.mime.text import MIMEText
 from imiptools.dates import format_datetime, get_datetime, \
@@ -31,6 +31,7 @@
                             to_timezone, to_utc_datetime
 from imiptools.freebusy import FreeBusyPeriod
 from imiptools.period import Period, RecurringPeriod
+from itertools import ifilter
 from vCalendar import iterwrite, parse, ParseError, to_dict, to_node
 from vRecurrence import get_parameters, get_rule
 import email.utils
@@ -1294,6 +1295,66 @@
 
         return period == self.main_period and self.main_period or period
 
+class MergingIterator:
+
+    "An iterator merging ordered collections."
+
+    def __init__(self, iterators):
+
+        "Initialise an iterator merging 'iterators'."
+
+        self.current = []
+
+        # Populate an ordered collection of (value, iterator) pairs by obtaining
+        # the first value from each iterator.
+
+        for iterator in iterators:
+            t = self.get_next(iterator)
+            if t:
+                self.current.append(t)
+
+        self.current.sort()
+
+    def __iter__(self):
+        return self
+
+    def get_next(self, iterator):
+
+        """
+        Return a (value, iterator) pair for 'iterator' or None if the iterator
+        has been exhausted.
+        """
+
+        try:
+            return (iterator.next(), iterator)
+        except StopIteration:
+            return None
+
+    def next(self):
+
+        """
+        Return the next value in an ordered sequence, choosing it from one of
+        the available iterators.
+        """
+
+        if not self.current:
+            raise StopIteration
+
+        # Obtain the current value and remove the (value, iterator) pair,
+        # pending insertion of a new pair for the iterator.
+
+        current, iterator = self.current[0]
+        del self.current[0]
+
+        # Get the next value, if any and insert the value and iterator into the
+        # ordered collection.
+
+        t = self.get_next(iterator)
+        if t:
+            insort_left(self.current, t)
+
+        return current
+
 def get_periods(obj, start=None, end=None, inclusive=False):
 
     """
@@ -1317,7 +1378,7 @@
     main_period = obj.get_main_period()
 
     if not rrule:
-        periods = [main_period]
+        rule_periods = iter([main_period])
 
     # Recurrence rules create multiple instances to be checked.
     # Conflicts may only be assessed within a period defined by policy
@@ -1329,21 +1390,21 @@
         # Filter periods using a start point. The end will be handled in the
         # materialisation process.
 
-        periods = filter(Period(start, None).wraps,
-                         RulePeriodCollection(rrule, main_period, tzid, end,
-                                              inclusive))
+        rule_periods = ifilter(Period(start, None).wraps,
+                               RulePeriodCollection(rrule, main_period, tzid,
+                                                    end, inclusive))
     else:
-        periods = []
+        rule_periods = iter([])
 
     # Add recurrence dates.
 
     rdates = obj.get_date_value_item_periods("RDATE")
     if rdates:
-        periods += rdates
+        rdates.sort()
 
     # Return a sorted list of the periods.
 
-    periods.sort()
+    periods = list(MergingIterator([rule_periods, iter(rdates or [])]))
 
     # Exclude exception dates.