Data structure to represent piecewise continuous range?

Question

Say that I have an integer-indexed array of length 400, and I want to drop out a few elements from the beginning, lots from the end, and something from the middle too, but without actually altering the original array. That is, instead of looping through the array using indices {0...399}, I want to use a piecewise continuous range such as

{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310}

What is a good data structure to describe this kind of index ranges? An obvious solution is to make another "index mediator" array, containing mappings from continuos zero-based indexing to the new coordinates above, but it feels quite wasteful, since almost all elements in it would be simply sequential numbers, with just a few occasional "jumps". Besides, what if I find that, oh, I want to modify the range a bit? The whole index array would have to be rebuilt. Not nice.

A few points to note:

• The ranges never overlap. If a new range is added to the data structure, and it overlaps with existing ranges, the whole thing should get merged. That is, if I add to the above example the range {300... 308}, it should instead replace the last two ranges with {250...310}.
• It should be quite cheap to simply loop through the whole range.
• It should also be relatively cheap to query a value directly: "Give me the original index corresponding to the 42nd index in the mapped coordinates".
• It should be possible (though maybe not quite cheap) to work other way round: "Give me the mapped coordinate corresponding to 42 in the original coordinates, or tell if it's mapped at all."

Before rolling my own solution, I'd like to know if there exists a well-known data structure that solves this class of problems elegantly.

Thanks!

Answer 1

Seems like an array or list of integer pairs would be the best data structure. Your choice as to whether the second integer of the pair is a end point or a count from the first integer.

Edit: On further reflection, this problem is exactly what a database index has to do. If the integer pairs don't have to be in numeric order, you can handle splits easier. If the number sequence has to remain in order, you need a data structure that allows you to add integer pairs to the middle of the array or list.

A split would be having to change the (6, 12) integer pair to (6, 9) (11, 12), when 10 is removed, as an example.

Besides, what if I find that, oh, I want to modify the range a bit? The whole index array would have to be rebuilt. Not nice.

True. Perhaps one integer pair needs to change. Worst case, you'd have to rebuild the entire array or list.