#!/usr/bin/env python

"""

Managing and presenting periods of time.

Copyright (C) 2014, 2015 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/>.

"""

from bisect import bisect_left, bisect_right, insort_left

from datetime import date, datetime, timedelta

from imiptools.dates import format_datetime, get_datetime, \

                            get_datetime_attributes, \

                            get_recurrence_start, get_recurrence_start_point, \

                            get_start_of_day, \

                            get_tzid, \

                            to_timezone, to_utc_datetime

class PeriodBase:

    "A basic period abstraction."

    def as_tuple(self):

        return self.start, self.end

    def __hash__(self):

        return hash((self.get_start(), self.get_end()))

    def __cmp__(self, other):

        "Return a comparison result against 'other' using points in time."

        if isinstance(other, PeriodBase):

            return cmp(

                (self.get_start_point(), self.get_end_point()),

                (other.get_start_point(), other.get_end_point())

                )

        else:

            return 1

    def get_key(self):

        return self.get_start(), self.get_end()

    # Datetime and metadata methods.

    def get_start(self):

        return self.start

    def get_end(self):

        return self.end

    def get_start_attr(self):

        return get_datetime_attributes(self.start, self.tzid)

    def get_end_attr(self):

        return get_datetime_attributes(self.end, self.tzid)

    def get_start_item(self):

        return self.get_start(), self.get_start_attr()

    def get_end_item(self):

        return self.get_end(), self.get_end_attr()

    def get_start_point(self):

        return self.start

    def get_end_point(self):

        return self.end

    def get_duration(self):

        return self.get_end_point() - self.get_start_point()

class Period(PeriodBase):

    "A simple period abstraction."

    def __init__(self, start, end, tzid=None, origin=None):

        """

        Initialise a period with the given 'start' and 'end', having a

        contextual 'tzid', if specified, and an indicated 'origin'.

        All metadata from the start and end points are derived from the supplied

        dates/datetimes.

        """

        self.start = isinstance(start, date) and start or get_datetime(start)

        self.end = isinstance(end, date) and end or get_datetime(end)

        self.tzid = tzid

        self.origin = origin

    def as_tuple(self):

        return self.start, self.end, self.tzid, self.origin

    def __repr__(self):

        return "Period%r" % (self.as_tuple(),)

    # Datetime and metadata methods.

    def get_tzid(self):

        return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid

    def get_start_point(self):

        return to_utc_datetime(self.get_start(), self.get_tzid())

    def get_end_point(self):

        return to_utc_datetime(self.get_end(), self.get_tzid())

    # Period and event recurrence logic.

    def is_replaced(self, recurrenceids):

        """

        Return whether this period refers to one of the 'recurrenceids'.

        The 'recurrenceids' should be normalised to UTC datetimes according to

        time zone information provided by their objects or be floating dates or

        datetimes requiring conversion using contextual time zone information.

        """

        for recurrenceid in recurrenceids:

            if self.is_affected(recurrenceid):

                return recurrenceid

        return None

    def is_affected(self, recurrenceid):

        """

        Return whether this period refers to 'recurrenceid'. The 'recurrenceid'

        should be normalised to UTC datetimes according to time zone information

        provided by their objects. Otherwise, this period's contextual time zone

        information is used to convert any date or floating datetime

        representation to a point in time.

        """

        if not recurrenceid:

            return None

        d = get_recurrence_start(recurrenceid)

        dt = get_recurrence_start_point(recurrenceid, self.tzid)

        if self.get_start() == d or self.get_start_point() == dt:

            return recurrenceid

        return None

