Skip to content

rangetools

Source

Danger

Each range is assumed to be valid, i.e. the left side is no larger than the right side.

Warning

Each range is closed on the left side, and open on the right side.

Range Operations

Tools for range operations.

issubrange

issubrange(a, b) returns whether a is contained by b.

issubrange((0, 0.6), (0.4, 1))
# False

issubrange((0.4, 0.6), (0.4, 1))
# True

intersect

intersect(a, b, allowempty=False) computes the overlapping of two ranges a and b. Returns None if there is no overlapping.

  • allowempty specifies whether empty range is returned.
intersect((0, 0.6), (0.4, 1))
# (0.4, 0.6)

union

union(a, b) computes the merging of two ranges a and b. Returns None if there is no overlapping.

union((0, 0.6), (0.4, 1))
# (0, 1)

Range Statistics

Tools for statistics over ranges.

histogram

histogram(thresholds, data, leftmost=-inf) computes the histogram over all the floats in data.

  • The search space is divided by the thresholds of bins specified in thresholds.

  • Each bin of the histogram is labelled by its lower threshold.

    • All values in the bin are no less than the current threshold and less than the next threshold.

    • The first bin is labelled by leftmost, which is -inf in default.

Danger

thresholds must be a sorted list.

histogram(
    [   0.1,                0.5,           0.8, 0.9],
    [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1]
)
# {-inf: 1, 0.1: 4, 0.5: 3, 0.8: 1, 0.9: 2}

Range Querying

Tools for querying ranges.

rangequery

rangequery(keyvalues, query, func=min) efficiently finds the best value from the covered values in keyvalues, if each key in keyvalues is within the query range query.

  • func defines how the best value is computed, and defaults to min for minimum value.

Info

Implemented by SegmentTree to solve the range minimum query problem.

rangequery(
    {0.1: 1, 0.2: 3, 0.3: 0},
            (0.2,            0.4)
)
# 0

Range Matching

Tools for matching ranges.

rangecover

rangecover(whole, covered) solves the variation of the set cover problem by covering the universe range whole as best as possible, using a subset of the covering ranges covered.

Warning

This is an approximate algorithm, which means the returned result is not always the best.

list(rangecover(
     (0,                                                 1),
    [(0, 0.4), (0.2, 0.5), (0.5, 0.8), (0.6, 0.9), (0.8, 1)]
))
# [(0, 0.4), (0.5, 0.8), (0.8, 1), (0.2, 0.5)]

covers

covers(covered) merges the covered ranges covered to resolve any overlap.

Danger

Covered ranges in covered must be sorted by the left side of each range.

list(covers([(-inf, 0), (0.1, 0.2), (0.5, 0.7), (0.6, 0.9)]))
# [(-inf, 0), (0.1, 0.2), (0.5, 0.9)]

gaps

gaps(covered, whole=(-inf, inf)) computes the uncovered ranges of the whole range whole, given the covered ranges covered.

Danger

Covered ranges in covered must be sorted by the left side of each range.

Info

Overlaps among covered ranges covered are resolved, like covers(covered).

list(gaps(
    [(-inf, 0), (0.1, 0.2), (0.5, 0.7), (0.6, 0.9)],
           (0,                                     1)
))
# [(0, 0.1), (0.2, 0.5), (0.9, 1)]