#!/usr/bin/env python
# -*- coding: utf-8 -*-

import datetime
import csv

class Booking:
    def __init__(self):
        self.id = -1              # Booking id
        self.start_date = None    # Start date of booking (as integer)
        self.end_date = None      # End date of booking (as integer)
        self.movable = False      # If the booking is movable or pre-colored
        self.color = -1           # The pre-colored color if not movable
        self.orig_color = -1      # The color from the know good coloring
        self.booking_date = None  # Date the booking was made (as integer)
        self.cc = None            # The current color class for the interval

class ColorClass:
    def __init__(self, colors = [], intervals = [], movable = 0):
        self.colors = colors        # Assigned colors (max density)
        self.intervals = intervals  # Assigned intervals (density)
        self.movable = movable      # Number of assigned movable intervals

# Create a booking for testing purposes
def book(start, end, color = -1, movable = lambda s, e, c: True):
    b = Booking()
    b.start_date = start
    b.end_date = end
    b.color = color
    b.movable = movable(start, end, color)
    return b

# Converts a string date ("07-04-2006" or "07/04/2006")
# to an integer
def str2date(s):
    splitchar = '/' if '/' in s else '-'
    l = map(int, s.split(' ')[0].split(splitchar))
    l.reverse()
    return (datetime.date(*tuple(l))).toordinal()

# Converts a string to whether or not a booking is movable
def str2movable(s):
    s = s.lower()
    if ('flytbar' in s) and ('ikke' in s):
        return False
    return True

# Converts each booking to two endpoints
# Each endpoint is a 3-tuple:
# (date as integer, 0/1, index of booking into bookings list)
# 1 = date is start date of booking
# 0 = date is end date of booking
# Sorting results in that for all dates the bookings that end that day
# come before all bookings that start that day (as required)
def bookings2endpoints(bookings):
    endpoints = []
    for i, b in enumerate(bookings):
        endpoints.append((b.start_date,1,i))
        endpoints.append((b.end_date,0,i))
    endpoints.sort()
    return endpoints

# Remove bookings which overlap in time and color
# (the color is the color given by the known coloring).
# This shouldn't really happen since that would mean that two
# booked the same spot for overlapping periods of time...?!?
# Similarly we give bookings which have a booking date strictly
# later than the start day of the booking, a booking date which
# is identical with the start date.
def sanitize(bookings, k):
    endpoints = bookings2endpoints(bookings)
    colors = k * [None]
    filtered = []
    for endpoint in endpoints:
        (_, t, b) = endpoint
        I = bookings[b]
        if I.booking_date > I.start_date:
            I.booking_date = I.start_date
        if t == 1: # start point
            if colors[I.orig_color] == None:
                colors[I.orig_color] = I
        else: # end point
            if colors[I.orig_color] == I:
                filtered.append(I)
                colors[I.orig_color] = None
    return filtered

# Loads bookings from file f and only load bookings of type t
def load_bookings(f, t):
    r = csv.reader(f)
    bookings = []

    # Map "strange"/arbitrary color names to consecutive integer values
    color_mapping = {}
    next_color = 0

    # First row is header
    row = r.next()

    if len(row) == 8: # Nordsoe Camping
        for row in r:
            # Only consider bookings for the specificed type
            if row[7] == t:
                b = Booking()
                b.id = int(row[1])
                b.start_date = str2date(row[2])
                b.end_date = str2date(row[3])
                if b.start_date > b.end_date:
                    tmp = b.start_date
                    b.start_date = b.end_date
                    b.end_date = tmp
                b.movable = str2movable(row[4])
                c = int(row[5])
                if c not in color_mapping:
                    color_mapping[c] = next_color
                    next_color = next_color + 1
                b.orig_color = color_mapping[c]
                b.booking_date = str2date(row[6])
                bookings.append(b)
    else: # Kolding Camping
        for row in r:
            # Only consider bookings for the specificed type
            if row[6] == t:
                b = Booking()
                b.id = int(row[0])
                b.start_date = str2date(row[1])
                b.end_date = str2date(row[2])
                if b.start_date > b.end_date:
                    tmp = b.start_date
                    b.start_date = b.end_date
                    b.end_date = tmp
                b.movable = str2movable(row[3])
                c = int(row[4])
                if c not in color_mapping:
                    color_mapping[c] = next_color
                    next_color = next_color + 1
                b.orig_color = color_mapping[c]
                b.booking_date = str2date(row[5])
                bookings.append(b)

    f.close()

    # Number of colors
    k = len(color_mapping)

    bookings = sanitize(bookings, k)

    # Strip color information from movable intervals and use precoloring from
    # know good coloring
    for I in bookings:
        if I.movable:
            I.color = -1
        else:
            I.color = I.orig_color

    return (bookings, k)