class FreeBusyPeriod(PeriodBase):

    "A free/busy record abstraction."

    def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None):

        """

        Initialise a free/busy period with the given 'start' and 'end' points,

        plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser'

        details.

        An additional 'expires' parameter can be used to indicate an expiry

        datetime in conjunction with free/busy offers made when countering

        event proposals.

        """

        self.start = isinstance(start, datetime) and start or get_datetime(start)

        self.end = isinstance(end, datetime) and end or get_datetime(end)

        self.uid = uid

        self.transp = transp

        self.recurrenceid = recurrenceid

        self.summary = summary

        self.organiser = organiser

        self.expires = expires

    def as_tuple(self, strings_only=False):

        """

        Return the initialisation parameter tuple, converting false value

        parameters to strings if 'strings_only' is set to a true value.

        """

        null = lambda x: (strings_only and [""] or [x])[0]

        return (

            strings_only and format_datetime(self.get_start_point()) or self.start,

            strings_only and format_datetime(self.get_end_point()) or self.end,

            self.uid or null(self.uid),

            self.transp or strings_only and "OPAQUE" or None,

            self.recurrenceid or null(self.recurrenceid),

            self.summary or null(self.summary),

            self.organiser or null(self.organiser),

            self.expires or null(self.expires)

            )

    def __cmp__(self, other):

        """

        Compare this object to 'other', employing the uid if the periods

        involved are the same.

        """

        result = PeriodBase.__cmp__(self, other)

        if result == 0 and isinstance(other, FreeBusyPeriod):

            return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid))

        else:

            return result

    def get_key(self):

        return self.uid, self.recurrenceid, self.get_start()

    def __repr__(self):

        return "FreeBusyPeriod%r" % (self.as_tuple(),)

    # Period and event recurrence logic.

    def is_replaced(self, recurrences):

        """

        Return whether this period refers to one of the 'recurrences'.

        The 'recurrences' must be UTC datetimes corresponding to the start of

        the period described by a recurrence.

        """

        for recurrence in recurrences:

            if self.is_affected(recurrence):

                return True

        return False

    def is_affected(self, recurrence):

        """

        Return whether this period refers to 'recurrence'. The 'recurrence' must

        be a UTC datetime corresponding to the start of the period described by

        a recurrence.

        """

        return recurrence and self.get_start_point() == recurrence

class RecurringPeriod(Period):

    """

    A period with iCalendar metadata attributes and origin information from an

    object.

    """

    def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None):

        Period.__init__(self, start, end, tzid, origin)

        self.start_attr = start_attr

        self.end_attr = end_attr

    def get_start_attr(self):

        return self.start_attr

    def get_end_attr(self):

        return self.end_attr

    def as_tuple(self):

        return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr

    def __repr__(self):

        return "RecurringPeriod%r" % (self.as_tuple(),)

# Time and period management.

def can_schedule(freebusy, periods, uid, recurrenceid):

    """

    Return whether the 'freebusy' list can accommodate the given 'periods'

    employing the specified 'uid' and 'recurrenceid'.

    """

    for conflict in have_conflict(freebusy, periods, True):

        if conflict.uid != uid or conflict.recurrenceid != recurrenceid:

            return False

    return True

def have_conflict(freebusy, periods, get_conflicts=False):

    """

    Return whether any period in 'freebusy' overlaps with the given 'periods',

    returning a collection of such overlapping periods if 'get_conflicts' is

    set to a true value.

    """

    conflicts = set()

    for p in periods:

        overlapping = period_overlaps(freebusy, p, get_conflicts)

        if overlapping:

            if get_conflicts:

                conflicts.update(overlapping)

            else:

                return True

    if get_conflicts:

        return conflicts

    else:

        return False

def insert_period(freebusy, period):

    "Insert into 'freebusy' the given 'period'."

    i = bisect_left(freebusy, period)

    if i == len(freebusy):

        freebusy.append(period)

    elif freebusy[i] != period:

        freebusy.insert(i, period)

def remove_period(freebusy, uid, recurrenceid=None):

    """

    Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid'

    (which if omitted causes the "parent" object's periods to be referenced).

    """

    removed = False

    i = 0

    while i < len(freebusy):

        fb = freebusy[i]

        if fb.uid == uid and fb.recurrenceid == recurrenceid:

            del freebusy[i]

            removed = True

        else:

            i += 1

    return removed

def remove_additional_periods(freebusy, uid, recurrenceids=None):

    """

    Remove from 'freebusy' all periods associated with 'uid' having a

    recurrence identifier indicating an additional or modified period.

    If 'recurrenceids' is specified, remove all periods associated with 'uid'

    that do not have a recurrence identifier in the given list.

    """

    i = 0

    while i < len(freebusy):

        fb = freebusy[i]

        if fb.uid == uid and fb.recurrenceid and (

            recurrenceids is None or

            recurrenceids is not None and fb.recurrenceid not in recurrenceids

            ):

            del freebusy[i]

        else:

            i += 1

