text: # -*- coding: utf-8 -*-
  """
  The rrule module offers a small, complete, and very fast, implementation of
  the recurrence rules documented in the
  `iCalendar RFC <http://www.ietf.org/rfc/rfc2445.txt>`_,
  including support for caching of results.
  """
  import itertools
  import datetime
  import calendar
  import sys
  
  from fractions import gcd
  
  from six import advance_iterator, integer_types
  from six.moves import _thread
  
  __all__ = ["rrule", "rruleset", "rrulestr",
             "YEARLY", "MONTHLY", "WEEKLY", "DAILY",
             "HOURLY", "MINUTELY", "SECONDLY",
             "MO", "TU", "WE", "TH", "FR", "SA", "SU"]
  
  # Every mask is 7 days longer to handle cross-year weekly periods.
  M366MASK = tuple([1]*31+[2]*29+[3]*31+[4]*30+[5]*31+[6]*30 +
                   [7]*31+[8]*31+[9]*30+[10]*31+[11]*30+[12]*31+[1]*7)
  M365MASK = list(M366MASK)
  M29, M30, M31 = list(range(1, 30)), list(range(1, 31)), list(range(1, 32))
  MDAY366MASK = tuple(M31+M29+M31+M30+M31+M30+M31+M31+M30+M31+M30+M31+M31[:7])
  MDAY365MASK = list(MDAY366MASK)
  M29, M30, M31 = list(range(-29, 0)), list(range(-30, 0)), list(range(-31, 0))
  NMDAY366MASK = tuple(M31+M29+M31+M30+M31+M30+M31+M31+M30+M31+M30+M31+M31[:7])
  NMDAY365MASK = list(NMDAY366MASK)
  M366RANGE = (0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366)
  M365RANGE = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)
  WDAYMASK = [0, 1, 2, 3, 4, 5, 6]*55
  del M29, M30, M31, M365MASK[59], MDAY365MASK[59], NMDAY365MASK[31]
  MDAY365MASK = tuple(MDAY365MASK)
  M365MASK = tuple(M365MASK)
  
  (YEARLY,
   MONTHLY,
   WEEKLY,
   DAILY,
   HOURLY,
   MINUTELY,
   SECONDLY) = list(range(7))
  
  # Imported on demand.
  easter = None
  parser = None
  
  
  class weekday(object):
      __slots__ = ["weekday", "n"]
  
      def __init__(self, weekday, n=None):
          if n == 0:
              raise ValueError("Can't create weekday with n == 0")
          self.weekday = weekday
          self.n = n
  
      def __call__(self, n):
          if n == self.n:
              return self
          else:
              return self.__class__(self.weekday, n)
  
      def __eq__(self, other):
          try:
              if self.weekday != other.weekday or self.n != other.n:
                  return False
          except AttributeError:
              return False
          return True
  
      def __repr__(self):
          s = ("MO", "TU", "WE", "TH", "FR", "SA", "SU")[self.weekday]
          if not self.n:
              return s
          else:
              return "%s(%+d)" % (s, self.n)
  
  MO, TU, WE, TH, FR, SA, SU = weekdays = tuple([weekday(x) for x in range(7)])
  
  
  class rrulebase(object):
      def __init__(self, cache=False):
          if cache:
              self._cache = []
              self._cache_lock = _thread.allocate_lock()
              self._cache_gen = self._iter()
              self._cache_complete = False
          else:
              self._cache = None
              self._cache_complete = False
          self._len = None
  
      def __iter__(self):
          if self._cache_complete:
              return iter(self._cache)
          elif self._cache is None:
              return self._iter()
          else:
              return self._iter_cached()
  
      def _iter_cached(self):
          i = 0
          gen = self._cache_gen
          cache = self._cache
          acquire = self._cache_lock.acquire
          release = self._cache_lock.release
          while gen:
              if i == len(cache):
                  acquire()
                  if self._cache_complete:
                      break
                  try:
                      for j in range(10):
                          cache.append(advance_iterator(gen))
                  except StopIteration:
                      self._cache_gen = gen = None
                      self._cache_complete = True
                      break
                  release()
              yield cache[i]
              i += 1
          while i < self._len:
              yield cache[i]
              i += 1
  
      def __getitem__(self, item):
          if self._cache_complete:
              return self._cache[item]
          elif isinstance(item, slice):
              if item.step and item.step < 0:
                  return list(iter(self))[item]
              else:
                  return list(itertools.islice(self,
                                               item.start or 0,
                                               item.stop or sys.maxsize,
                                               item.step or 1))
          elif item >= 0:
              gen = iter(self)
              try:
                  for i in range(item+1):
                      res = advance_iterator(gen)
              except StopIteration:
                  raise IndexError
              return res
          else:
              return list(iter(self))[item]
  
      def __contains__(self, item):
          if self._cache_complete:
              return item in self._cache
          else:
              for i in self:
                  if i == item:
                      return True
                  elif i > item:
                      return False
          return False
  
      # __len__() introduces a large performance penality.
      def count(self):
          """ Returns the number of recurrences in this set. It will have go
              trough the whole recurrence, if this hasn't been done before. """
          if self._len is None:
              for x in self:
                  pass
          return self._len
  
      def before(self, dt, inc=False):
          """ Returns the last recurrence before the given datetime instance. The
              inc keyword defines what happens if dt is an occurrence. With
              inc=True, if dt itself is an occurrence, it will be returned. """
          if self._cache_complete:
              gen = self._cache
          else:
              gen = self
          last = None
          if inc:
              for i in gen:
                  if i > dt:
                      break
                  last = i
          else:
              for i in gen:
                  if i >= dt:
                      break
                  last = i
          return last
  
      def after(self, dt, inc=False):
          """ Returns the first recurrence after the given datetime instance. The
              inc keyword defines what happens if dt is an occurrence. With
              inc=True, if dt itself is an occurrence, it will be returned.  """
          if self._cache_complete:
              gen = self._cache
          else:
              gen = self
          if inc:
              for i in gen:
                  if i >= dt:
                      return i
          else:
              for i in gen:
                  if i > dt:
                      return i
          return None
  
      def between(self, after, before, inc=False):
          """ Returns all the occurrences of the rrule between after and before.
          The inc keyword defines what happens if after and/or before are
          themselves occurrences. With inc=True, they will be included in the
          list, if they are found in the recurrence set. """
          if self._cache_complete:
              gen = self._cache
          else:
              gen = self
          started = False
          l = []
          if inc:
              for i in gen:
                  if i > before:
                      break
                  elif not started:
                      if i >= after:
                          started = True
                          l.append(i)
                  else:
                      l.append(i)
          else:
              for i in gen:
                  if i >= before:
                      break
                  elif not started:
                      if i > after:
                          started = True
                          l.append(i)
                  else:
                      l.append(i)
          return l
  
  
  class rrule(rrulebase):
      """
      That's the base of the rrule operation. It accepts all the keywords
      defined in the RFC as its constructor parameters (except byday,
      which was renamed to byweekday) and more. The constructor prototype is::
  
              rrule(freq)
  
      Where freq must be one of YEARLY, MONTHLY, WEEKLY, DAILY, HOURLY, MINUTELY,
      or SECONDLY.
  
      Additionally, it supports the following keyword arguments:
  
      :param cache:
          If given, it must be a boolean value specifying to enable or disable
          caching of results. If you will use the same rrule instance multiple
          times, enabling caching will improve the performance considerably.
      :param dtstart:
          The recurrence start. Besides being the base for the recurrence,
          missing parameters in the final recurrence instances will also be
          extracted from this date. If not given, datetime.now() will be used
          instead.
      :param interval:
          The interval between each freq iteration. For example, when using
          YEARLY, an interval of 2 means once every two years, but with HOURLY,
          it means once every two hours. The default interval is 1.
      :param wkst:
          The week start day. Must be one of the MO, TU, WE constants, or an
          integer, specifying the first day of the week. This will affect
          recurrences based on weekly periods. The default week start is got
          from calendar.firstweekday(), and may be modified by
          calendar.setfirstweekday().
      :param count:
          How many occurrences will be generated.
      :param until:
          If given, this must be a datetime instance, that will specify the
          limit of the recurrence. If a recurrence instance happens to be the
          same as the datetime instance given in the until keyword, this will
          be the last occurrence.
      :param bysetpos:
          If given, it must be either an integer, or a sequence of integers,
          positive or negative. Each given integer will specify an occurrence
          number, corresponding to the nth occurrence of the rule inside the
          frequency period. For example, a bysetpos of -1 if combined with a
          MONTHLY frequency, and a byweekday of (MO, TU, WE, TH, FR), will
          result in the last work day of every month.
      :param bymonth:
          If given, it must be either an integer, or a sequence of integers,
          meaning the months to apply the recurrence to.
      :param bymonthday:
          If given, it must be either an integer, or a sequence of integers,
          meaning the month days to apply the recurrence to.
      :param byyearday:
          If given, it must be either an integer, or a sequence of integers,
          meaning the year days to apply the recurrence to.
      :param byweekno:
          If given, it must be either an integer, or a sequence of integers,
          meaning the week numbers to apply the recurrence to. Week numbers
          have the meaning described in ISO8601, that is, the first week of
          the year is that containing at least four days of the new year.
      :param byweekday:
          If given, it must be either an integer (0 == MO), a sequence of
          integers, one of the weekday constants (MO, TU, etc), or a sequence
          of these constants. When given, these variables will define the
          weekdays where the recurrence will be applied. It's also possible to
          use an argument n for the weekday instances, which will mean the nth
          occurrence of this weekday in the period. For example, with MONTHLY,
          or with YEARLY and BYMONTH, using FR(+1) in byweekday will specify the
          first friday of the month where the recurrence happens. Notice that in
          the RFC documentation, this is specified as BYDAY, but was renamed to
          avoid the ambiguity of that keyword.
      :param byhour:
          If given, it must be either an integer, or a sequence of integers,
          meaning the hours to apply the recurrence to.
      :param byminute:
          If given, it must be either an integer, or a sequence of integers,
          meaning the minutes to apply the recurrence to.
      :param bysecond:
          If given, it must be either an integer, or a sequence of integers,
          meaning the seconds to apply the recurrence to.
      :param byeaster:
          If given, it must be either an integer, or a sequence of integers,
          positive or negative. Each integer will define an offset from the
          Easter Sunday. Passing the offset 0 to byeaster will yield the Easter
          Sunday itself. This is an extension to the RFC specification.
       """
      def __init__(self, freq, dtstart=None,
                   interval=1, wkst=None, count=None, until=None, bysetpos=None,
                   bymonth=None, bymonthday=None, byyearday=None, byeaster=None,
                   byweekno=None, byweekday=None,
                   byhour=None, byminute=None, bysecond=None,
                   cache=False):
          super(rrule, self).__init__(cache)
          global easter
          if not dtstart:
              dtstart = datetime.datetime.now().replace(microsecond=0)
          elif not isinstance(dtstart, datetime.datetime):
              dtstart = datetime.datetime.fromordinal(dtstart.toordinal())
          else:
              dtstart = dtstart.replace(microsecond=0)
          self._dtstart = dtstart
          self._tzinfo = dtstart.tzinfo
          self._freq = freq
          self._interval = interval
          self._count = count
  
          if until and not isinstance(until, datetime.datetime):
              until = datetime.datetime.fromordinal(until.toordinal())
          self._until = until
  
          if wkst is None:
              self._wkst = calendar.firstweekday()
          elif isinstance(wkst, integer_types):
              self._wkst = wkst
          else:
              self._wkst = wkst.weekday
  
          if bysetpos is None:
              self._bysetpos = None
          elif isinstance(bysetpos, integer_types):
              if bysetpos == 0 or not (-366 <= bysetpos <= 366):
                  raise ValueError("bysetpos must be between 1 and 366, "
                                   "or between -366 and -1")
              self._bysetpos = (bysetpos,)
          else:
              self._bysetpos = tuple(bysetpos)
              for pos in self._bysetpos:
                  if pos == 0 or not (-366 <= pos <= 366):
                      raise ValueError("bysetpos must be between 1 and 366, "
                                       "or between -366 and -1")
  
          if (byweekno is None and byyearday is None and bymonthday is None and
                  byweekday is None and byeaster is None):
              if freq == YEARLY:
                  if bymonth is None:
                      bymonth = dtstart.month
                  bymonthday = dtstart.day
              elif freq == MONTHLY:
                  bymonthday = dtstart.day
              elif freq == WEEKLY:
                  byweekday = dtstart.weekday()
  
          # bymonth
          if bymonth is None:
              self._bymonth = None
          else:
              if isinstance(bymonth, integer_types):
                  bymonth = (bymonth,)
  
              self._bymonth = set(bymonth)
  
          # byyearday
          if byyearday is None:
              self._byyearday = None
          else:
              if isinstance(byyearday, integer_types):
                  byyearday = (byyearday,)
  
              self._byyearday = set(byyearday)
  
          # byeaster
          if byeaster is not None:
              if not easter:
                  from dateutil import easter
              if isinstance(byeaster, integer_types):
                  self._byeaster = (byeaster,)
              else:
                  self._byeaster = tuple(byeaster)
          else:
              self._byeaster = None
  
          # bymonthay
          if bymonthday is None:
              self._bymonthday = ()
              self._bynmonthday = ()
          else:
              if isinstance(bymonthday, integer_types):
                  bymonthday = (bymonthday,)
  
              self._bymonthday = set([x for x in bymonthday if x > 0])
              self._bynmonthday = set([x for x in bymonthday if x < 0])
  
          # byweekno
          if byweekno is None:
              self._byweekno = None
          else:
              if isinstance(byweekno, integer_types):
                  byweekno = (byweekno,)
  
              self._byweekno = set(byweekno)
  
          # byweekday / bynweekday
          if byweekday is None:
              self._byweekday = None
              self._bynweekday = None
          else:
              if isinstance(byweekday, integer_types):
                  byweekday = (byweekday,)
              elif hasattr(byweekday, "n"):
                  byweekday = (byweekday.weekday,)
  
              self._byweekday = set()
              self._bynweekday = set()
              for wday in byweekday:
                  if isinstance(wday, integer_types):
                      self._byweekday.add(wday)
                  elif not wday.n or freq > MONTHLY:
                      self._byweekday.add(wday.weekday)
                  else:
                      self._bynweekday.add((wday.weekday, wday.n))
  
              if not self._byweekday:
                  self._byweekday = None
              elif not self._bynweekday:
                  self._bynweekday = None
  
          # byhour
          if byhour is None:
              if freq < HOURLY:
                  self._byhour = set((dtstart.hour,))
              else:
                  self._byhour = None
          else:
              if isinstance(byhour, integer_types):
                  byhour = (byhour,)
  
              if freq == HOURLY:
                  self._byhour = self.__construct_byset(start=dtstart.hour,
                                                        byxxx=byhour,
                                                        base=24)
              else:
                  self._byhour = set(byhour)
  
          # byminute
          if byminute is None:
              if freq < MINUTELY:
                  self._byminute = set((dtstart.minute,))
              else:
                  self._byminute = None
          else:
              if isinstance(byminute, integer_types):
                  byminute = (byminute,)
  
              if freq == MINUTELY:
                  self._byminute = self.__construct_byset(start=dtstart.minute,
                                                          byxxx=byminute,
                                                          base=60)
              else:
                  self._byminute = set(byminute)
  
          # bysecond
          if bysecond is None:
              if freq < SECONDLY:
                  self._bysecond = ((dtstart.second,))
              else:
                  self._bysecond = None
          else:
              if isinstance(bysecond, integer_types):
                  bysecond = (bysecond,)
  
              self._bysecond = set(bysecond)
  
              if freq == SECONDLY:
                  self._bysecond = self.__construct_byset(start=dtstart.second,
                                                          byxxx=bysecond,
                                                          base=60)
              else:
                  self._bysecond = set(bysecond)
  
          if self._freq >= HOURLY:
              self._timeset = None
          else:
              self._timeset = []
              for hour in self._byhour:
                  for minute in self._byminute:
                      for second in self._bysecond:
                          self._timeset.append(
                              datetime.time(hour, minute, second,
                                            tzinfo=self._tzinfo))
              self._timeset.sort()
              self._timeset = tuple(self._timeset)
  
      def _iter(self):
          year, month, day, hour, minute, second, weekday, yearday, _ = \
              self._dtstart.timetuple()
  
          # Some local variables to speed things up a bit
          freq = self._freq
          interval = self._interval
          wkst = self._wkst
          until = self._until
          bymonth = self._bymonth
          byweekno = self._byweekno
          byyearday = self._byyearday
          byweekday = self._byweekday
          byeaster = self._byeaster
          bymonthday = self._bymonthday
          bynmonthday = self._bynmonthday
          bysetpos = self._bysetpos
          byhour = self._byhour
          byminute = self._byminute
          bysecond = self._bysecond
  
          ii = _iterinfo(self)
          ii.rebuild(year, month)
  
          getdayset = {YEARLY: ii.ydayset,
                       MONTHLY: ii.mdayset,
                       WEEKLY: ii.wdayset,
                       DAILY: ii.ddayset,
                       HOURLY: ii.ddayset,
                       MINUTELY: ii.ddayset,
                       SECONDLY: ii.ddayset}[freq]
  
          if freq < HOURLY:
              timeset = self._timeset
          else:
              gettimeset = {HOURLY: ii.htimeset,
                            MINUTELY: ii.mtimeset,
                            SECONDLY: ii.stimeset}[freq]
              if ((freq >= HOURLY and
                   self._byhour and hour not in self._byhour) or
                  (freq >= MINUTELY and
                   self._byminute and minute not in self._byminute) or
                  (freq >= SECONDLY and
                   self._bysecond and second not in self._bysecond)):
                  timeset = ()
              else:
                  timeset = gettimeset(hour, minute, second)
  
          total = 0
          count = self._count
          while True:
              # Get dayset with the right frequency
              dayset, start, end = getdayset(year, month, day)
  
              # Do the "hard" work ;-)
              filtered = False
              for i in dayset[start:end]:
                  if ((bymonth and ii.mmask[i] not in bymonth) or
                      (byweekno and not ii.wnomask[i]) or
                      (byweekday and ii.wdaymask[i] not in byweekday) or
                      (ii.nwdaymask and not ii.nwdaymask[i]) or
                      (byeaster and not ii.eastermask[i]) or
                      ((bymonthday or bynmonthday) and
                       ii.mdaymask[i] not in bymonthday and
                       ii.nmdaymask[i] not in bynmonthday) or
                      (byyearday and
                       ((i < ii.yearlen and i+1 not in byyearday and
                         -ii.yearlen+i not in byyearday) or
                        (i >= ii.yearlen and i+1-ii.yearlen not in byyearday and
                         -ii.nextyearlen+i-ii.yearlen not in byyearday)))):
                      dayset[i] = None
                      filtered = True
  
              # Output results
              if bysetpos and timeset:
                  poslist = []
                  for pos in bysetpos:
                      if pos < 0:
                          daypos, timepos = divmod(pos, len(timeset))
                      else:
                          daypos, timepos = divmod(pos-1, len(timeset))
                      try:
                          i = [x for x in dayset[start:end]
                               if x is not None][daypos]
                          time = timeset[timepos]
                      except IndexError:
                          pass
                      else:
                          date = datetime.date.fromordinal(ii.yearordinal+i)
                          res = datetime.datetime.combine(date, time)
                          if res not in poslist:
                              poslist.append(res)
                  poslist.sort()
                  for res in poslist:
                      if until and res > until:
                          self._len = total
                          return
                      elif res >= self._dtstart:
                          total += 1
                          yield res
                          if count:
                              count -= 1
                              if not count:
                                  self._len = total
                                  return
              else:
                  for i in dayset[start:end]:
                      if i is not None:
                          date = datetime.date.fromordinal(ii.yearordinal+i)
                          for time in timeset:
                              res = datetime.datetime.combine(date, time)
                              if until and res > until:
                                  self._len = total
                                  return
                              elif res >= self._dtstart:
                                  total += 1
                                  yield res
                                  if count:
                                      count -= 1
                                      if not count:
                                          self._len = total
                                          return
  
              # Handle frequency and interval
              fixday = False
              if freq == YEARLY:
                  year += interval
                  if year > datetime.MAXYEAR:
                      self._len = total
                      return
                  ii.rebuild(year, month)
              elif freq == MONTHLY:
                  month += interval
                  if month > 12:
                      div, mod = divmod(month, 12)
                      month = mod
                      year += div
                      if month == 0:
                          month = 12
                          year -= 1
                      if year > datetime.MAXYEAR:
                          self._len = total
                          return
                  ii.rebuild(year, month)
              elif freq == WEEKLY:
                  if wkst > weekday:
                      day += -(weekday+1+(6-wkst))+self._interval*7
                  else:
                      day += -(weekday-wkst)+self._interval*7
                  weekday = wkst
                  fixday = True
              elif freq == DAILY:
                  day += interval
                  fixday = True
              elif freq == HOURLY:
                  if filtered:
                      # Jump to one iteration before next day
                      hour += ((23-hour)//interval)*interval
  
                  if byhour:
                      ndays, hour = self.__mod_distance(value=hour,
                                                        byxxx=self._byhour,
                                                        base=24)
                  else:
                      ndays, hour = divmod(hour+interval, 24)
  
                  if ndays:
                      day += ndays
                      fixday = True
  
                  timeset = gettimeset(hour, minute, second)
              elif freq == MINUTELY:
                  if filtered:
                      # Jump to one iteration before next day
                      minute += ((1439-(hour*60+minute))//interval)*interval
  
                  valid = False
                  rep_rate = (24*60)
                  for j in range(rep_rate // gcd(interval, rep_rate)):
                      if byminute:
                          nhours, minute = \
                              self.__mod_distance(value=minute,
                                                  byxxx=self._byminute,
                                                  base=60)
                      else:
                          nhours, minute = divmod(minute+interval, 60)
  
                      div, hour = divmod(hour+nhours, 24)
                      if div:
                          day += div
                          fixday = True
                          filtered = False
  
                      if not byhour or hour in byhour:
                          valid = True
                          break
  
                  if not valid:
                      raise ValueError('Invalid combination of interval and ' +
                                       'byhour resulting in empty rule.')
  
                  timeset = gettimeset(hour, minute, second)
              elif freq == SECONDLY:
                  if filtered:
                      # Jump to one iteration before next day
                      second += (((86399-(hour*3600+minute*60+second))
                                  // interval)*interval)
  
                  rep_rate = (24*3600)
                  valid = False
                  for j in range(0, rep_rate // gcd(interval, rep_rate)):
                      if bysecond:
                          nminutes, second = \
                              self.__mod_distance(value=second,
                                                  byxxx=self._bysecond,
                                                  base=60)
                      else:
                          nminutes, second = divmod(second+interval, 60)
  
                      div, minute = divmod(minute+nminutes, 60)
                      if div:
                          hour += div
                          div, hour = divmod(hour, 24)
                          if div:
                              day += div
                              fixday = True
  
                      if ((not byhour or hour in byhour) and
                              (not byminute or minute in byminute) and
                              (not bysecond or second in bysecond)):
                          valid = True
                          break
  
                  if not valid:
                      raise ValueError('Invalid combination of interval, ' +
                                       'byhour and byminute resulting in empty' +
                                       ' rule.')
  
                  timeset = gettimeset(hour, minute, second)
  
              if fixday and day > 28:
                  daysinmonth = calendar.monthrange(year, month)[1]
                  if day > daysinmonth:
                      while day > daysinmonth:
                          day -= daysinmonth
                          month += 1
                          if month == 13:
                              month = 1
                              year += 1
                              if year > datetime.MAXYEAR:
                                  self._len = total
                                  return
                          daysinmonth = calendar.monthrange(year, month)[1]
                      ii.rebuild(year, month)
  
      def __construct_byset(self, start, byxxx, base):
          """
          If a `BYXXX` sequence is passed to the constructor at the same level as
          `FREQ` (e.g. `FREQ=HOURLY,BYHOUR={2,4,7},INTERVAL=3`), there are some
          specifications which cannot be reached given some starting conditions.
  
          This occurs whenever the interval is not coprime with the base of a
          given unit and the difference between the starting position and the
          ending position is not coprime with the greatest common denominator
          between the interval and the base. For example, with a FREQ of hourly
          starting at 17:00 and an interval of 4, the only valid values for
          BYHOUR would be {21, 1, 5, 9, 13, 17}, because 4 and 24 are not
          coprime.
  
          :param:`start` specifies the starting position.
          :param:`byxxx` is an iterable containing the list of allowed values.
          :param:`base` is the largest allowable value for the specified
                        frequency (e.g. 24 hours, 60 minutes).
  
          This does not preserve the type of the iterable, returning a set, since
          the values should be unique and the order is irrelevant, this will
          speed up later lookups.
  
          In the event of an empty set, raises a :exception:`ValueError`, as this
          results in an empty rrule.
          """
  
          cset = set()
  
          # Support a single byxxx value.
          if isinstance(byxxx, integer_types):
              byxxx = (byxxx)
  
          for num in byxxx:
              i_gcd = gcd(self._interval, base)
              # Use divmod rather than % because we need to wrap negative nums.
              if i_gcd == 1 or divmod(num - start, i_gcd)[1] == 0:
                  cset.add(num)
  
          if len(cset) == 0:
              raise ValueError("Invalid rrule byxxx generates an empty set.")
  
          return cset
  
      def __mod_distance(self, value, byxxx, base):
          """
          Calculates the next value in a sequence where the `FREQ` parameter is
          specified along with a `BYXXX` parameter at the same "level"
          (e.g. `HOURLY` specified with `BYHOUR`).
  
          :param:`value` is the old value of the component.
          :param:`byxxx` is the `BYXXX` set, which should have been generated
                         by `rrule._construct_byset`, or something else which
                         checks that a valid rule is present.
          :param:`base` is the largest allowable value for the specified
                        frequency (e.g. 24 hours, 60 minutes).
  
          If a valid value is not found after `base` iterations (the maximum
          number before the sequence would start to repeat), this raises a
          :exception:`ValueError`, as no valid values were found.
  
          This returns a tuple of `divmod(n*interval, base)`, where `n` is the
          smallest number of `interval` repetitions until the next specified
          value in `byxxx` is found.
          """
          accumulator = 0
          for ii in range(1, base + 1):
              # Using divmod() over % to account for negative intervals
              div, value = divmod(value + self._interval, base)
              accumulator += div
              if value in byxxx:
                  return (accumulator, value)
  
  
  class _iterinfo(object):
      __slots__ = ["rrule", "lastyear", "lastmonth",
                   "yearlen", "nextyearlen", "yearordinal", "yearweekday",
                   "mmask", "mrange", "mdaymask", "nmdaymask",
                   "wdaymask", "wnomask", "nwdaymask", "eastermask"]
  
      def __init__(self, rrule):
          for attr in self.__slots__:
              setattr(self, attr, None)
          self.rrule = rrule
  
      def rebuild(self, year, month):
          # Every mask is 7 days longer to handle cross-year weekly periods.
          rr = self.rrule
          if year != self.lastyear:
              self.yearlen = 365+calendar.isleap(year)
              self.nextyearlen = 365+calendar.isleap(year+1)
              firstyday = datetime.date(year, 1, 1)
              self.yearordinal = firstyday.toordinal()
              self.yearweekday = firstyday.weekday()
  
              wday = datetime.date(year, 1, 1).weekday()
              if self.yearlen == 365:
                  self.mmask = M365MASK
                  self.mdaymask = MDAY365MASK
                  self.nmdaymask = NMDAY365MASK
                  self.wdaymask = WDAYMASK[wday:]
                  self.mrange = M365RANGE
              else:
                  self.mmask = M366MASK
                  self.mdaymask = MDAY366MASK
                  self.nmdaymask = NMDAY366MASK
                  self.wdaymask = WDAYMASK[wday:]
                  self.mrange = M366RANGE
  
              if not rr._byweekno:
                  self.wnomask = None
              else:
                  self.wnomask = [0]*(self.yearlen+7)
                  # no1wkst = firstwkst = self.wdaymask.index(rr._wkst)
                  no1wkst = firstwkst = (7-self.yearweekday+rr._wkst) % 7
                  if no1wkst >= 4:
                      no1wkst = 0
                      # Number of days in the year, plus the days we got
                      # from last year.
                      wyearlen = self.yearlen+(self.yearweekday-rr._wkst) % 7
                  else:
                      # Number of days in the year, minus the days we
                      # left in last year.
                      wyearlen = self.yearlen-no1wkst
                  div, mod = divmod(wyearlen, 7)
                  numweeks = div+mod//4
                  for n in rr._byweekno:
                      if n < 0:
                          n += numweeks+1
                      if not (0 < n <= numweeks):
                          continue
                      if n > 1:
                          i = no1wkst+(n-1)*7
                          if no1wkst != firstwkst:
                              i -= 7-firstwkst
                      else:
                          i = no1wkst
                      for j in range(7):
                          self.wnomask[i] = 1
                          i += 1
                          if self.wdaymask[i] == rr._wkst:
                              break
                  if 1 in rr._byweekno:
                      # Check week number 1 of next year as well
                      # TODO: Check -numweeks for next year.
                      i = no1wkst+numweeks*7
                      if no1wkst != firstwkst:
                          i -= 7-firstwkst
                      if i < self.yearlen:
                          # If week starts in next year, we
                          # don't care about it.
                          for j in range(7):
                              self.wnomask[i] = 1
                              i += 1
                              if self.wdaymask[i] == rr._wkst:
                                  break
                  if no1wkst:
                      # Check last week number of last year as
                      # well. If no1wkst is 0, either the year
                      # started on week start, or week number 1
                      # got days from last year, so there are no
                      # days from last year's last week number in
                      # this year.
                      if -1 not in rr._byweekno:
                          lyearweekday = datetime.date(year-1, 1, 1).weekday()
                          lno1wkst = (7-lyearweekday+rr._wkst) % 7
                          lyearlen = 365+calendar.isleap(year-1)
                          if lno1wkst >= 4:
                              lno1wkst = 0
                              lnumweeks = 52+(lyearlen +
                                              (lyearweekday-rr._wkst) % 7) % 7//4
                          else:
                              lnumweeks = 52+(self.yearlen-no1wkst) % 7//4
                      else:
                          lnumweeks = -1
                      if lnumweeks in rr._byweekno:
                          for i in range(no1wkst):
                              self.wnomask[i] = 1
  
          if (rr._bynweekday and (month != self.lastmonth or
                                  year != self.lastyear)):
              ranges = []
              if rr._freq == YEARLY:
                  if rr._bymonth:
                      for month in rr._bymonth:
                          ranges.append(self.mrange[month-1:month+1])
                  else:
                      ranges = [(0, self.yearlen)]
              elif rr._freq == MONTHLY:
                  ranges = [self.mrange[month-1:month+1]]
              if ranges:
                  # Weekly frequency won't get here, so we may not
                  # care about cross-year weekly periods.
                  self.nwdaymask = [0]*self.yearlen
                  for first, last in ranges:
                      last -= 1
                      for wday, n in rr._bynweekday:
                          if n < 0:
                              i = last+(n+1)*7
                              i -= (self.wdaymask[i]-wday) % 7
                          else:
                              i = first+(n-1)*7
                              i += (7-self.wdaymask[i]+wday) % 7
                          if first <= i <= last:
                              self.nwdaymask[i] = 1
  
          if rr._byeaster:
              self.eastermask = [0]*(self.yearlen+7)
              eyday = easter.easter(year).toordinal()-self.yearordinal
              for offset in rr._byeaster:
                  self.eastermask[eyday+offset] = 1
  
          self.lastyear = year
          self.lastmonth = month
  
      def ydayset(self, year, month, day):
          return list(range(self.yearlen)), 0, self.yearlen
  
      def mdayset(self, year, month, day):
          dset = [None]*self.yearlen
          start, end = self.mrange[month-1:month+1]
          for i in range(start, end):
              dset[i] = i
          return dset, start, end
  
      def wdayset(self, year, month, day):
          # We need to handle cross-year weeks here.
          dset = [None]*(self.yearlen+7)
          i = datetime.date(year, month, day).toordinal()-self.yearordinal
          start = i
          for j in range(7):
              dset[i] = i
              i += 1
              # if (not (0 <= i < self.yearlen) or
              #    self.wdaymask[i] == self.rrule._wkst):
              # This will cross the year boundary, if necessary.
              if self.wdaymask[i] == self.rrule._wkst:
                  break
          return dset, start, i
  
      def ddayset(self, year, month, day):
          dset = [None]*self.yearlen
          i = datetime.date(year, month, day).toordinal()-self.yearordinal
          dset[i] = i
          return dset, i, i+1
  
      def htimeset(self, hour, minute, second):
          tset = []
          rr = self.rrule
          for minute in rr._byminute:
              for second in rr._bysecond:
                  tset.append(datetime.time(hour, minute, second,
                                           tzinfo=rr._tzinfo))
          tset.sort()
          return tset
  
      def mtimeset(self, hour, minute, second):
          tset = []
          rr = self.rrule
          for second in rr._bysecond:
              tset.append(datetime.time(hour, minute, second, tzinfo=rr._tzinfo))
          tset.sort()
          return tset
  
      def stimeset(self, hour, minute, second):
          return (datetime.time(hour, minute, second,
                  tzinfo=self.rrule._tzinfo),)
  
  
  class rruleset(rrulebase):
      """ The rruleset type allows more complex recurrence setups, mixing
      multiple rules, dates, exclusion rules, and exclusion dates. The type
      constructor takes the following keyword arguments:
  
      :param cache: If True, caching of results will be enabled, improving
                    performance of multiple queries considerably. """
  
      class _genitem(object):
          def __init__(self, genlist, gen):
              try:
                  self.dt = advance_iterator(gen)
                  genlist.append(self)
              except StopIteration:
                  pass
              self.genlist = genlist
              self.gen = gen
  
          def __next__(self):
              try:
                  self.dt = advance_iterator(self.gen)
              except StopIteration:
                  self.genlist.remove(self)
  
          next = __next__
  
          def __lt__(self, other):
              return self.dt < other.dt
  
          def __gt__(self, other):
              return self.dt > other.dt
  
          def __eq__(self, other):
              return self.dt == other.dt
  
          def __ne__(self, other):
              return self.dt != other.dt
  
      def __init__(self, cache=False):
          super(rruleset, self).__init__(cache)
          self._rrule = []
          self._rdate = []
          self._exrule = []
          self._exdate = []
  
      def rrule(self, rrule):
          """ Include the given :py:class:`rrule` instance in the recurrence set
              generation. """
          self._rrule.append(rrule)
  
      def rdate(self, rdate):
          """ Include the given :py:class:`datetime` instance in the recurrence
              set generation. """
          self._rdate.append(rdate)
  
      def exrule(self, exrule):
          """ Include the given rrule instance in the recurrence set exclusion
              list. Dates which are part of the given recurrence rules will not
              be generated, even if some inclusive rrule or rdate matches them.
          """
          self._exrule.append(exrule)
  
      def exdate(self, exdate):
          """ Include the given datetime instance in the recurrence set
              exclusion list. Dates included that way will not be generated,
              even if some inclusive rrule or rdate matches them. """
          self._exdate.append(exdate)
  
      def _iter(self):
          rlist = []
          self._rdate.sort()
          self._genitem(rlist, iter(self._rdate))
          for gen in [iter(x) for x in self._rrule]:
              self._genitem(rlist, gen)
          rlist.sort()
          exlist = []
          self._exdate.sort()
          self._genitem(exlist, iter(self._exdate))
          for gen in [iter(x) for x in self._exrule]:
              self._genitem(exlist, gen)
          exlist.sort()
          lastdt = None
          total = 0
          while rlist:
              ritem = rlist[0]
              if not lastdt or lastdt != ritem.dt:
                  while exlist and exlist[0] < ritem:
                      advance_iterator(exlist[0])
                      exlist.sort()
                  if not exlist or ritem != exlist[0]:
                      total += 1
                      yield ritem.dt
                  lastdt = ritem.dt
              advance_iterator(ritem)
              rlist.sort()
          self._len = total
  
  
  class _rrulestr(object):
  
      _freq_map = {"YEARLY": YEARLY,
                   "MONTHLY": MONTHLY,
                   "WEEKLY": WEEKLY,
                   "DAILY": DAILY,
                   "HOURLY": HOURLY,
                   "MINUTELY": MINUTELY,
                   "SECONDLY": SECONDLY}
  
      _weekday_map = {"MO": 0, "TU": 1, "WE": 2, "TH": 3,
                      "FR": 4, "SA": 5, "SU": 6}
  
      def _handle_int(self, rrkwargs, name, value, **kwargs):
          rrkwargs[name.lower()] = int(value)
  
      def _handle_int_list(self, rrkwargs, name, value, **kwargs):
          rrkwargs[name.lower()] = [int(x) for x in value.split(',')]
  
      _handle_INTERVAL = _handle_int
      _handle_COUNT = _handle_int
      _handle_BYSETPOS = _handle_int_list
      _handle_BYMONTH = _handle_int_list
      _handle_BYMONTHDAY = _handle_int_list
      _handle_BYYEARDAY = _handle_int_list
      _handle_BYEASTER = _handle_int_list
      _handle_BYWEEKNO = _handle_int_list
      _handle_BYHOUR = _handle_int_list
      _handle_BYMINUTE = _handle_int_list
      _handle_BYSECOND = _handle_int_list
  
      def _handle_FREQ(self, rrkwargs, name, value, **kwargs):
          rrkwargs["freq"] = self._freq_map[value]
  
      def _handle_UNTIL(self, rrkwargs, name, value, **kwargs):
          global parser
          if not parser:
              from dateutil import parser
          try:
              rrkwargs["until"] = parser.parse(value,
                                               ignoretz=kwargs.get("ignoretz"),
                                               tzinfos=kwargs.get("tzinfos"))
          except ValueError:
              raise ValueError("invalid until date")
  
      def _handle_WKST(self, rrkwargs, name, value, **kwargs):
          rrkwargs["wkst"] = self._weekday_map[value]
  
      def _handle_BYWEEKDAY(self, rrkwargs, name, value, **kwarsg):
          l = []
          for wday in value.split(','):
              for i in range(len(wday)):
                  if wday[i] not in '+-0123456789':
                      break
              n = wday[:i] or None
              w = wday[i:]
              if n:
                  n = int(n)
              l.append(weekdays[self._weekday_map[w]](n))
          rrkwargs["byweekday"] = l
  
      _handle_BYDAY = _handle_BYWEEKDAY
  
      def _parse_rfc_rrule(self, line,
                           dtstart=None,
                           cache=False,
                           ignoretz=False,
                           tzinfos=None):
          if line.find(':') != -1:
              name, value = line.split(':')
              if name != "RRULE":
                  raise ValueError("unknown parameter name")
          else:
              value = line
          rrkwargs = {}
          for pair in value.split(';'):
              name, value = pair.split('=')
              name = name.upper()
              value = value.upper()
              try:
                  getattr(self, "_handle_"+name)(rrkwargs, name, value,
                                                 ignoretz=ignoretz,
                                                 tzinfos=tzinfos)
              except AttributeError:
                  raise ValueError("unknown parameter '%s'" % name)
              except (KeyError, ValueError):
                  raise ValueError("invalid '%s': %s" % (name, value))
          return rrule(dtstart=dtstart, cache=cache, **rrkwargs)
  
      def _parse_rfc(self, s,
                     dtstart=None,
                     cache=False,
                     unfold=False,
                     forceset=False,
                     compatible=False,
                     ignoretz=False,
                     tzinfos=None):
          global parser
          if compatible:
              forceset = True
              unfold = True
          s = s.upper()
          if not s.strip():
              raise ValueError("empty string")
          if unfold:
              lines = s.splitlines()
              i = 0
              while i < len(lines):
                  line = lines[i].rstrip()
                  if not line:
                      del lines[i]
                  elif i > 0 and line[0] == " ":
                      lines[i-1] += line[1:]
                      del lines[i]
                  else:
                      i += 1
          else:
              lines = s.split()
          if (not forceset and len(lines) == 1 and (s.find(':') == -1 or
                                                    s.startswith('RRULE:'))):
              return self._parse_rfc_rrule(lines[0], cache=cache,
                                           dtstart=dtstart, ignoretz=ignoretz,
                                           tzinfos=tzinfos)
          else:
              rrulevals = []
              rdatevals = []
              exrulevals = []
              exdatevals = []
              for line in lines:
                  if not line:
                      continue
                  if line.find(':') == -1:
                      name = "RRULE"
                      value = line
                  else:
                      name, value = line.split(':', 1)
                  parms = name.split(';')
                  if not parms:
                      raise ValueError("empty property name")
                  name = parms[0]
                  parms = parms[1:]
                  if name == "RRULE":
                      for parm in parms:
                          raise ValueError("unsupported RRULE parm: "+parm)
                      rrulevals.append(value)
                  elif name == "RDATE":
                      for parm in parms:
                          if parm != "VALUE=DATE-TIME":
                              raise ValueError("unsupported RDATE parm: "+parm)
                      rdatevals.append(value)
                  elif name == "EXRULE":
                      for parm in parms:
                          raise ValueError("unsupported EXRULE parm: "+parm)
                      exrulevals.append(value)
                  elif name == "EXDATE":
                      for parm in parms:
                          if parm != "VALUE=DATE-TIME":
                              raise ValueError("unsupported RDATE parm: "+parm)
                      exdatevals.append(value)
                  elif name == "DTSTART":
                      for parm in parms:
                          raise ValueError("unsupported DTSTART parm: "+parm)
                      if not parser:
                          from dateutil import parser
                      dtstart = parser.parse(value, ignoretz=ignoretz,
                                             tzinfos=tzinfos)
                  else:
                      raise ValueError("unsupported property: "+name)
              if (forceset or len(rrulevals) > 1 or rdatevals
                      or exrulevals or exdatevals):
                  if not parser and (rdatevals or exdatevals):
                      from dateutil import parser
                  rset = rruleset(cache=cache)
                  for value in rrulevals:
                      rset.rrule(self._parse_rfc_rrule(value, dtstart=dtstart,
                                                       ignoretz=ignoretz,
                                                       tzinfos=tzinfos))
                  for value in rdatevals:
                      for datestr in value.split(','):
                          rset.rdate(parser.parse(datestr,
                                                  ignoretz=ignoretz,
                                                  tzinfos=tzinfos))
                  for value in exrulevals:
                      rset.exrule(self._parse_rfc_rrule(value, dtstart=dtstart,
                                                        ignoretz=ignoretz,
                                                        tzinfos=tzinfos))
                  for value in exdatevals:
                      for datestr in value.split(','):
                          rset.exdate(parser.parse(datestr,
                                                   ignoretz=ignoretz,
                                                   tzinfos=tzinfos))
                  if compatible and dtstart:
                      rset.rdate(dtstart)
                  return rset
              else:
                  return self._parse_rfc_rrule(rrulevals[0],
                                               dtstart=dtstart,
                                               cache=cache,
                                               ignoretz=ignoretz,
                                               tzinfos=tzinfos)
  
      def __call__(self, s, **kwargs):
          return self._parse_rfc(s, **kwargs)
  
  rrulestr = _rrulestr()
  
  # vim:ts=4:sw=4:et
  