# Returns if interval I fits in color class cc
# Fits == with the currently assigned intervals in cc and
# future pre-colored intervals (colored with colors currently in cc)
# the density of cc is not exceeded.
def fit_in_cc(I, cc, precolored, precolored_index):
    colors = cc.colors[:]
    end = I.end_date
    points = []
    for J in cc.intervals:
        if not J.movable:
            colors.remove(J.color)
        else:
            points.append((J.end_date,0,J))
    capacity = len(colors)
    for c in colors:
        i = precolored_index[c]
        if i < len(precolored[c]):
            J = precolored[c][i]
            sd = J.start_date
            ed = J.end_date
            if ed <= end:
                points.append((sd,1,J))
                points.append((ed,0,J))
            elif sd < end:
                points.append((sd,1,J))
    points.sort()
    used = cc.movable
    for (_,t,J) in points:
        if t == 1: # start point
            used += 1
        else: # end point
            used -= 1
            if not J.movable:
                capacity -= 1
        if used >= capacity:
            return False
    return True

def prext(bookings, k):
    # Algorithm assumes bookings are sorted on start date
    bookings.sort(lambda I, J: I.start_date - J.start_date)

    endpoints = bookings2endpoints(bookings)

    # Find pre-colored intervals and make a list
    precolored = []
    for i in range(k):
        precolored.append([])
    for I in bookings:
        if not I.movable:
            precolored[I.color].append(I)

    # for each color: index of next precolored interval in the precolored list
    precolored_index = k * [0]

    # List of color classes
    ccs = [ColorClass(range(k),[],0)]

    # color class which contain no movable intervals (might be None)
    cc_zero = ccs[0]

    # Map colors to cc's, i.e., color i is in cc colors[i]
    colors = k * [ccs[0]]

    # State stack
    states = []

    # If we are moving forward (1), i.e., everything is going fine
    # or we are moving backwards (-1), .i.e., we have to undo choices
    direction = 1

    # The index of the currently considered endpoint
    i = 0

    while True:
        if i >= len(endpoints) or i < 0:
            break

        (_, t, b) = endpoints[i]
        I = bookings[b]

        if t == 1 and not I.movable: # Start point of pre-colored interval
            if direction == -1:
                cc = I.cc
                I.cc = None
                cc.intervals.pop()
                precolored_index[I.color] -= 1
                i -= 1
                continue
            else:
                precolored_index[I.color] += 1
                cc = colors[I.color]
                if len(cc.colors) > len(cc.intervals):
                    cc.intervals.append(I)
                    I.cc = cc
                    i += 1
                    continue
                else:
                    precolored_index[I.color] -= 1
                    i -= 1
                    direction = -1
                    continue

        elif t == 1 and I.movable: # Start point of movable interval
            j = 0
            if direction == -1:
                (j, cc_zero) = states.pop()
                cc = ccs[j]
                I.cc = None
                cc.movable -= 1
                cc.intervals.pop()
                j += 1
                direction = 1
            if direction == 1:
                try:
                    while j < len(ccs):
                        cc = ccs[j]
                        if len(cc.colors) > len(cc.intervals) and \
                               fit_in_cc(I, cc, precolored, precolored_index):
                            cc.intervals.append(I)
                            cc.movable += 1
                            states.append((j, cc_zero))
                            if cc == cc_zero:
                                cc_zero = None
                            I.cc = cc
                            raise Exception()
                        j += 1
                except:
                    i += 1
                    continue
                i -= 1
                direction = -1
                continue

        elif t == 0 and not I.movable: # End point of pre-colored interval
            if direction == 1:
                cc = I.cc
                i_index = cc.intervals.index(I)
                del cc.intervals[i_index]
                if len(cc.colors) > 1:
                    if (cc_zero != None) and (cc_zero != cc):
                        cc_zero.colors.append(I.color)
                        colors[I.color] = cc_zero
                        c_index = cc.colors.index(I.color)
                        del cc.colors[c_index]
                        states.append((0, cc_zero, i_index, c_index))
                    elif cc_zero != cc: # cc_zero == None
                        cc_new = ColorClass([I.color],[],0)
                        ccs.append(cc_new)
                        colors[I.color] = cc_new
                        cc_zero = cc_new
                        c_index = cc.colors.index(I.color)
                        del cc.colors[c_index]
                        states.append((1, cc_zero, i_index, c_index))
                    else: # cc_zero == cc
                        states.append((2, cc_zero, i_index, -1))
                    i += 1
                    continue
                else:
                    states.append((3, cc_zero, i_index, -1))
                    i += 1
                    continue
            else:
                (j, cc_zero, i_index, c_index) = states.pop()
                cc = I.cc
                if j == 0:
                    cc.colors.insert(c_index, I.color)
                    colors[I.color] = cc
                    cc_zero.colors.pop()
                elif j == 1:
                    cc.colors.insert(c_index, I.color)
                    colors[I.color] = cc
                    ccs.pop()
                    cc_zero = None
                cc.intervals.insert(i_index, I)
                i -= 1
                continue

        else: # t == 0 and I.movable: # End point of movable interval
            if direction == 1:
                cc = I.cc
                i_index = cc.intervals.index(I)
                del cc.intervals[i_index]
                cc.movable -= 1
                if cc.movable == 0:
                    if cc_zero != None:
                        cc_zero.colors.extend(cc.colors)
                        cc_zero.intervals.extend(cc.intervals)
                        for J in cc.intervals:
                            J.cc = cc_zero
                        for c in cc.colors:
                            colors[c] = cc_zero
                        cc_index = ccs.index(cc)
                        del ccs[cc_index]
                        states.append((0, cc_zero, i_index, cc_index))
                    else:
                        states.append((1, cc_zero, i_index, -1))
                        cc_zero = cc
                else:
                    states.append((2, cc_zero, i_index, -1))
                i += 1
                continue
            else:
                (j, cc_zero_old, i_index, cc_index) = states.pop()
                cc = I.cc
                if j == 0:
                    ccs.insert(cc_index, cc)
                    for c in cc.colors:
                        colors[c] = cc
                    for J in cc.intervals:
                        J.cc = cc
                    for c in cc.colors:
                        cc_zero.colors.remove(c)
                    for J in cc.intervals:
                        cc_zero.intervals.remove(J)
                cc_zero = cc_zero_old
                cc.movable += 1
                cc.intervals.insert(i_index, I)
                i -= 1
                continue

    if i < 0:
        return False

    else: # i >= len(endpoints):
        while i > 0:
            i -= 1
            (_, t, b) = endpoints[i]
            I = bookings[b]

            if t == 1 and not I.movable: # Start point of pre-colored interval
                I.cc.intervals.pop()
                continue

            elif t == 1 and I.movable: # Start point of movable interval
                (j, cc_zero) = states.pop()
                ccs[j].movable -= 1
                ccs[j].intervals.pop()
                continue

            elif t == 0 and not I.movable: # End point of pre-colored interval
                (j, cc_zero, i_index, c_index) = states.pop()
                if j == 0:
                    I.cc.colors.insert(c_index, I.color)
                    colors[I.color] = I.cc
                    cc_zero.colors.pop()
                elif j == 1:
                    I.cc.colors.insert(c_index, I.color)
                    colors[I.color] = I.cc
                    ccs.pop()
                    cc_zero = None
                I.cc.intervals.insert(i_index, I)
                continue

            else: # t == 0 and I.movable: # End point of movable interval
                (j, cc_zero_old, i_index, cc_index) = states.pop()
                cc = I.cc
                if j == 0:
                    ccs.insert(cc_index, cc)
                    for c in cc.colors:
                        colors[c] = cc
                    for J in cc.intervals:
                        J.cc = cc
                    for c in cc.colors:
                        cc_zero.colors.remove(c)
                    for J in cc.intervals:
                        cc_zero.intervals.remove(J)
                cc_zero = cc_zero_old
                cc.movable += 1
                cc.intervals.insert(i_index, I)
                # Assign I a color from cc not in use by other intervals
                used_colors = [J.color for J in cc.intervals if J.color != -1]
                for c in cc.colors:
                    if c not in used_colors:
                        I.color = c
                        break
                continue
        return True

