# -*- coding: utf-8 -*-
"""
:authors: python273
:license: Apache License, Version 2.0
:copyright: (c) 2018 python273
"""
from itertools import chain
from numbers import Number

from sortedcontainers import SortedList


class Container:
    __slots__ = ('from_', 'to', 'obj')

    def __init__(self, from_, to, obj=None):
        self.from_ = from_
        self.to = to
        self.obj = obj

    def __eq__(self, other):
        if isinstance(other, Number):
            return self.from_ == other

        return self.from_ == other.from_

    def __lt__(self, other):
        if isinstance(other, Number):
            return self.from_ < other

        return self.from_ < other.from_

    def __gt__(self, other):
        if isinstance(other, Number):
            return self.from_ > other

        return self.from_ > other.from_

    def __repr__(self):
        return 'Container({}, {}, {})'.format(self.from_, self.to, self.obj)


class Line:
    __slots__ = ('from_', 'to', 'l')

    def __init__(self, from_, to):
        self.from_ = from_
        self.to = to

        self.l = SortedList()

    def can_mark(self, from_, to):
        included = (
                (self.from_ <= from_ < self.to) and
                (self.from_ <= to < self.to)
        )
        if not included:
            raise ValueError('Not included in interval')

        existing_index = self.l.bisect(from_) - 1

        if existing_index >= 0:
            existing = self.l[existing_index]

            intersects = (
                    (existing.from_ <= from_ < existing.to) or
                    (existing.from_ <= to < existing.to)
            )

            if intersects:
                return False

            existing_index += 1
            if existing_index >= len(self.l):
                return True

            existing = self.l[existing_index]

            return to <= existing.from_

        return True

    def mark(self, from_, to, obj):
        if not self.can_mark(from_, to):
            raise ValueError('Already marked')

        self.l.add(Container(from_, to, obj))

    def __iter__(self):
        return iter(self.l)

    def get(self, x):
        existing_index = self.l.bisect(x) - 1

        if existing_index >= 0:
            existing = self.l[existing_index]

            if x < existing.to:
                return existing

        raise IndexError

    def get_free(self):
        free_intervals = []

        prev = None

        for curr in chain(self.l, [None]):
            if prev is None:
                if curr.from_ > self.from_:
                    free_intervals.append([self.from_, curr.from_])
            elif curr is None:
                if prev.to < self.to:
                    free_intervals.append([prev.to, self.to])
            else:
                if prev.to < curr.from_:
                    free_intervals.append([prev.to, curr.from_])

            prev = curr

        return free_intervals


def main():
    timeline = Line(from_=9, to=18)
    timeline.mark(from_=9, to=11, obj='Procrastinating')
    timeline.mark(from_=12, to=13, obj='Playing games')

    assert timeline.can_mark(from_=11, to=12) == True
    assert timeline.can_mark(from_=10, to=11) == False
    assert timeline.can_mark(from_=11, to=13) == False
    assert timeline.get_free() == [[11, 12], [13, 18]]
    assert timeline.get(10).obj == 'Procrastinating'
    assert timeline.get(12).obj == 'Playing games'

    for obj in timeline:
        print('From: {} To: {} Obj: {}'.format(obj.from_, obj.to, obj.obj))

    try:
        timeline.mark(from_=10, to=12.5, obj='Playing games')
    except ValueError:
        print('passed')

    try:
        timeline.mark(from_=9.5, to=10, obj='Playing games')
    except ValueError:
        print('passed')

    try:
        timeline.mark(from_=5, to=6, obj='Playing games')
    except ValueError:
        print('passed')

    try:
        timeline.get(11.5)
    except IndexError:
        print('passed')

    try:
        timeline.get(13)
    except IndexError:
        print('passed')


if __name__ == '__main__':
    main()