5
$\begingroup$

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 x belongs to the set, we perform a binary search. If x is found in the array at an even position, x is a member; if x is not found in the array, but can be inserted at an odd index while preserving order, it is also a member. Otherwise x is 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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Your union produces bad results without producing an error when fed overlapping ranges. You should be careful with it. $\endgroup$
    – orlp
    Commented Feb 4, 2017 at 13:47
  • 1
    $\begingroup$ I'm not sure that asking "What is the name of my idea?" makes for a very good question. Try this thought experiment: Suppose someone told you a name. What would do with the name? What question that allow you to answer? Then, edit your question to ask about that question, instead of asking for a "name". Maybe someone will be able to answer that question even if they don't know a "name" for the scheme. Also, there are many more ideas than there are "names"; the great thing about human language is that we describe all sorts of ideas that we don't already have a name for. $\endgroup$
    – D.W. ♦
    Commented Feb 4, 2017 at 17:41
  • 2
    $\begingroup$ Do you seek a "inversion list"? $\endgroup$
    – Evil
    Commented Feb 5, 2017 at 0:13
  • $\begingroup$ @orlp It's called an Inversion List, and the union algorithm works. $\endgroup$
    – Kile Kasmir Asmussen
    Commented Feb 7, 2017 at 16:50
  • $\begingroup$ @D.W. The problem is that I know the signified, but not the signifier, and google only accepts signifiers! It's called an inversion list as Evil correctly guessed. Cut back on the philosophy next time :) I know what I'm about, son. $\endgroup$
    – Kile Kasmir Asmussen
    Commented Feb 7, 2017 at 16:50

1 Answer 1

Reset to default
3
$\begingroup$

The name of the data structure, as @Evil correctly pointed out, is an Inversion List.

And boy is that Wikipedia article a stub.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.