CODEWITHSUNDEEP
python
dude
dude

Reputation: 53

I have an interval of integers that comprises some inner intervals. Given these intervals I want to compute a list including the intervals between

Inner intervals are always inside the global one. All intervals are integer, left-closed, right-open intervals.

Let's take this example. The "global" interval is [0, 22[. "Inner" intervals are [3, 6[ and [12, 15[.

For this example I expect : [0, 3[ U [3, 6[ U [6, 12[ U [12, 15[ U [15, 22[

I've tried to define a function but then messed up with indices while iterating over intervals.


def allspans(r, spans):
    pass

allspans((0, 22), [(3,6), (12,15)])  # expected : [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Upvotes: 1

Views: 84

Answers (3)

kaya3
kaya3

Reputation: 51063

Using itertools.chain and itertools.pairwise (Python 3.10+):

from itertools import chain, pairwise

def all_spans(r, spans):
    start, end = r
    it = chain((start,), chain.from_iterable(spans), (end,))
    return [t for t in pairwise(it) if t[0] != t[1]]

First, we construct an iterator it over all of the interval endpoints in order; then the sub-ranges are all the pairs of consecutive endpoints, excluding the empty sub-ranges where two consecutive endpoints are equal.

Upvotes: 1

evanstjabadi
evanstjabadi

Reputation: 305

Using a normal loop:

def allspans(r, spans):
    intervals = []
    intervals.append((r[0], spans[0][0]))

    for i in range(len(spans)):
        current_span = spans[i]
        if i != 0:
            intervals.append((spans[i - 1][1], current_span[0]))
        intervals.append((current_span[0], current_span[1]))

    intervals.append((spans[-1][1], r[1]))

    return intervals


print(allspans((0, 22), [(3, 6), (12, 15)]))
# [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Upvotes: 1

0x0fba
0x0fba

Reputation: 1620

Yes you have to iterate over your spans but take care of maintaining a position to correctly fill the spaces between.

from typing import Generator

def allspans(r, spans) -> Generator:
    pos = 0
    for lower, upper in spans:
        if pos < lower:
            yield pos, lower
        yield lower, upper
        pos = upper
    if pos <= r[1]:
        yield pos, r[1]

I find it easier to use a Generator. Just use list() to convert to a List.

list(allspans((0, 22), [(3,6), (12,15)]))  # [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Upvotes: 1

Related Questions