def remove_affected_period(freebusy, uid, start):

    """

    Remove from 'freebusy' a period associated with 'uid' that provides an

    occurrence starting at the given 'start' (provided by a recurrence

    identifier, converted to a datetime). A recurrence identifier is used to

    provide an alternative time period whilst also acting as a reference to the

    originally-defined occurrence.

    """

    search = Period(start, start)

    found = bisect_left(freebusy, search)

    while found < len(freebusy):

        fb = freebusy[found]

        # Stop looking if the start no longer matches the recurrence identifier.

        if fb.get_start_point() != search.get_start_point():

            return

        # If the period belongs to the parent object, remove it and return.

        if not fb.recurrenceid and uid == fb.uid:

            del freebusy[found]

            break

        # Otherwise, keep looking for a matching period.

        found += 1

def periods_from(freebusy, period):

    "Return the entries in 'freebusy' at or after 'period'."

    first = bisect_left(freebusy, period)

    return freebusy[first:]

def periods_until(freebusy, period):

    "Return the entries in 'freebusy' before 'period'."

    last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid()))

    return freebusy[:last]

def get_overlapping(freebusy, period):

    """

    Return the entries in 'freebusy' providing periods overlapping with

    'period'.

    """

    # Find the range of periods potentially overlapping the period in the

    # free/busy collection.

    startpoints = periods_until(freebusy, period)

    # Find the range of periods potentially overlapping the period in a version

    # of the free/busy collection sorted according to end datetimes.

    endpoints = [(fb.get_end_point(), fb.get_start_point(), fb) for fb in startpoints]

    endpoints.sort()

    first = bisect_left(endpoints, (period.get_start_point(),))

    endpoints = endpoints[first:]

    overlapping = set()

    for end, start, fb in endpoints:

        if end > period.get_start_point() and start < period.get_end_point():

            overlapping.add(fb)

    overlapping = list(overlapping)

    overlapping.sort()

    return overlapping

def period_overlaps(freebusy, period, get_periods=False):

    """

    Return whether any period in 'freebusy' overlaps with the given 'period',

    returning a collection of overlapping periods if 'get_periods' is set to a

    true value.

    """

    overlapping = get_overlapping(freebusy, period)

    if get_periods:

        return overlapping

    else:

        return len(overlapping) != 0

def remove_overlapping(freebusy, period):

    "Remove from 'freebusy' all periods overlapping with 'period'."

    overlapping = get_overlapping(freebusy, period)

    if overlapping:

        for fb in overlapping:

            freebusy.remove(fb)

def replace_overlapping(freebusy, period, replacements):

    """

    Replace existing periods in 'freebusy' within the given 'period', using the

    given 'replacements'.

    """

    remove_overlapping(freebusy, period)

    for replacement in replacements:

        insert_period(freebusy, replacement)

def coalesce_freebusy(freebusy):

    "Coalesce the periods in 'freebusy'."

    if not freebusy:

        return freebusy

    fb = []

    start = freebusy[0].get_start_point()

    end = freebusy[0].get_end_point()

    for period in freebusy[1:]:

        if period.get_start_point() > end:

            fb.append(FreeBusyPeriod(start, end))

            start = period.get_start_point()

            end = period.get_end_point()

        else:

            end = max(end, period.get_end_point())

    fb.append(FreeBusyPeriod(start, end))

    return fb

def invert_freebusy(freebusy):

    "Return the free periods from 'freebusy'."

    if not freebusy:

        return None

    fb = coalesce_freebusy(freebusy)

    free = []

    start = fb[0].get_end_point()

    for period in fb[1:]:

        free.append(FreeBusyPeriod(start, period.get_start_point()))

        start = period.get_end_point()

    return free

# Period layout.

def get_scale(periods, tzid):

    """

    Return an ordered time scale from the given list of 'periods'.

    The given 'tzid' is used to make sure that the times are defined according

    to the chosen time zone.

    The returned scale is a mapping from time to (starting, ending) tuples,

    where starting and ending are collections of periods.

    """

    scale = {}

    for p in periods:

        # Add a point and this event to the starting list.

        start = to_timezone(p.get_start(), tzid)

        if not scale.has_key(start):

            scale[start] = [], []

        scale[start][0].append(p)

        # Add a point and this event to the ending list.

        end = to_timezone(p.get_end(), tzid)

        if not scale.has_key(end):

            scale[end] = [], []

        scale[end][1].append(p)

    return scale

