RampTable

This crate formalizes a data structure that I've encountered many times. I've never seen this data structure treated in its own right. Instead, I've only seen it used in many code bases, implicitly, and never given a name. Perhaps it does have a name and is well-known, but I have not yet been able to find any discussion of it. (If you know of it, please let me know.)

A ramp table is a specific representation for storing a set of lists. The sets are numbered, and the (non-negative) numbers cluster near zero. Ideally, the set numbers are contiguous, or close to it. Each set maps to a list of items.

The representation uses two vectors: index and values. Each entry in the index array corresponds to a set number (also called a key). The index array also contains one additional entry, at the end, which is not associated with any set but which terminates the index vector.

index[key] gives the index within values of the beginning of the values for that key. index[key + 1] gives the index within values of the end (exclusive upper bound) of the values for that key. Thus, &values[index[key]..index[key + 1]] gives the slice of values for a key.

At this point you're about to say, "Oh, that data structure? Everyone knows about that." Precisely! It's so common that it's used all over the place. However, usually I see this data structure "open-coded" into its applications, so it's a little hard to identify it at first. It's also useful to formalize a data structure and give it a name. It also improves readability.

I've seen this data structure used in:

* graphviz (SparseMatrix, lots of other things)
* Berkeley YACC (storing all kinds of things)
* and many more