59 Monotone increasing extents on interval set

Interval set

An interval set means a linear list of non-overlapping intervals on the integers ℤ used to represent a finite subset of ℤ.

    [---------)    [---)   [------------------)           [-------)

Intervals sets are implemented in Ceda/cxUtils/Interval.h in the cxUtils library and provide the set theoretic functions for union, intersection and difference.

The extent of an interval set means the cardinality of the set of integers that it represents.

Monotone increasing extents on interval set

For a given interval set I, class MeasureMonotoneIncreasingExtentsOnIntervalSet can be used to efficiently calculate the cardinality of I⋂[0,t) for (non-strictly) monotone increasing values of integer t.

We call the cardinality of I⋂[0,t) the extent at t:

extent(t) = |I ⋂ [0,t)|

It's like an accumulated extent up to but not including position t.

    [---------)    [---)   [------------------)           [-------)
    |<--        extent(t)       -->|
                                   t

MonotoneIncreasingExtentsOnIntervalSet.h

In the following code the member variable r of type Range represents an iterator through the half-open intervals (aka a "range") of an interval set defined on the natural numbers ℕ (i.e. non-negative integers).

If r points at an interval (i.e. the implicit conversion from r to bool equals true) then

• r->begin() returns the integer position of the start of the interval
• r->end() returns the integer position at the end (i.e. one past last position) of the interval.
• r->size() equals r->end()-r->begin()

Source: Ceda/cxOT/MonotoneIncreasingExtentsOnIntervalSet.h