What abstract data type is this?

Question

Is the following a common data type (i.e. does it have a name)?

Its unique characteristic is, unlike a regular Set, that it contains the "universe" on initialisation with O(C) memory overhead, and a max memory overhead of O(N/2) (which only occurs when you remove every-other element):

> s = new Structure(701)
s = Structure(0-700)

> s.remove(100)
s = Structure(0-99, 101-700)

> s.add(100)
s = Structure(0-700)

> s.remove(200)
s = Structure(0-199, 201-700)

> s.remove(202)
s = Structure(0-199, 201, 203-700)

> s.removeAll()
s = Structure()

Does something like this have a standard name?

Answer 1

It's a Compressed Bit Set or Compressed Bitmap.

A Bit Set or Bitmap is a set specifically designed for storing Integers. Most languages offer standard implementations of these. They typically work by assigning a 1 to the Nth bit in an internal array of Integers where N is the number you're adding to the set. 0 indicates the value is not present. The memory usage for these types of Bit Sets is dictated by the largest number you store.

A Compressed Bit Set is one that compacts ranges of 0s and 1s.

In this case, the question demonstrates a type of compression called "run-length-encoding" (thank you @Ralf Kleberhoff), so it is specifically a Run-length Encoded Bitmap.

Common implementations of Compressed Bitmaps (from newest-to-oldest) are:

• Roaring Bitmaps (only one to provide "good random access")
• EWAH
• WAH
• Oracle BBC

Answer 2

I've used this many times in the past and seen it used in things like plane-sweep algorithms for polygon clipping.

Sometimes the abstract data type it represents is just a set, and the data structure is an optimization. I use this for representing the set of matching characters given by a regex expression like [^a-zA-z0-9.-], for example, and to perform intersection, union, and other operations on those sets.

This sort of data structure is implemented on top of some other ordered set or map structure, by simply storing the keys where membership in the set changes instead of the keys in the set itself. In all the other cases where I've seen this sort of thing done, the authors refer to that underlying structure instead of giving a name to the concept itself.

I like the idea of having a name for it, though, since as I said I've used it myself many times. Maybe I would call it an "in & out set" in honor of the hamburger chain I liked the best back when I ate hamburgers.