#!/usr/bin/env python  """ Recurrence rule calculation.  Copyright (C) 2014, 2015, 2017 Paul Boddie <paul@boddie.org.uk>  This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.  This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.  You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>.  ----  References:  RFC 5545: Internet Calendaring and Scheduling Core Object Specification           (iCalendar)           http://tools.ietf.org/html/rfc5545  ----  FREQ defines the selection resolution. DTSTART defines the start of the selection. INTERVAL defines the step of the selection. COUNT defines a number of instances UNTIL defines a limit to the selection.  BY... qualifiers select instances within each outer selection instance according to the recurrence of instances of the next highest resolution. For example, BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated, all weeks are selected within the selection of the next highest explicitly specified resolution, whether this is months or years.  BYSETPOS in conjunction with BY... qualifiers permit the selection of specific instances.  Within the FREQ resolution, BY... qualifiers refine selected instances.  Outside the FREQ resolution, BY... qualifiers select instances at the resolution concerned.  Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing resolution (or decreasing scope). """  from calendar import monthrange from datetime import date, datetime, timedelta import operator  # Frequency levels, specified by FREQ in iCalendar.  freq_levels = (     "YEARLY",     "MONTHLY",     "WEEKLY",     None,       # yearday has no equivalent frequency     None,       # monthday has no equivalent frequency     "DAILY",     "HOURLY",     "MINUTELY",     "SECONDLY"     )  # Symbols corresponding to resolution levels.  YEARS, MONTHS, WEEKS, DAYS, HOURS, MINUTES, SECONDS = 0, 1, 2, 5, 6, 7, 8  # Enumeration levels, employed by BY... qualifiers.  enum_levels = (     None,     "BYMONTH",     "BYWEEKNO",     "BYYEARDAY",     "BYMONTHDAY",     "BYDAY",     "BYHOUR",     "BYMINUTE",     "BYSECOND"     )  # Levels defining days.  daylevels = [2, 3, 4, 5]  # Map from levels to lengths of datetime tuples.  lengths = [1, 2, 3, 3, 3, 3, 4, 5, 6] positions = [l-1 for l in lengths]  # Define the lowest values at each resolution (years, months, days... hours, # minutes, seconds).  firstvalues = [0, 1, 1, 1, 1, 1, 0, 0, 0]  # Map from qualifiers to interval multiples. Here, weeks are defined as 7 days.  multiples = {"WEEKLY" : 7}  # Make dictionaries mapping qualifiers to levels.  freq = {} for i, level in enumerate(freq_levels):     if level:         freq[level] = i  enum = {} for i, level in enumerate(enum_levels):     if level:         enum[level] = i  # Weekdays: name -> 1-based value  weekdays = {} for i, weekday in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"]):     weekdays[weekday] = i + 1  # Functions for structuring the recurrences.  def get_next(it):      "Return the next value from iterator 'it' or None if no more values exist."      try:         return it.next()     except StopIteration:         return None  def get_parameters(values):      "Return parameters from the given list of 'values'."      d = {}     for value in values:         try:             key, value = value.split("=", 1)             d[key] = value         except ValueError:             continue     return d  def get_qualifiers(values):      """     Process the list of 'values' of the form "key=value", returning a list of     qualifiers of the form (qualifier name, args).     """      qualifiers = []     frequency = None     interval = 1      for value in values:         try:             key, value = value.split("=", 1)         except ValueError:             continue          # Accept frequency indicators as qualifiers.          if key == "FREQ" and freq.has_key(value):             qualifier = frequency = (value, {})          # Accept interval indicators for frequency qualifier parameterisation.          elif key == "INTERVAL":             interval = int(value)             continue          # Accept result set selection, truncation and enumerators as qualifiers.          elif key in ("BYSETPOS", "COUNT") or enum.has_key(key):             qualifier = (key, {"values" : get_qualifier_values(key, value)})          # Ignore other items.          else:             continue          qualifiers.append(qualifier)      # Parameterise any frequency qualifier with the interval.      if frequency:         frequency[1]["interval"] = interval      return qualifiers  def get_qualifier_values(qualifier, value):      """     For the given 'qualifier', process the 'value' string, returning a list of     suitable values.     """      # For non-weekday selection, obtain a list of day numbers.      if qualifier != "BYDAY":         return map(int, value.split(","))      # For weekday selection, obtain the weekday number and instance number.      values = []      for part in value.split(","):         weekday = weekdays.get(part[-2:])         if not weekday:             continue         index = part[:-2]         if index:             index = int(index)         else:             index = None         values.append((weekday, index))      return values  def order_qualifiers(qualifiers):      "Return the 'qualifiers' in order of increasing resolution."      l = []     max_level = 0      # Special qualifiers.      setpos = None     count = None      for qualifier, args in qualifiers:          # Distinguish between enumerators, used to select particular periods,         # and frequencies, used to select repeating periods.          if enum.has_key(qualifier):             level = enum[qualifier]              # Certain enumerators produce their values in a special way.              if special_enum_levels.has_key(qualifier):                 args["interval"] = 1                 selector = special_enum_levels[qualifier]             else:                 selector = Enum          elif qualifier == "BYSETPOS":             setpos = args             continue          elif qualifier == "COUNT":             count = args             continue          else:             level = freq[qualifier]             selector = Pattern          l.append(selector(level, args, qualifier))         max_level = max(level, max_level)      # Add the result set selector at the maximum level of enumeration.      if setpos is not None:         l.append(PositionSelector(max_level, setpos, "BYSETPOS"))      # Add the result set truncator at the top level.      if count is not None:         l.append(LimitSelector(0, count, "COUNT"))      # Make BYSETPOS sort earlier than the enumeration it modifies.     # Other BY... qualifiers sort earlier than selectors at the same resolution     # even though such things as "FREQ=HOURLY;BYHOUR=10" do not make much sense.      l.sort(key=lambda x: (x.level, not x.qualifier.startswith("BY") and 2 or                                    x.qualifier != "BYSETPOS" and 1 or 0))     return l  def get_datetime_structure(datetime):      "Return the structure of 'datetime' for recurrence production."      l = []     offset = 0      for pos, value in enumerate(datetime):          # At the day number, adjust the frequency level offset to reference         # days (and then hours, minutes, seconds).          if pos == 2:             offset = 3          l.append(Enum(pos + offset, {"values" : [value]}, "DT"))      return l  def combine_datetime_with_qualifiers(datetime, qualifiers):      """     Combine 'datetime' with 'qualifiers' to produce a structure for recurrence     production.      Initial datetime values appearing at broader resolutions than any qualifiers     are ignored, since their details will be used when materialising the     results.      Qualifiers are accumulated in order to define a selection. Datetime values     occurring between qualifiers or at the same resolution as qualifiers are     ignored.      Any remaining datetime values are introduced as enumerators, provided that     they do not conflict with qualifiers. For example, specific day values     conflict with day selectors and weekly qualifiers.      The purpose of the remaining datetime values is to define a result within     a period selected by the most precise qualifier. For example, the selection     of a day and month in a year recurrence.     """      iter_dt = iter(get_datetime_structure(datetime))     iter_q = iter(order_qualifiers(qualifiers))      l = []      from_dt = get_next(iter_dt)     from_q = get_next(iter_q)     have_q = False      # Consume from both lists, merging entries.      while from_dt and from_q:         _level = from_dt.level         level = from_q.level          # Datetime value at wider resolution.          if _level < level:             from_dt = get_next(iter_dt)          # Qualifier at wider or same resolution as datetime value.          else:             if not have_q:                 add_initial_qualifier(from_q, level, l)                 have_q = True              # Add the qualifier to the combined list.              l.append(from_q)              # Datetime value at same resolution.              if _level == level:                 from_dt = get_next(iter_dt)              # Get the next qualifier.              from_q = get_next(iter_q)      # Complete the list by adding remaining datetime enumerators.      while from_dt:          # Ignore datetime values that conflict with day-level qualifiers.          if not l or from_dt.level != freq["DAILY"] or \            l[-1].level not in daylevels:              l.append(from_dt)          from_dt = get_next(iter_dt)      # Complete the list by adding remaining qualifiers.      while from_q:         if not have_q:             add_initial_qualifier(from_q, level, l)             have_q = True          # Add the qualifier to the combined list.          l.append(from_q)          # Get the next qualifier.          from_q = get_next(iter_q)      return l  def add_initial_qualifier(from_q, level, l):      """     Take the first qualifier 'from_q' at the given resolution 'level', using it     to create an initial qualifier, adding it to the combined list 'l' if     required.     """      if isinstance(from_q, Enum) and level > 0:         repeat = Pattern(level - 1, {"interval" : 1}, None)         l.append(repeat)  def get_multiple(qualifier):      "Return the time unit multiple for 'qualifier'."      return multiples.get(qualifier, 1)  # Datetime arithmetic.  def is_year_only(t):      "Return if 't' describes a year."      return len(t) == lengths[YEARS]  def is_month_only(t):      "Return if 't' describes a month within a year."      return len(t) == lengths[MONTHS]  def start_of_year(t):      "Return the start of the year referenced by 't'."      return (t[0], 1, 1)  def end_of_year(t):      "Return the end of the year referenced by 't'."      return (t[0], 12, 31)  def start_of_month(t):      "Return the start of the month referenced by 't'."      year, month = t[:2]     return (year, month, 1)  def end_of_month(t):      "Return the end of the month referenced by 't'."      year, month = t[:2]     return update(update((year, month, 1), (0, 1, 0)), (0, 0, -1))  def day_in_year(t, number):      "Return the day in the year referenced by 't' with the given 'number'."      return to_tuple(date(*start_of_year(t)) + timedelta(number - 1))  def get_year_length(t):      "Return the length of the year referenced by 't'."      first_day = date(*start_of_year(t))     last_day = date(*end_of_year(t))     return (last_day - first_day).days + 1  def get_weekday(t):      "Return the 1-based weekday for the month referenced by 't'."      year, month = t[:2]     return monthrange(year, month)[0] + 1  def get_ordered_weekdays(t):      """     Return the 1-based weekday sequence describing the first week of the month     referenced by 't'.     """      first = get_weekday(t)     return range(first, 8) + range(1, first)  def get_last_weekday_instance(weekday, first_day, last_day):      """     Return the last instance number for 'weekday' within the period from     'first_day' to 'last_day' inclusive.      Here, 'weekday' is 1-based (starting on Monday), the returned limit is     1-based.     """      weekday0 = get_first_day(first_day, weekday)     days = (date(*last_day) - weekday0).days     return days / 7 + 1  def precision(t, level, value=None):      """     Return 't' trimmed in resolution to the indicated resolution 'level',     setting 'value' at the given resolution if indicated.     """      pos = positions[level]      if value is None:         return t[:pos + 1]     else:         return t[:pos] + (value,)  def scale(interval, level):      """     Scale the given 'interval' value in resolution to the indicated resolution     'level', returning a tuple with leading zero elements and 'interval' at the     stated position.     """      pos = positions[level]     return (0,) * pos + (interval,)  def get_seconds(t):      "Convert the sub-day part of 't' into seconds."      t = t + (0,) * (6 - len(t))     return (t[3] * 60 + t[4]) * 60 + t[5]  def update(t, step):      "Update 't' by 'step' at the resolution of 'step'."      i = len(step)      # Years only.      if i == 1:         return (t[0] + step[0],) + tuple(t[1:])      # Years and months.      elif i == 2:         month = t[1] + step[1]         return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:])      # Dates and datetimes.      else:         updated_for_months = update(t, step[:2])          # Dates only.          if i == 3:             d = datetime(*updated_for_months)             s = timedelta(step[2])          # Datetimes.          else:             d = datetime(*updated_for_months)             s = timedelta(step[2], get_seconds(step))          return to_tuple(d + s)[:len(t)]  def to_tuple(d):      "Return date or datetime 'd' as a tuple."      if not isinstance(d, date):         return d     if isinstance(d, datetime):         n = 6     else:         n = 3     return d.timetuple()[:n]  def get_first_day(first_day, weekday):      """     Return the first occurrence at or after 'first_day' of 'weekday' as a date     instance.     """      first_day = date(*first_day)     first_weekday = first_day.isoweekday()     if first_weekday > weekday:         return first_day + timedelta(7 - first_weekday + weekday)     else:         return first_day + timedelta(weekday - first_weekday)  def get_last_day(last_day, weekday):      """     Return the last occurrence at or before 'last_day' of 'weekday' as a date     instance.     """      last_day = date(*last_day)     last_weekday = last_day.isoweekday()     if last_weekday < weekday:         return last_day - timedelta(last_weekday + 7 - weekday)     else:         return last_day - timedelta(last_weekday - weekday)  # Value expansion and sorting.  def sort_values(values, limit=None):      """     Sort the given 'values' using 'limit' to determine the positions of negative     values.     """      # Convert negative values to positive values according to the value limit.      if limit is not None:         l = map(lambda x, limit=limit: x < 0 and x + 1 + limit or x, values)     else:         l = values[:]      l.sort()     return l  def compare_weekday_selectors(x, y, weekdays):      """     Compare 'x' and 'y' values of the form (weekday number, instance number)     using 'weekdays' to define an ordering of the weekday numbers.     """      return cmp((x[1], weekdays.index(x[0])), (y[1], weekdays.index(y[0])))  def sort_weekdays(values, first_day, last_day):      """     Return a sorted copy of the given 'values', each having the form (weekday     number, instance number) using 'weekdays' to define the ordering of the     weekday numbers and 'limit' to determine the positions of negative instance     numbers.     """      weekdays = get_ordered_weekdays(first_day)      # Expand the values to incorporate specific weekday instances.      l = []      for weekday, index in values:          # Obtain the last instance number of the weekday in the period.          limit = get_last_weekday_instance(weekday, first_day, last_day)          # For specific instances, convert negative selections.          if index is not None:             l.append((weekday, index < 0 and index + 1 + limit or index))          # For None, introduce selections for all instances of the weekday.          else:             index = 1             while index <= limit:                 l.append((weekday, index))                 index += 1      # Sort the values so that the resulting dates are ordered.      fn = lambda x, y, weekdays=weekdays: compare_weekday_selectors(x, y, weekdays)     l.sort(cmp=fn)     return l  def convert_positions(setpos):      "Convert 'setpos' to 0-based indexes."      l = []     if setpos:         for pos in setpos:             index = pos < 0 and pos or pos - 1             l.append(index)     return l  # Classes for producing instances from recurrence structures.  class Selector:      "A generic selector."      def __init__(self, level, args, qualifier, selecting=None, first=False):          """         Initialise at the given 'level' a selector employing the given 'args'         defined in the interpretation of recurrence rule qualifiers, with the         'qualifier' being the name of the rule qualifier, and 'selecting' being         an optional selector used to find more specific instances from those         found by this selector.         """          self.level = level         self.args = args         self.qualifier = qualifier         self.selecting = selecting         self.first = first      def __repr__(self):         return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level,                                        self.args, self.qualifier, self.first)      def select(self, start, end, inclusive=False):          """         Return an iterator over instances starting at 'start' and continuing up         to but not including any at 'end' or later.          If 'inclusive' is specified, the selection of instances will include the         end of the search period if present in the results.         """          start = to_tuple(start)         end = to_tuple(end)         return self.materialise_items(start, start, end, inclusive)      def materialise(self, start, end, inclusive=False):          """         Starting at 'start', materialise instances up to but not including any         at 'end' or later. A list of instances is returned.          If 'inclusive' is specified, the selection of instances will include the         end of the search period if present in the results.         """          return list(self.select(start, end, inclusive))  class Pattern(Selector):      "A selector of time periods according to a repeating pattern."      def __init__(self, level, args, qualifier, selecting=None, first=False):         Selector.__init__(self, level, args, qualifier, selecting, first)          multiple = get_multiple(self.qualifier)         interval = self.args.get("interval", 1)          # Define the step between result periods.          self.step = scale(interval * multiple, level)          # Define the scale of a single period.          self.unit_step = scale(multiple, level)      def materialise_items(self, context, start, end, inclusive=False):          """         Bounded by the given 'context', return periods within 'start' to 'end'.          If 'inclusive' is specified, the selection of periods will include those         starting at the end of the search period, if present in the results.         """          # Employ the context as the current period if this is the first         # qualifier in the selection chain.          if self.first:             current = precision(context, self.level)          # Otherwise, obtain the first value at this resolution within the         # context period.          else:             current = precision(context, self.level, firstvalues[self.level])          return PatternIterator(self, current, start, end, inclusive,                                self.step, self.unit_step)  class WeekDayFilter(Selector):      "A selector of instances specified in terms of day numbers."      def __init__(self, level, args, qualifier, selecting=None, first=False):         Selector.__init__(self, level, args, qualifier, selecting, first)         self.step = scale(1, WEEKS)      def materialise_items(self, context, start, end, inclusive=False):          # Get weekdays in the year.          if is_year_only(context):             first_day = start_of_year(context)             last_day = end_of_year(context)          # Get weekdays in the month.          elif is_month_only(context):             first_day = start_of_month(context)             last_day = end_of_month(context)          # Get weekdays in the week.          else:             current = context             values = [value for (value, index) in self.args["values"]]             return WeekDayIterator(self, current, start, end, inclusive, self.step, values)          current = first_day         values = sort_weekdays(self.args["values"], first_day, last_day)         return WeekDayGeneralIterator(self, current, start, end, inclusive, self.step, values)  class Enum(Selector):      "A generic value selector."      def __init__(self, level, args, qualifier, selecting=None, first=False):         Selector.__init__(self, level, args, qualifier, selecting, first)         self.step = scale(1, level)      def materialise_items(self, context, start, end, inclusive=False):         values = sort_values(self.args["values"])         return EnumIterator(self, context, start, end, inclusive, self.step, values)  class MonthDayFilter(Enum):      "A selector of month days."      def materialise_items(self, context, start, end, inclusive=False):         last_day = end_of_month(context)[2]         values = sort_values(self.args["values"], last_day)         return EnumIterator(self, context, start, end, inclusive, self.step, values)  class YearDayFilter(Enum):      "A selector of days in years."      def materialise_items(self, context, start, end, inclusive=False):         first_day = start_of_year(context)         year_length = get_year_length(context)         values = sort_values(self.args["values"], year_length)         return YearDayFilterIterator(self, first_day, start, end, inclusive, self.step, values)  special_enum_levels = {     "BYDAY" : WeekDayFilter,     "BYMONTHDAY" : MonthDayFilter,     "BYYEARDAY" : YearDayFilter,     }  class LimitSelector(Selector):      "A result set limit selector."      def materialise_items(self, context, start, end, inclusive=False):         limit = self.args["values"][0]         return LimitIterator(self, context, start, end, inclusive, limit)  class PositionSelector(Selector):      "A result set position selector."      def __init__(self, level, args, qualifier, selecting=None, first=False):         Selector.__init__(self, level, args, qualifier, selecting, first)         self.step = scale(1, level)      def materialise_items(self, context, start, end, inclusive=False):         values = convert_positions(sort_values(self.args["values"]))         return PositionIterator(self, context, start, end, inclusive, self.step, values)  # Iterator classes.  class SelectorIterator:      "An iterator over selected data."      def __init__(self, selector, current, start, end, inclusive):          """         Define an iterator having the 'current' point in time, 'start' and 'end'         limits, and whether the selection is 'inclusive'.         """          self.selector = selector         self.current = current         self.start = start         self.end = end         self.inclusive = inclusive          # Iterator over selections within this selection.          self.iterator = None      def __iter__(self):         return self      def next_item(self, earliest, next):          """         Given the 'earliest' acceptable instance and the 'next' instance, return         a list of result items.          Where no selection within the current instance occurs, the current         instance will be returned as a result if the same or later than the         earliest acceptable instance.         """          # Obtain an item from a selector operating within this selection.          selecting = self.selector.selecting          if selecting:              # Obtain an iterator for any selector within the current period.              if not self.iterator:                 self.iterator = selecting.materialise_items(self.current,                                     earliest, next, self.inclusive)              # Attempt to obtain and return a value.              return self.iterator.next()          # Return items within this selection.          else:             return self.current      def filter_by_period(self, result):          "Return whether 'result' occurs within the selection period."          return (self.inclusive and result <= self.end or result < self.end) and \                self.start <= result      def at_limit(self):          "Obtain periods before the end (and also at the end if inclusive)."          return not self.inclusive and self.current == self.end or \                self.current > self.end  class PatternIterator(SelectorIterator):      "An iterator for a general selection pattern."      def __init__(self, selector, current, start, end, inclusive, step, unit_step):         SelectorIterator.__init__(self, selector, current, start, end, inclusive)         self.step = step         self.unit_step = unit_step      def next(self):          "Return the next value."          while not self.at_limit():              # Increment the current datetime by the step for the next period.              next = update(self.current, self.step)              # Determine the end point of the current period.              current_end = update(self.current, self.unit_step)              # Obtain any period or periods within the bounds defined by the             # current period and any contraining start and end points.              try:                 result = self.next_item(max(self.current, self.start),                                         min(current_end, self.end))                  # Obtain the next period if not selecting within this period.                  if not self.selector.selecting:                     self.current = next                  # Filter out periods.                  if self.filter_by_period(result):                     return result              # Move on to the next instance.              except StopIteration:                 self.current = next                 self.iterator = None          raise StopIteration  class WeekDayIterator(SelectorIterator):      "An iterator over weekday selections in week periods."      def __init__(self, selector, current, start, end, inclusive, step, values):         SelectorIterator.__init__(self, selector, current, start, end, inclusive)         self.step = step         self.values = values      def next(self):          "Return the next value."          while not self.at_limit():              # Increment the current datetime by the step for the next period.              next = update(self.current, self.step)              # Determine whether the day is one chosen.              if date(*self.current).isoweekday() in self.values:                 try:                     result = self.next_item(max(self.current, self.start),                                             min(next, self.end))                      # Obtain the next period if not selecting within this period.                      if not self.selector.selecting:                         self.current = next                      return result                  # Move on to the next instance.                  except StopIteration:                     self.current = next                     self.iterator = None              else:                 self.current = next                 self.iterator = None          raise StopIteration  class EnumIterator(SelectorIterator):      "An iterator over specific value selections."      def __init__(self, selector, current, start, end, inclusive, step, values):         SelectorIterator.__init__(self, selector, current, start, end, inclusive)         self.step = step          # Derive selected periods from a base and the indicated values.          self.base = current          # Iterate over the indicated period values.          self.values = iter(values)         self.value = None      def get_selected_period(self):          "Return the period indicated by the current value."          return precision(self.base, self.selector.level, self.value)      def next(self):          "Return the next value."          while True:              # Find each of the given selected values.              if not self.selector.selecting or self.value is None:                 self.value = self.values.next()              # Select a period for each value at the current resolution.              self.current = self.get_selected_period()             next = update(self.current, self.step)              # To support setpos, only current and next bound the search, not             # the period in addition.              try:                 return self.next_item(self.current, next)              # Move on to the next instance.              except StopIteration:                 self.value = None                 self.iterator = None          raise StopIteration  class WeekDayGeneralIterator(EnumIterator):      "An iterator over weekday selections in month and year periods."      def get_selected_period(self):          "Return the day indicated by the current day value."          value, index = self.value         offset = timedelta(7 * (index - 1))         weekday0 = get_first_day(self.base, value)         return precision(to_tuple(weekday0 + offset), DAYS)  class YearDayFilterIterator(EnumIterator):      "An iterator over day-in-year selections."      def get_selected_period(self):          "Return the day indicated by the current day value."          offset = timedelta(self.value - 1)         return precision(to_tuple(date(*self.base) + offset), DAYS)  class LimitIterator(SelectorIterator):      "A result set limiting iterator."      def __init__(self, selector, context, start, end, inclusive, limit):         SelectorIterator.__init__(self, selector, context, start, end, inclusive)         self.limit = limit         self.count = 0      def next(self):          "Return the next value."          if self.count < self.limit:             self.count += 1             result = self.next_item(self.start, self.end)             return result          raise StopIteration  class PositionIterator(SelectorIterator):      "An iterator over results, selecting positions."      def __init__(self, selector, context, start, end, inclusive, step, positions):         SelectorIterator.__init__(self, selector, context, start, end, inclusive)         self.step = step          # Positions to select.          self.positions = positions          # Queue to hold values matching the negative position values.          self.queue_length = positions and positions[0] < 0 and abs(positions[0]) or 0         self.queue = []          # Result position.          self.resultpos = 0      def next(self):          "Return the next value."          while True:             try:                 result = self.next_item(self.start, self.end)                  # Positive positions can have their values released immediately.                  selected = self.resultpos in self.positions                 self.resultpos += 1                  if selected:                     return result                  # Negative positions must be held until this iterator completes and                 # then be released.                  if self.queue_length:                     self.queue.append(result)                     if len(self.queue) > self.queue_length:                         del self.queue[0]              except StopIteration:                  # With a queue and positions, attempt to find the referenced                 # positions.                  if self.queue and self.positions:                     index = self.positions[0]                     del self.positions[0]                      # Only negative positions are used at this point.                      if index < 0:                         try:                             return self.queue[index]                         except IndexError:                             pass                      # With only positive positions remaining, signal the end of                     # the collection.                      else:                         raise                  # With no queue or positions remaining, signal the end of the                 # collection.                  else:                     raise  # Public functions.  def connect_selectors(selectors):      """     Make the 'selectors' reference each other in a hierarchy so that     materialising the principal selector causes the more specific ones to be     employed in the operation.     """      current = selectors[0]     current.first = first = True      for selector in selectors[1:]:         current.selecting = selector          # Allow selectors within the limit selector to act as if they are first         # in the chain and will operate using the supplied datetime context.          first = isinstance(current, LimitSelector)          current = selector         current.first = first      return selectors[0]  def get_selector(dt, qualifiers):      """     Combine the initial datetime 'dt' with the given 'qualifiers', returning an     object that can be used to select recurrences described by the 'qualifiers'.     """      dt = to_tuple(dt)     return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers))  def get_rule(dt, rule):      """     Using the given initial datetime 'dt', interpret the 'rule' (a semicolon-     separated collection of "key=value" strings), and return the resulting     selector object.     """      if not isinstance(rule, tuple):         rule = rule.split(";")     qualifiers = get_qualifiers(rule)     return get_selector(dt, qualifiers)  # vim: tabstop=4 expandtab shiftwidth=4