Google is failing me, so here goes:
- The data structure is used to describe a set of positive integers.
- It works conceptually, by keeping track of disjoint ranges [a,b) on the number line.
- These ranges are stored, in a sorted manner. For two consecutive ranges
[a, b), [c, d)the invariant is that
a < b < c < d.
- The ranges are stored flat in an internal array, meaning that for the ranges
[a, b), [c, d)the internal representation is
[a, b, c, d].
- To look up if an integer
xbelongs to the set, we perform a binary search. If
xis found in the array at an even position,
xis a member; if
xis not found in the array, but can be inserted at an odd index while preserving order, it is also a member. Otherwise
xis not a member.
- The internal array does not necessarily contain an even number of elements; if there is an odd number of elements, the last range is open-ended above.
[a, b, c]is the set
[a,b) ∪ [c,∞)
- Conceptually you start excluding numbers up from zero until you reach the first number in the array, then you include numbers up until the second number of the array, then you exclude until the third, include until the fourth, etc.
- Union of a collection of sets is made by iteratively taking the least element from the set with the smallest least element. If that element used to occupy an even index, we increment a counter, if it used to occupy an odd index, we decrement. Whenever the counter moves away from zero, or falls to zero, we include the just-removed element in the new array, otherwise we discard it.
- Complement of a set is computed by inspecting the first element of the array. If it is zero, remove it, it it is not zero, prepend zero.
- This data structure is often used to store information about Unicode properties, as it very compactly describes consecutive ranges of Unicode code points.
What is the name of this beast?