Run-length bitmaps: union, intersect, and subtract alert spans

Last updated: 5 Oct 20269 min read

tutorial

A run-length bitmap represents a set of nonnegative integers as sorted, disjoint half-open intervals. Construction merges overlapping and adjacent runs. Membership binary-searches the run starts, while union normalizes both run lists, intersection advances two cursors, and difference subtracts overlapping pieces without expanding individual IDs. The result of each set operation is a new bitmap; the input objects remain intact. This is effective when many IDs are consecutive. It is not automatically compact for isolated IDs, because each singleton needs its own run record. The example stores Python interval tuples rather than a byte-packed bitmap wire format, so its memory measurements would include substantial language object overhead.

Operational case

North owns [19,29), [29,47), and [83,91), which construction merges into [19,47) and [83,91). East owns [23,31) and [43,61). Their intersection is [23,31) and [43,47); north minus east leaves [19,23), [31,43), and [83,91). The union contains fifty integer IDs. Each right endpoint is excluded, so 47 is absent from north before union but present in east. Adjacent intervals should merge, or the same represented set would have avoidable extra runs. A negative or empty interval is rejected rather than hidden as a silent no-op.

Working Python program

class AlertBitmap:
    def __init__(self, runs=()):
        ordered = sorted(runs)
        merged = []
        for start, end in ordered:
            if not isinstance(start, int) or not isinstance(end, int) or start < 0 or end <= start:
                raise ValueError("runs must be nonnegative half-open integer intervals")
            if merged and start <= merged[-1][1]:
                merged[-1] = (merged[-1][0], max(merged[-1][1], end))
            else:
                merged.append((start, end))
        self.runs = tuple(merged)

    def union(self, other):
        return AlertBitmap(self.runs + other.runs)

    def intersection(self, other):
        left = right = 0
        overlap = []
        while left < len(self.runs) and right < len(other.runs):
            start = max(self.runs[left][0], other.runs[right][0])
            end = min(self.runs[left][1], other.runs[right][1])
            if start < end:
                overlap.append((start, end))
            if self.runs[left][1] < other.runs[right][1]:
                left += 1
            else:
                right += 1
        return AlertBitmap(overlap)

    def difference(self, other):
        remaining = []
        right = 0
        for start, end in self.runs:
            cursor = start
            while right < len(other.runs) and other.runs[right][1] <= cursor:
                right += 1
            scan = right
            while scan < len(other.runs) and other.runs[scan][0] < end:
                cut_start, cut_end = other.runs[scan]
                if cursor < cut_start:
                    remaining.append((cursor, min(cut_start, end)))
                cursor = max(cursor, cut_end)
                if cursor >= end:
                    break
                scan += 1
            if cursor < end:
                remaining.append((cursor, end))
        return AlertBitmap(remaining)

    def contains(self, alert_number):
        left, right = 0, len(self.runs)
        while left < right:
            middle = (left + right) // 2
            if self.runs[middle][0] <= alert_number:
                left = middle + 1
            else:
                right = middle
        return left > 0 and alert_number < self.runs[left - 1][1]

    def cardinality(self):
        return sum(end - start for start, end in self.runs)


north_alerts = AlertBitmap([(19, 29), (29, 47), (83, 91)])
east_alerts = AlertBitmap([(23, 31), (43, 61)])
print("shared runs:", north_alerts.intersection(east_alerts).runs)
print("north only:", north_alerts.difference(east_alerts).runs)
print("union count:", north_alerts.union(east_alerts).cardinality())

Output

shared runs: ((23, 31), (43, 47))
north only: ((19, 23), (31, 43), (83, 91))
union count: 50

Time, space, and tradeoff

For A and B input run counts, intersection and difference scan O(A+B) runs and use O(A+B) worst-case output space. The current union concatenates and sorts all runs, taking O((A+B) log(A+B)) time, even though a linear merge is possible because each input is already sorted. Membership costs O(log A); cardinality scans O(A) run lengths each call. Stored space is O(A) run tuples. A chunked bitmap may win on scattered dense blocks, while run-length encoding wins when long adjacent ID stretches dominate. Neither format by itself promises a specific byte count without an encoding specification.

Common Mistakes

Do not include the right endpoint of a half-open run.
Do not expand every ID merely to compute an intersection.
Do not assume runs save space for isolated identifiers.
Do not call this Python tuple model a compressed on-disk byte format.

Connected lessons

Compare this operation boundary with Alias tables: constant-work draws from fixed dispatch weights, MinHash bands: retrieve incident candidates, then check exact overlap, then complete the structure audit and decision quiz.

Inverted indexes: intersect sorted incident postings gives a related indexing or summary tradeoff.

data structures

range-query-structures