New "range-tower" data structure.
A range tower is a bitmap, implemented as an augmented binary tree.
Beyond the usual features of a bitmap, a range tower can efficiently
implement a "splice" operation that shifts ranges of bits left or right.
This feature does cost memory and time, so use a range tower only if this
feature is actually needed. Otherwise, use a range set (see range-set.h),
which can do everything that a range tower can do except the "splice"
operation.
Each operation has O(lg N) cost, where N is the number of contiguous
regions of 1-bits in the bitmap. Also, a cache reduces the second and
subsequent containment tests within a single contiguous region to O(1).
projects / pspp / commit