#!/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_start_of_day, to_timezone

class Period:

    "A basic period abstraction."

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

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

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

        self.origin = origin

    def as_tuple(self):

        return self.start, self.end

    def __hash__(self):

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

    def __cmp__(self, other):

        if isinstance(other, Period):

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

        else:

            return 1

    def get_key(self):

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

    def __repr__(self):

        return "Period(%r, %r)" % (self.start, self.end)

    # Datetime metadata methods.

    def get_start(self, tzid=None):

        if tzid:

            return to_timezone(self.start, tzid)

        else:

            return self.start

    def get_end(self, tzid=None):

        if tzid:

            return to_timezone(self.end, tzid)

        else:

            return self.end

    def get_start_item(self):

        return self.start, get_datetime_attributes(self.start)

    def get_end_item(self):

        return self.end, get_datetime_attributes(self.end)

class FreeBusyPeriod(Period):

    "A free/busy record abstraction."

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

        """

        Initialise a free/busy period with 'start' and 'end' datetime string

        representations, employing UTC, plus any 'uid', 'transp',

        'recurrenceid', 'summary' and 'organiser' details.

        """

        Period.__init__(self, start, end)

        self.uid = uid

        self.transp = transp

        self.recurrenceid = recurrenceid

        self.summary = summary

        self.organiser = organiser

    def as_tuple(self):

        return format_datetime(self.start), format_datetime(self.end), self.uid, self.transp, self.recurrenceid, self.summary, self.organiser

    def __cmp__(self, other):

        if isinstance(other, FreeBusyPeriod):

            return cmp((self.start, self.end, self.uid), (other.start, other.end, other.uid))

        else:

            return Period.__cmp__(self, other)

    def get_key(self):

        return self.uid, self.recurrenceid, self.start

    def __repr__(self):

        return "FreeBusyPeriod(%r, %r, %r, %r, %r, %r, %r)" % (

            self.start, self.end, self.uid, self.transp, self.recurrenceid,

            self.summary, self.organiser)

# 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'."

    insort_left(freebusy, 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.

    """

    found = bisect_left(freebusy, Period(start))

    while found < len(freebusy):

        fb = freebusy[found]

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

        if fb.get_start() != start:

            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 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.

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

    startpoints = freebusy[:last]

    # 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(), fb.get_start(), fb) for fb in startpoints]

    endpoints.sort()

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

    endpoints = endpoints[first:]

    overlapping = set()

    for end, start, fb in endpoints:

        if end > period.get_start() and start < period.get_end():

            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)

# 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.

        if not scale.has_key(p.get_start(tzid)):

            scale[p.get_start(tzid)] = [], []

        scale[p.get_start(tzid)][0].append(p)

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

        if not scale.has_key(p.get_end(tzid)):

            scale[p.get_end(tzid)] = [], []

        scale[p.get_end(tzid)][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 event uids 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

    return spans

def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser):

    """

    Update the free/busy details with the given 'periods', 'transp' setting,

    'uid' plus 'recurrenceid' and 'summary' and 'organiser' details.

    """

    remove_period(freebusy, uid, recurrenceid)

    for p in periods:

        insert_period(freebusy, FreeBusyPeriod(p.get_start(), p.get_end(), uid, transp, recurrenceid, summary, organiser))

# vim: tabstop=4 expandtab shiftwidth=4