intervals_to_disjoint_intervals

#!python
# -*- coding: latin-1 -*-

#
# Suite à l'article "Union d'un ensemble d'intervalles" du site "Sam & Max" :
# http://sametmax.com/union-dun-ensemble-dintervalles/
#
# Olivier Pirson --- http://www.opimedia.be/
# 18 février 2013
#
# Testé sur Python 2.7.3 et Python 3.3.0
#

from __future__ import print_function




import bisect
import collections



def intervals_to_disjoint_intervals(intervals,
                                    closed = False,
                                    container = list):
    """
    Renvoie container(suite d'intervalles)
      avec les intervalles non vides,
      strictements ordonnés sur leur premier élément
      et strictement disjoints.

    Si closed
    alors les intervalles sont considérés comme fermés,
    sinon ils sont considérés comme ouverts ou semi-ouverts tous du même côté
          et les intervalles (a, a) sont éliminés

    Complexité O(n*lg(n)) par rapport à la longueur de intervals

    Pre: intervals: Iterable fini de couples d'éléments deux à deux comparables
         closed: bool
         container: classe dont le constructeur peut recevoir l'itérable
                    résultat de ordered_intervals_to_disjoint_intervals_iter()

    Return: list de tuples de 2 éléments
    """
    assert isinstance(intervals, collections.Iterable), type(intervals)
    assert isinstance(closed, bool), type(closed)
    assert isinstance(container, type), type(container)

    return container(ordered_intervals_to_disjoint_intervals_iter(
            intervals_to_ordered_intervals(intervals,
                                           closed = closed),
            closed = closed))


def intervals_to_ordered_intervals(intervals,
                                   closed = False):
    """
    Renvoie une list
      avec les intervalles non vides,
      strictements ordonnés sur leur premier élément
      et avec les intervalles contigues rassemblés en un seul intervalle
      (mais les intervalles peuvent être strictement disjoints
      ou se chevaucher).

    Si closed
    alors les intervalles sont considérés comme fermés,
    sinon ils sont considérés comme ouverts ou semi-ouverts tous du même côté
          et les intervalles (a, a) sont éliminés.

    Complexité O(n*lg(n)) par rapport à la longueur de intervals

    Pre: intervals: Iterable fini de couples d'éléments deux à deux comparables
         closed: bool

    Return: list de tuples de 2 éléments
    """
    assert isinstance(intervals, collections.Iterable), type(intervals)
    assert isinstance(closed, bool), type(closed)

    begins = []
    ends = []

    len_begins = 0

    for (a, b) in intervals:
        if (a > b) or ((not closed) and (a >= b)):  # interval vide
            continue


        # Est-ce qu'il y a déjà un intervalle qui commence par a ?
        i_begin = bisect.bisect(begins, (a, b))

        len_begins = len(begins)

        if (i_begin + 1 < len(begins)) and (begins[i_begin + 1][0] == a):
            # Déja un (a, > b) dans begins
            assert begins[i_begin - 1][1] > b, (begins[i_begin + 1], (a, b))

            continue

        if (0 < i_begin) and (begins[i_begin - 1][0] == a):
            # Déjà un (a, <= b) dans begins
            assert begins[i_begin - 1][1] <= b, (begins[i_begin - 1], (a, b))

            if begins[i_begin - 1][1] != b:
                # Déjà un (a, < b) dans begins,
                #   on remplace dans begins et dans ends
                del ends[bisect.bisect(ends, (begins[i_begin - 1][1],
                                              begins[i_begin - 1][0])) - 1]

                bisect.insort(ends, (b, a))

                begins[i_begin - 1] = (a, b)

            continue


        # Est-ce qu'il y a déjà un intervalle qui commence par b ?
        i_end = bisect.bisect(ends, (b, a))

        assert len_begins == len(ends)

        if (i_end + 1 < len_begins) and (ends[i_end + 1][0] == b):
            # Déja un (b, > a) dans ends
            assert ends[i_end - 1][1] > a, (ends[i_end + 1], (b, a))

            continue

        if (0 < i_end) and (ends[i_end - 1][0] == b):
            # Déjà un (b, < a) dans ends, on remplace dans begins et dans ends
            assert ends[i_end - 1][1] < a, (ends[i_end - 1], (b, a))

            del begins[bisect.bisect(begins, (ends[i_end - 1][0],
                                              ends[i_end - 1][0])) - 1]

            bisect.insort(begins, (a, b))

            ends[i_end - 1] = (b, a)

            continue


        # Aucun intervalle commençant par a ou terminant par b
        #   n'a encore été rencontré
        begins.insert(i_begin, (a, b))
        ends.insert(i_end, (b, a))

        len_begins += 1

    del ends

    return begins


def ordered_intervals_to_disjoint_intervals_iter(ordered_intervals,
                                                 closed = False):
    """
    Renvoie un itérateur,
    qui renvoie un intervalle après l'autre
                de façon strictement ordonné sur leur premier élément
                et disjoints entre eux.

    Si closed
    alors les intervalles sont considérés comme fermés,
    sinon ils sont considérés comme ouverts ou semi-ouverts tous du même côté
          et les intervalles (a, a) sont éliminés.

    Complexité O(n) par rapport à la longueur de ordered_intervals

    Pre: ordered_intervals: Iterable de couples d'éléments
                              deux à deux comparables
                              strictement ordonné sur leur premier élément
         closed: bool

    Return: Iterator sur des tuple de 2 éléments
    """
    assert isinstance(ordered_intervals, collections.Iterable), \
        type(ordered_intervals)
    assert isinstance(closed, bool), type(closed)

    i = iter(ordered_intervals)
    while True:  # prend le premier intervalle non vide (a, b)
        (a, b) = next(i)
        if (a <= b) and (closed or (a < b)):
            break

    while True:  # compare progressivement les intervalles deux à deux
        while True:  # prend l'intervalle non vide suivant (c, d)
            try:
                (c, d) = next(i)
            except StopIteration:
                yield (a, b)  # il restait cette intervalle

                raise StopIteration

            if (c <= d) and (closed or (c < d)):
                break

        assert a < c, ((a, b), (c, d))

        if b >= c:  # (a, b) et (c, d) se chevauchent ou sont contigus
            a, b = a, max(b, d)
        else:       # (a, b) et (c, d) sont séparés
            yield (a, b)

            a, b = c, d



########
# Main #
########
if __name__ == '__main__':
    from datetime import datetime

    for i, ex in enumerate((((2, 7),
                             (3, 7),
                             (1, 5),
                             (9, 10),
                             (8, 9)),
                            ((10, 210), )*1000000,
                            ((-7.2, -6.9),
                             (-8.4, -5.3),
                             (-10.5, -5.25),
                             (-1.7, 0.01),
                             (0.0, 4.0),
                             (12.125, 13.9),
                             (13.9, 15.0)),
                            ((datetime(2012, 12, 21, 16, 54),
                              datetime(2013, 2, 16, 12, 59)),
                             (datetime(2013, 2, 14, 2, 0),
                              datetime(2069, 1, 1, 13, 37))))):
        result = intervals_to_disjoint_intervals(ex)

        print(result)

        solution = ([(1, 7),
                     (8, 10)],
                    [(10, 210)],
                    [(-10.5, -5.25),
                     (-1.7, 4.0),
                     (12.125, 15.0)],
                    [(datetime(2012, 12, 21, 16, 54),
                      datetime(2069, 1, 1, 13, 37))])[i]

        assert result == solution