# HG changeset patch # User Paul Boddie # Date 1508628248 -7200 # Node ID a6c69e29fcbd93b9e25743d5d903fa15b75d4650 # Parent c675f7bdd52d178533bb4d6bcb5e6b9afa616fd9 Reworked various aspects of the recurrence computation implementation, removing explicit sort operations and changing day selection to produce results in order. diff -r c675f7bdd52d -r a6c69e29fcbd tests/qualifiers.py --- a/tests/qualifiers.py Fri Nov 24 18:11:57 2017 +0100 +++ b/tests/qualifiers.py Sun Oct 22 01:24:08 2017 +0200 @@ -443,7 +443,7 @@ qualifiers = [ ("MONTHLY", {"interval" : 1}), - ("BYMONTHDAY", {"values" : [2, 15]}) + ("BYMONTHDAY", {"values" : [15, 2]}) # test ordering ] l = order_qualifiers(qualifiers) @@ -804,4 +804,20 @@ print l[0] == (2018, 1, 1), (2018, 1, 1), l[0] print l[-1] == (2018, 1, 31), (2018, 1, 31), l[-1] +qualifiers = get_qualifiers(["FREQ=MONTHLY", "BYDAY=WE,1FR,2MO,2FR"]) + +l = order_qualifiers(qualifiers) +show(l) +dt = (2017, 10, 15) +l = get_datetime_structure(dt) +show(l) +l = combine_datetime_with_qualifiers(dt, qualifiers) +show(l) + +s = get_selector(dt, qualifiers) +l = s.materialise(dt, (2018, 1, 1)) +print len(l) == 17 +print l[0] == (2017, 10, 18), (2017, 10, 18), l[0] +print l[-1] == (2017, 12, 27), (2017, 12, 27), l[-1] + # vim: tabstop=4 expandtab shiftwidth=4 diff -r c675f7bdd52d -r a6c69e29fcbd vRecurrence.py --- a/vRecurrence.py Fri Nov 24 18:11:57 2017 +0100 +++ b/vRecurrence.py Sun Oct 22 01:24:08 2017 +0200 @@ -70,6 +70,10 @@ "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 = ( @@ -98,19 +102,34 @@ firstvalues = [0, 1, 1, 1, 1, 1, 0, 0, 0] -# Map from qualifiers to interval units. Here, weeks are defined as 7 days. +# Map from qualifiers to interval multiples. Here, weeks are defined as 7 days. -units = {"WEEKLY" : 7} +multiples = {"WEEKLY" : 7} # Make dictionaries mapping qualifiers to levels. -freq = dict([(level, i) for (i, level) in enumerate(freq_levels) if level]) -enum = dict([(level, i) for (i, level) in enumerate(enum_levels) if level]) -weekdays = dict([(weekday, i+1) for (i, weekday) in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"])]) +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: @@ -186,10 +205,15 @@ 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: @@ -237,15 +261,15 @@ l = [] offset = 0 - for level, value in enumerate(datetime): + for pos, value in enumerate(datetime): # At the day number, adjust the frequency level offset to reference # days (and then hours, minutes, seconds). - if level == 2: + if pos == 2: offset = 3 - l.append(Enum(level + offset, {"values" : [value]}, "DT")) + l.append(Enum(pos + offset, {"values" : [value]}, "DT")) return l @@ -318,7 +342,9 @@ # 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: + 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) @@ -352,24 +378,120 @@ 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 combine(t1, t2): +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): """ - Combine tuples 't1' and 't2', returning a copy of 't1' filled with values - from 't2' in positions where 0 appeared in 't1'. + Return the 1-based weekday sequence describing the first week of the month + referenced by 't'. """ - return tuple(map(lambda x, y: x or y, t1, t2)) + 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. -def scale(interval, pos): + 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): """ - Scale the given 'interval' value to the indicated position 'pos', returning - a tuple with leading zero elements and 'interval' at the stated position. + 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): @@ -413,24 +535,26 @@ d = datetime(*updated_for_months) s = timedelta(step[2], get_seconds(step)) - return to_tuple(d + s, len(t)) + return to_tuple(d + s)[:len(t)] -def to_tuple(d, n=None): +def to_tuple(d): - "Return 'd' as a tuple, optionally trimming the result to 'n' positions." + "Return date or datetime 'd' as a tuple." if not isinstance(d, date): return d - if n is None: - if isinstance(d, datetime): - n = 6 - else: - n = 3 + 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'." + """ + 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() @@ -441,7 +565,10 @@ def get_last_day(last_day, weekday): - "Return the last occurrence at or before 'last_day' of '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() @@ -450,6 +577,74 @@ 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 + # Classes for producing instances from recurrence structures. class Selector: @@ -472,12 +667,9 @@ self.selecting = selecting self.first = first - # Define the index of values from datetimes involved with this selector. - - self.pos = positions[level] - def __repr__(self): - return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.first) + return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, + self.args, self.qualifier, self.first) def materialise(self, start, end, count=None, setpos=None, inclusive=False): @@ -493,9 +685,8 @@ start = to_tuple(start) end = to_tuple(end) - counter = count and [0, count] + counter = Counter(count) results = self.materialise_items(start, start, end, counter, setpos, inclusive) - results.sort() return results[:count] def materialise_item(self, current, earliest, next, counter, setpos=None, inclusive=False): @@ -509,7 +700,8 @@ """ if self.selecting: - return self.selecting.materialise_items(current, earliest, next, counter, setpos, inclusive) + return self.selecting.materialise_items(current, earliest, next, + counter, setpos, inclusive) elif earliest <= current: return [current] else: @@ -521,9 +713,8 @@ l = [] for pos in setpos: - lower = pos < 0 and pos or pos - 1 - upper = pos > 0 and pos or pos < -1 and pos + 1 or None - l.append((lower, upper)) + index = pos < 0 and pos or pos - 1 + l.append(index) return l def select_positions(self, results, setpos): @@ -532,25 +723,15 @@ results.sort() l = [] - for lower, upper in self.convert_positions(setpos): - l += results[lower:upper] + for index in self.convert_positions(setpos): + l.append(results[index]) return l - def filter_by_period(self, results, start, end, inclusive): - - """ - Filter 'results' so that only those at or after 'start' and before 'end' - are returned. + def filter_by_period(self, result, start, end, inclusive): - If 'inclusive' is specified, the selection of instances will include the - end of the search period if present in the results. - """ + "Return whether 'result' occurs at or after 'start' and before 'end'." - l = [] - for result in results: - if start <= result and (inclusive and result <= end or result < end): - l.append(result) - return l + return start <= result and (inclusive and result <= end or result < end) class Pattern(Selector): @@ -569,26 +750,25 @@ # Define the step between result periods. - interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) - step = scale(interval, self.pos) + multiple = get_multiple(self.qualifier) + interval = self.args.get("interval", 1) * multiple + step = scale(interval, self.level) # Define the scale of a single period. - unit_interval = units.get(self.qualifier, 1) - unit_step = scale(unit_interval, self.pos) + unit_step = scale(multiple, self.level) # Employ the context as the current period if this is the first # qualifier in the selection chain. if self.first: - current = context[:self.pos+1] + current = precision(context, self.level) # Otherwise, obtain the first value at this resolution within the # context period. else: - first = scale(firstvalues[self.level], self.pos) - current = combine(context[:self.pos], first) + current = precision(context, self.level, firstvalues[self.level]) results = [] @@ -596,7 +776,7 @@ # provided that any limit imposed by the counter has not been exceeded. while (inclusive and current <= end or current < end) and \ - (counter is None or counter[0] < counter[1]): + not counter.at_limit(): # Increment the current datetime by the step for the next period. @@ -610,12 +790,13 @@ # current period and any contraining start and end points, plus # counter, setpos and inclusive details. - interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos, inclusive) + interval_results = self.materialise_item(current, + max(current, start), min(current_end, end), + counter, setpos, inclusive) # Update the counter with the number of identified results. - if counter is not None: - counter[0] += len(interval_results) + counter += len(interval_results) # Accumulate the results. @@ -632,21 +813,20 @@ "A selector of instances specified in terms of day numbers." def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): - step = scale(1, 2) + step = scale(1, WEEKS) results = [] # Get weekdays in the year. - if len(context) == 1: - first_day = (context[0], 1, 1) - last_day = (context[0], 12, 31) + if is_year_only(context): + first_day = start_of_year(context) + last_day = end_of_year(context) # Get weekdays in the month. - elif len(context) == 2: - first_day = (context[0], context[1], 1) - last_day = update((context[0], context[1], 1), (0, 1, 0)) - last_day = update(last_day, (0, 0, -1)) + elif is_month_only(context): + first_day = start_of_month(context) + last_day = end_of_month(context) # Get weekdays in the week. @@ -656,8 +836,11 @@ while (inclusive and current <= end or current < end): next = update(current, step) + if date(*current).isoweekday() in values: - results += self.materialise_item(current, max(current, start), min(next, end), counter, inclusive=inclusive) + results += self.materialise_item(current, + max(current, start), min(next, end), + counter, inclusive=inclusive) current = next if setpos: @@ -667,113 +850,113 @@ # Find each of the given days. - for value, index in self.args["values"]: - if index is not None: - offset = timedelta(7 * (abs(index) - 1)) + for value, index in sort_weekdays(self.args["values"], first_day, last_day): + offset = timedelta(7 * (abs(index) - 1)) + + current = precision(to_tuple(get_first_day(first_day, value) + offset), DAYS) + next = update(current, step) - if index < 0: - current = to_tuple(get_last_day(last_day, value) - offset, 3) - else: - current = to_tuple(get_first_day(first_day, value) + offset, 3) + # To support setpos, only current and next bound the search, not + # the period in addition. - next = update(current, step) + results += self.materialise_item(current, current, next, counter, + inclusive=inclusive) - # To support setpos, only current and next bound the search, not - # the period in addition. + # Extract selected positions and remove out-of-period instances. - results += self.materialise_item(current, current, next, counter, inclusive=inclusive) + if setpos: + results = self.select_positions(results, setpos) - else: - if index < 0: - current = to_tuple(get_last_day(last_day, value), 3) - direction = operator.sub - else: - current = to_tuple(get_first_day(first_day, value), 3) - direction = operator.add + return filter(lambda result: + self.filter_by_period(result, start, end, inclusive), + results) + +class Enum(Selector): + + "A generic value selector." + + def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): + step = scale(1, self.level) + results = [] - while first_day <= current <= last_day: - next = update(current, step) + # Select each value at the current resolution. + + for value in sort_values(self.args["values"]): + current = precision(context, self.level, value) + next = update(current, step) - # To support setpos, only current and next bound the search, not - # the period in addition. + # To support setpos, only current and next bound the search, not + # the period in addition. - results += self.materialise_item(current, current, next, counter, inclusive=inclusive) - current = to_tuple(direction(date(*current), timedelta(7)), 3) + results += self.materialise_item(current, current, next, counter, + setpos, inclusive) # Extract selected positions and remove out-of-period instances. if setpos: results = self.select_positions(results, setpos) - return self.filter_by_period(results, start, end, inclusive) + return filter(lambda result: + self.filter_by_period(result, start, end, inclusive), + results) -class Enum(Selector): +class MonthDayFilter(Enum): + + "A selector of month days." + def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): - step = scale(1, self.pos) + step = scale(1, self.level) results = [] - for value in self.args["values"]: - current = combine(context[:self.pos], scale(value, self.pos)) + + last_day = end_of_month(context)[2] + + for value in sort_values(self.args["values"], last_day): + current = precision(context, self.level, value) next = update(current, step) # To support setpos, only current and next bound the search, not # the period in addition. - results += self.materialise_item(current, current, next, counter, setpos, inclusive) + results += self.materialise_item(current, current, next, counter, + inclusive=inclusive) # Extract selected positions and remove out-of-period instances. if setpos: results = self.select_positions(results, setpos) - return self.filter_by_period(results, start, end, inclusive) + return filter(lambda result: + self.filter_by_period(result, start, end, inclusive), + results) -class MonthDayFilter(Enum): +class YearDayFilter(Enum): + + "A selector of days in years." + def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): - last_day = monthrange(context[0], context[1])[1] - step = scale(1, self.pos) + step = scale(1, self.level) results = [] - for value in self.args["values"]: - if value < 0: - value = last_day + 1 + value - current = combine(context, scale(value, self.pos)) + + year_length = get_year_length(context) + + for value in sort_values(self.args["values"], year_length): + current = day_in_year(context, value) next = update(current, step) # To support setpos, only current and next bound the search, not # the period in addition. - results += self.materialise_item(current, current, next, counter, inclusive=inclusive) + results += self.materialise_item(current, current, next, counter, + inclusive=inclusive) # Extract selected positions and remove out-of-period instances. if setpos: results = self.select_positions(results, setpos) - return self.filter_by_period(results, start, end, inclusive) - -class YearDayFilter(Enum): - def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): - first_day = date(context[0], 1, 1) - next_first_day = date(context[0] + 1, 1, 1) - year_length = (next_first_day - first_day).days - step = scale(1, self.pos) - results = [] - for value in self.args["values"]: - if value < 0: - value = year_length + 1 + value - current = to_tuple(first_day + timedelta(value - 1), 3) - next = update(current, step) - - # To support setpos, only current and next bound the search, not - # the period in addition. - - results += self.materialise_item(current, current, next, counter, inclusive=inclusive) - - # Extract selected positions and remove out-of-period instances. - - if setpos: - results = self.select_positions(results, setpos) - - return self.filter_by_period(results, start, end, inclusive) + return filter(lambda result: + self.filter_by_period(result, start, end, inclusive), + results) special_enum_levels = { "BYDAY" : WeekDayFilter, @@ -781,6 +964,21 @@ "BYYEARDAY" : YearDayFilter, } +class Counter: + + "A counter to track instance quantities." + + def __init__(self, limit): + self.current = 0 + self.limit = limit + + def __iadd__(self, n): + self.current += n + return self + + def at_limit(self): + return self.limit is not None and self.current >= self.limit + # Public functions. def connect_selectors(selectors):