class Point:

    "A qualified point in time."

    PRINCIPAL, REPEATED = 0, 1

    def __init__(self, point, indicator=None):

        self.point = point

        self.indicator = indicator or self.PRINCIPAL

    def __hash__(self):

        return hash((self.point, self.indicator))

    def __cmp__(self, other):

        if isinstance(other, Point):

            return cmp((self.point, self.indicator), (other.point, other.indicator))

        elif isinstance(other, datetime):

            return cmp(self.point, other)

        else:

            return 1

    def __eq__(self, other):

        return self.__cmp__(other) == 0

    def __ne__(self, other):

        return not self == other

    def __lt__(self, other):

        return self.__cmp__(other) < 0

    def __le__(self, other):

        return self.__cmp__(other) <= 0

    def __gt__(self, other):

        return not self <= other

    def __ge__(self, other):

        return not self < other

    def __repr__(self):

        return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL")

def get_slots(scale):

    """

    Return an ordered list of time slots from the given 'scale'.

    Each slot is a tuple containing details of a point in time for the start of

    the slot, together with a list of parallel event periods.

    Each point in time is described as a Point representing the actual point in

    time together with an indicator of the nature of the point in time (as a

    principal point in a time scale or as a repeated point used to terminate

    events occurring for an instant in time).

    """

    slots = []

    active = []

    points = scale.items()

    points.sort()

    for point, (starting, ending) in points:

        ending = set(ending)

        instants = ending.intersection(starting)

        # Discard all active events ending at or before this start time.

        # Free up the position in the active list.

        for t in ending.difference(instants):

            i = active.index(t)

            active[i] = None

        # For each event starting at the current point, fill any newly-vacated

        # position or add to the end of the active list.

        for t in starting:

            try:

                i = active.index(None)

                active[i] = t

            except ValueError:

                active.append(t)

        # Discard vacant positions from the end of the active list.

        while active and active[-1] is None:

            active.pop()

        # Add an entry for the time point before "instants".

        slots.append((Point(point), active[:]))

        # Discard events ending at the same time as they began.

        if instants:

            for t in instants:

                i = active.index(t)

                active[i] = None

            # Discard vacant positions from the end of the active list.

            while active and active[-1] is None:

                active.pop()

            # Add another entry for the time point after "instants".

            slots.append((Point(point, Point.REPEATED), active[:]))

    return slots

def add_day_start_points(slots, tzid):

    """

    Introduce into the 'slots' any day start points required by multi-day

    periods. The 'tzid' is required to make sure that appropriate time zones

    are chosen and not necessarily those provided by the existing time points.

    """

    new_slots = []

    current_date = None

    previously_active = []

    for point, active in slots:

        start_of_day = get_start_of_day(point.point, tzid)

        this_date = point.point.date()

        # For each new day, add a slot for the start of the day where periods

        # are active and where no such slot already exists.

        if this_date != current_date:

            # Fill in days where events remain active.

            if current_date:

                current_date += timedelta(1)

                while current_date < this_date:

                    new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active))

                    current_date += timedelta(1)

            else:

                current_date = this_date

            # Add any continuing periods.

            if point.point != start_of_day:

                new_slots.append((Point(start_of_day), previously_active))

        # Add the currently active periods at this point in time.

        previously_active = active

    for t in new_slots:

        insort_left(slots, t)

def add_slots(slots, points):

    """

    Introduce into the 'slots' entries for those in 'points' that are not

    already present, propagating active periods from time points preceding

    those added.

    """

    new_slots = []

    for point in points:

        i = bisect_left(slots, (point,)) # slots is [(point, active)...]

        if i < len(slots) and slots[i][0] == point:

            continue

        new_slots.append((point, i > 0 and slots[i-1][1] or []))

    for t in new_slots:

        insort_left(slots, t)

def partition_by_day(slots):

    """

    Return a mapping from dates to time points provided by 'slots'.

    """

    d = {}

    for point, value in slots:

        day = point.point.date()

        if not d.has_key(day):

            d[day] = []

        d[day].append((point, value))

    return d

def add_empty_days(days, tzid):

    "Add empty days to 'days' between busy days."

    last_day = None

    all_days = days.keys()

    all_days.sort()

    for day in all_days:

        if last_day:

            empty_day = last_day + timedelta(1)

            while empty_day < day:

                days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)]

                empty_day += timedelta(1)

        last_day = day 

def get_spans(slots):

    "Inspect the given 'slots', returning a mapping of period keys to spans."

    points = [point for point, active in slots]

    spans = {}

    for _point, active in slots:

        for p in active:

            if p:

                key = p.get_key()

                start_slot = bisect_left(points, p.get_start())

                end_slot = bisect_left(points, p.get_end())

                spans[key] = end_slot - start_slot