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 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:
    """A half-open range containing non-overlapping, positive-length intervals."""

    __slots__ = ('from_', 'to', 'l')

    def __init__(self, from_, to):
        if not from_ < to:
            raise ValueError('Line must have positive length')

        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):
        if not from_ < to:
            raise ValueError('Interval must have positive length')
        if not self.from_ <= from_ < to <= self.to:
            raise ValueError('Not included in interval')

        index = self.l.bisect_left(from_)
        if index > 0 and self.l[index - 1].to > from_:
            return False
        return index == len(self.l) or to <= self.l[index].from_

    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 = []
        cursor = self.from_
        for interval in self.l:
            if cursor < interval.from_:
                free_intervals.append([cursor, interval.from_])
            cursor = interval.to
        if cursor < self.to:
            free_intervals.append([cursor, self.to])

        return free_intervals

    @property
    def total_marked(self):
        return sum(
            (interval.to - interval.from_ for interval in self.l),
            self.total - self.total,
        )

    @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

from line import Line


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)  # 21 days, 0:00:00
    print(timeline.total_unmarked)  # 10 days, 0:00:00

if __name__ == '__main__':
    main()

requirements.txt

sortedcontainers