Let's say that I have an array with an integer index of 400 in length, and I want to discard several elements from the very beginning, lots from the end and something average, but without changing the original array. That is, instead of iterating over an array using indexes {0...399}, I want to use a piecewise-continuous range, like
{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310}
What is a good data structure for describing such index ranges? The obvious solution is to create another array of “index picks” containing comparisons from continuous indexing with a zero index to the new coordinates above, but this looks rather wasteful, since almost all the elements in it will be just consecutive numbers, and just a few random “jumps” . Also, what if I find this, oh, I want to change the range a bit? The entire array of indexes would have to be rebuilt. Not nice.
A few notes:
- Ranges never overlap. If a new range is added to the data structure and it overlaps with existing ranges, all this should be combined. That is, if I add a range to the above example
{300... 308}, I should replace it instead of the last two ranges {250...310}. - It should be pretty cheap to just iterate over the entire range.
- It should also be relatively cheap to request the value directly: "Give me the source index corresponding to the 42nd index in the displayed coordinates."
- It should be possible (although maybe not quite cheap) to work differently: "Give me a mapped coordinate corresponding to 42 in the original coordinates, or tell me if it is displayed at all."
, , , .
!