def prext_noopt(bookings, k):
    # Algorithm assumes bookings are sorted on start date
    bookings.sort(lambda I, J: I.start_date - J.start_date)

    endpoints = bookings2endpoints(bookings)

    # Find pre-colored intervals and make a list
    precolored = []
    for i in range(k):
        precolored.append([])
    for I in bookings:
        if not I.movable:
            precolored[I.color].append(I)

    # for each color: index of next precolored interval in the precolored list
    precolored_index = k * [0]

    # List of color classes
    ccs = [ColorClass(range(k),[],0)]

    # color class which contain no movable intervals (might be None)
    cc_zero = ccs[0]

    # Map colors to cc's, i.e., color i is in cc colors[i]
    colors = k * [ccs[0]]

    # State stack
    states = []

    # If we are moving forward (1), i.e., everything is going fine
    # or we are moving backwards (-1), .i.e., we have to undo choices
    direction = 1

    # The index of the currently considered endpoint
    i = 0

    while True:
        if i >= len(endpoints) or i < 0:
            break

        (_, t, b) = endpoints[i]
        I = bookings[b]

        if t == 1 and not I.movable: # Start point of pre-colored interval
            if direction == -1:
                cc = I.cc
                I.cc = None
                cc.intervals.pop()
                precolored_index[I.color] -= 1
                i -= 1
                continue
            else:
                precolored_index[I.color] += 1
                cc = colors[I.color]
                if len(cc.colors) > len(cc.intervals):
                    cc.intervals.append(I)
                    I.cc = cc
                    i += 1
                    continue
                else:
                    precolored_index[I.color] -= 1
                    i -= 1
                    direction = -1
                    continue

        elif t == 1 and I.movable: # Start point of movable interval
            j = 0
            if direction == -1:
                (j, cc_zero) = states.pop()
                cc = ccs[j]
                I.cc = None
                cc.movable -= 1
                cc.intervals.pop()
                j += 1
                direction = 1
            if direction == 1:
                try:
                    while j < len(ccs):
                        cc = ccs[j]
                        if len(cc.colors) > len(cc.intervals):
                            cc.intervals.append(I)
                            cc.movable += 1
                            states.append((j, cc_zero))
                            if cc == cc_zero:
                                cc_zero = None
                            I.cc = cc
                            raise Exception()
                        j += 1
                except:
                    i += 1
                    continue
                i -= 1
                direction = -1
                continue

        elif t == 0 and not I.movable: # End point of pre-colored interval
            if direction == 1:
                cc = I.cc
                i_index = cc.intervals.index(I)
                del cc.intervals[i_index]
                if len(cc.colors) > 1:
                    if (cc_zero != None) and (cc_zero != cc):
                        cc_zero.colors.append(I.color)
                        colors[I.color] = cc_zero
                        c_index = cc.colors.index(I.color)
                        del cc.colors[c_index]
                        states.append((0, cc_zero, i_index, c_index))
                    elif cc_zero != cc: # cc_zero == None
                        cc_new = ColorClass([I.color],[],0)
                        ccs.append(cc_new)
                        colors[I.color] = cc_new
                        cc_zero = cc_new
                        c_index = cc.colors.index(I.color)
                        del cc.colors[c_index]
                        states.append((1, cc_zero, i_index, c_index))
                    else: # cc_zero == cc
                        states.append((2, cc_zero, i_index, -1))
                    i += 1
                    continue
                else:
                    states.append((3, cc_zero, i_index, -1))
                    i += 1
                    continue
            else:
                (j, cc_zero, i_index, c_index) = states.pop()
                cc = I.cc
                if j == 0:
                    cc.colors.insert(c_index, I.color)
                    colors[I.color] = cc
                    cc_zero.colors.pop()
                elif j == 1:
                    cc.colors.insert(c_index, I.color)
                    colors[I.color] = cc
                    ccs.pop()
                    cc_zero = None
                cc.intervals.insert(i_index, I)
                i -= 1
                continue

        else: # t == 0 and I.movable: # End point of movable interval
            if direction == 1:
                cc = I.cc
                i_index = cc.intervals.index(I)
                del cc.intervals[i_index]
                cc.movable -= 1
                if cc.movable == 0:
                    if cc_zero != None:
                        cc_zero.colors.extend(cc.colors)
                        cc_zero.intervals.extend(cc.intervals)
                        for J in cc.intervals:
                            J.cc = cc_zero
                        for c in cc.colors:
                            colors[c] = cc_zero
                        cc_index = ccs.index(cc)
                        del ccs[cc_index]
                        states.append((0, cc_zero, i_index, cc_index))
                    else:
                        states.append((1, cc_zero, i_index, -1))
                        cc_zero = cc
                else:
                    states.append((2, cc_zero, i_index, -1))
                i += 1
                continue
            else:
                (j, cc_zero_old, i_index, cc_index) = states.pop()
                cc = I.cc
                if j == 0:
                    ccs.insert(cc_index, cc)
                    for c in cc.colors:
                        colors[c] = cc
                    for J in cc.intervals:
                        J.cc = cc
                    for c in cc.colors:
                        cc_zero.colors.remove(c)
                    for J in cc.intervals:
                        cc_zero.intervals.remove(J)
                cc_zero = cc_zero_old
                cc.movable += 1
                cc.intervals.insert(i_index, I)
                i -= 1
                continue

    if i < 0:
        return False

    else: # i >= len(endpoints):
        while i > 0:
            i -= 1
            (_, t, b) = endpoints[i]
            I = bookings[b]

            if t == 1 and not I.movable: # Start point of pre-colored interval
                I.cc.intervals.pop()
                continue

            elif t == 1 and I.movable: # Start point of movable interval
                (j, cc_zero) = states.pop()
                ccs[j].movable -= 1
                ccs[j].intervals.pop()
                continue

            elif t == 0 and not I.movable: # End point of pre-colored interval
                (j, cc_zero, i_index, c_index) = states.pop()
                if j == 0:
                    I.cc.colors.insert(c_index, I.color)
                    colors[I.color] = I.cc
                    cc_zero.colors.pop()
                elif j == 1:
                    I.cc.colors.insert(c_index, I.color)
                    colors[I.color] = I.cc
                    ccs.pop()
                    cc_zero = None
                I.cc.intervals.insert(i_index, I)
                continue

            else: # t == 0 and I.movable: # End point of movable interval
                (j, cc_zero_old, i_index, cc_index) = states.pop()
                cc = I.cc
                if j == 0:
                    ccs.insert(cc_index, cc)
                    for c in cc.colors:
                        colors[c] = cc
                    for J in cc.intervals:
                        J.cc = cc
                    for c in cc.colors:
                        cc_zero.colors.remove(c)
                    for J in cc.intervals:
                        cc_zero.intervals.remove(J)
                cc_zero = cc_zero_old
                cc.movable += 1
                cc.intervals.insert(i_index, I)
                # Assign I a color from cc not in use by other intervals
                used_colors = [J.color for J in cc.intervals if J.color != -1]
                for c in cc.colors:
                    if c not in used_colors:
                        I.color = c
                        break
                continue
        return True