# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1508880114 -7200
# Node ID 3463dddb812d36cedca31dfcf237df160a8c8a5a
# Parent  b3ba19f3e74dee1118e73f73618549365baf7522
Introduced an iterator that merges recurrence rule and date collections.

diff -r b3ba19f3e74d -r 3463dddb812d imiptools/data.py
--- a/imiptools/data.py	Tue Oct 24 19:13:28 2017 +0200
+++ b/imiptools/data.py	Tue Oct 24 23:21:54 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
@@ -1164,6 +1165,66 @@
         recurrence_start = self.iterator.next()
         return make_rule_period(recurrence_start, self.duration, self.attr, self.tzid)
 
+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, tzid, start=None, end=None, inclusive=False):
 
     """
@@ -1191,7 +1252,7 @@
     obj_tzid = obj.get_tzid()
 
     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
@@ -1203,21 +1264,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, obj_tzid or
-                                              tzid, end, inclusive))
+        rule_periods = ifilter(Period(start, None).wraps,
+                               RulePeriodCollection(rrule, main_period, obj_tzid or
+                                                    tzid, end, inclusive))
     else:
-        periods = []
+        rule_periods = iter([])
 
     # Add recurrence dates.
 
     rdates = obj.get_date_value_item_periods("RDATE", obj_tzid or tzid)
     if rdates:
-        periods += rdates
+        rdates.sort()
 
     # Return a sorted list of the periods.
 
-    periods.sort()
+    periods = list(MergingIterator([rule_periods, iter(rdates)]))
 
     # Exclude exception dates.