Python line (e.g. timeline) with non-intersecting intervals implementation

line.py

# -*- coding: utf-8 -*-
"""
:authors: python273
:license: Apache License, Version 2.0
:copyright: (c) 2018 python273
"""
from functools import reduce
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, (Container, Line)):
            return self.from_ == other.from_

        return self.from_ == other

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

        return self.from_ < other

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

        return self.from_ > other

    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 __iter__(self):
        return iter(self.l)

    @property
    def total(self):
        return self.to - self.from_

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

    @property
    def total_marked(self):
        return reduce(
            lambda a, b: (a[1] - a[0]) + (b[1] - b[0]),
            self.get_free()
        )

    @property
    def total_unmarked(self):
        return self.total - self.total_marked


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()

line_datetime_example.py

from datetime import datetime


def main():
    timeline = Line(from_=datetime(2018, 10, 1), to=datetime(2018, 11, 1))
    timeline.mark(datetime(2018, 10, 1), datetime(2018, 10, 6), 'A')
    timeline.mark(datetime(2018, 10, 10), datetime(2018, 10, 16), 'B')
    timeline.mark(datetime(2018, 10, 16), datetime(2018, 10, 21), 'C')
    timeline.mark(datetime(2018, 10, 21), datetime(2018, 10, 26), 'D')

    print(timeline.get_free())
    # [
    #     [datetime.datetime(2018, 10, 6, 0, 0), datetime.datetime(2018, 10, 10, 0, 0)],
    #     [datetime.datetime(2018, 10, 26, 0, 0), datetime.datetime(2018, 11, 1, 0, 0)]
    # ]

    print(timeline.total)  # 31 days, 0:00:00
    print(timeline.total_marked)  # 10 days, 0:00:00
    print(timeline.total_unmarked)  # 21 days, 0:00:00

if __name__ == '__main__':
    main()

requirements.txt

sortedcontainers