#!/usr/bin/env python

"""

Recurrence rule calculation.

Copyright (C) 2014 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 = (

    "SECONDLY",

    "MINUTELY",

    "HOURLY",

    "DAILY",

    "WEEKLY",

    "MONTHLY",

    "YEARLY"

    )

# Enumeration levels, employed by BY... qualifiers.

enum_levels = (

    ("BYSECOND",),

    ("BYMINUTE",),

    ("BYHOUR",),

    ("BYDAY", "BYMONTHDAY", "BYYEARDAY"),

    ("BYWEEKNO",),

    ("BYMONTH",)

    )

# Map from levels to lengths of datetime tuples.

lengths = [6, 5, 4, 3, 3, 2, 1]

positions = [l-1 for l in lengths]

# Map from qualifiers to interval units. Here, weeks are defined as 7 days.

units = {"WEEKLY" : 7}

# Map from tuple positions to base values at each resolution.

bases = [0, 1, 1, 0, 0, 0]

def basevalue(resolution):

    return bases[positions[resolution]]

# Make dictionaries mapping qualifiers to levels.

freq = dict([(level, i) for (i, level) in enumerate(freq_levels)])

enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) for level in levels])

# Functions for structuring the recurrences.

def get_next(it):

    try:

        return it.next()

    except StopIteration:

        return None

def order_qualifiers(qualifiers):

    "Return the 'qualifiers' in order of increasing resolution."

    l = []

    for qualifier, args in qualifiers:

        if enum.has_key(qualifier):

            level = enum[qualifier]

            if special_enum_levels.has_key(qualifier):

                args["interval"] = 1

                selector = special_enum_levels[qualifier]

            else:

                selector = Enum

        else:

            level = freq[qualifier]

            selector = Pattern

        pos = positions[level]

        l.append(selector(pos, args, qualifier))

    l.sort(key=lambda x: x.pos)

    return l

def get_datetime_structure(datetime):

    "Return the structure of 'datetime' for recurrence production."

    l = []

    for pos, value in enumerate(datetime):

        l.append(Enum(pos, {"values" : [value]}, "DT"))

    return l

def combine_datetime_with_qualifiers(datetime, qualifiers):

    """

    Combine 'datetime' with 'qualifiers' to produce a structure for recurrence

    production.

    """

    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

    context = []

    # Consume from both lists, merging entries.

    while from_dt and from_q:

        _pos = from_dt.pos

        pos = from_q.pos

        # Datetime value at wider resolution.

        if _pos < pos:

            context.append(from_dt.args["values"][0])

            from_dt = get_next(iter_dt)

        # Qualifier at wider or same resolution as datetime value.

        else:

            if not have_q:

                if isinstance(from_q, Enum) and pos > 0:

                    repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT")

                    repeat.context = tuple(context)

                    l.append(repeat)

                else:

                    from_q.context = tuple(context)

                have_q = True

            # Either introduce the qualifier first.

            if _pos > pos:

                l.append(from_q)

            # Or combine the qualifier and value details.

            else:

                context.append(from_dt.args["values"][0])

                l.append(combine_context_with_qualifier(context, from_q))

                from_dt = get_next(iter_dt)

            from_q = get_next(iter_q)

    # Complete the list.

    while from_dt:

        l.append(from_dt)

        from_dt = get_next(iter_dt)

    while from_q:

        if not have_q:

            if isinstance(from_q, Enum) and pos > 0:

                repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT")

                repeat.context = tuple(context)

                l.append(repeat)

            else:

                from_q.context = tuple(context)

            have_q = True

        l.append(from_q)

        from_q = get_next(iter_q)

    return l

def combine_context_with_qualifier(context, from_q):

    """

    Combine 'context' information (a datetime) and 'from_q' (a qualifier),

    imposing the datetime value information on any qualifiers.

    """

    if not from_q.args.has_key("values"):

        from_q.context = tuple(context)

    return from_q

# Datetime arithmetic.

def combine(t1, t2):

    return tuple(map(lambda x, y: x or y, t1, t2))

def scale(interval, pos):

    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 (d + s).timetuple()[:len(t)]

# Classes for producing instances from recurrence structures.

class Selector:

    def __init__(self, pos, args, qualifier, selecting=None):

        self.pos = pos

        self.args = args

        self.qualifier = qualifier

        self.context = ()

        self.selecting = selecting

    def __repr__(self):

        return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context)

    def materialise(self, start, end, count=None):

        counter = count and [0, count]

        return self.materialise_items(self.context, start, end, counter)

    def materialise_item(self, current, last, next, counter):

        if counter is None or counter[0] < counter[1]:

            if self.selecting:

                return self.selecting.materialise_items(current, last, next, counter)

            elif last <= current:

                if counter is not None:

                    counter[0] += 1

                return [current]

        return []

class Pattern(Selector):

    def materialise_items(self, context, start, end, counter):

        first = scale(self.context[self.pos], self.pos)

        # Define the step between items.

        interval = self.args.get("interval", 1) * units.get(self.qualifier, 1)

        step = scale(interval, self.pos)

        # Define the scale of a single item.

        unit_interval = units.get(self.qualifier, 1)

        unit_step = scale(unit_interval, self.pos)

        current = combine(context, first)

        results = []

        while current < end and (counter is None or counter[0] < counter[1]):

            next = update(current, step)

            current_end = update(current, unit_step)

            results += self.materialise_item(current, max(current, start), min(current_end, end), counter)

            current = next

        return results

class WeekDayFilter(Selector):

    def materialise_items(self, context, start, end, counter):

        first = scale(bases[self.pos], self.pos)

        # Define the step between items to be tested.

        step = scale(1, self.pos)

        current = combine(context, first)

        results = []

        while current < end and (counter is None or counter[0] < counter[1]):

            next = update(current, step)

            results += self.materialise_item(current, max(current, start), min(next, end), counter)

            current = next

        return results

    def materialise_item(self, current, last, next, counter):

        values = self.args["values"]

        # Select by day in week, also by occurrence in month.

        for value, index in values:

            if datetime(*current).isoweekday() == value:

                last_day = monthrange(current[0], current[1])[1]

                index_from_start = (current[2] - 1) / 7

                index_from_end = -(1 + (last_day - current[2]) / 7)

                if index is None or index in (index_from_start, index_from_end):

                    return Selector.materialise_item(self, current, last, next, counter)

        return []

class Enum(Selector):

    def materialise_items(self, context, start, end, counter):

        step = scale(1, self.pos)

        results = []

        for value in self.args["values"]:

            current = combine(context, scale(value, self.pos))

            if current < end and (counter is None or counter[0] < counter[1]):

                next = update(current, step)

                results += self.materialise_item(current, max(current, start), min(next, end), counter)

        return results

class MonthDayFilter(Enum):

    def materialise_items(self, context, start, end, counter):

        last_day = monthrange(context[0], context[1])[1]

        step = scale(1, self.pos)

        results = []

        for value in self.args["values"]:

            if value < 0:

                value = last_day + 1 + value

            current = combine(context, scale(value, self.pos))

            if current < end and (counter is None or counter[0] < counter[1]):

                next = update(current, step)

                results += self.materialise_item(current, max(current, start), min(next, end), counter)

        return results

class YearDayFilter(Enum):

    def materialise_items(self, context, start, end, counter):

        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 = (first_day + timedelta(value - 1)).timetuple()[:3]

            if current < end and (counter is None or counter[0] < counter[1]):

                next = update(current, step)

                results += self.materialise_item(current, max(current, start), min(next, end), counter)

        return results

def process(selectors):

    current = selectors[0]

    for selector in selectors[1:]:

        current.selecting = selector

        current = selector

    return selectors[0]

special_enum_levels = {

    "BYDAY" : WeekDayFilter,

    "BYMONTHDAY" : MonthDayFilter,

    "BYYEARDAY" : YearDayFilter,

    }

# vim: tabstop=4 expandtab shiftwidth=4