Re: IncrementalRangeMap

From: Darin Adler (darin_at_[hidden])
Date: 2001-12-31 15:19:39

Darin Adler wrote:
>> And we had IncrementalRangeMap that
>> mapped half-open numeric ranges to numeric value ranges of the
>> same size.  The IncrementalRangeMap was an efficient data
>> structure to express what goes where when you are rearranging
>> something.

Nathan Meyers wrote:
> I'd like to learn more about this.

Here's a quick explanation. A RangeSet does something like this:

    1-5
    123-1000

A RangeMap does something like this:

    1-5      -> 0
    123-1000 -> 155

An IncrementalRangeMap does something like this:

    1-5      -> 0-4
    123-1000 -> 155-1032

The data structure for RangeMap and IncrementalRangeMap can be similar. The
IncrementalRangeMap stores the initial value for each value range. The
implementation difference lies in the rules about when ranges overlap and
are equivalent. So if you have a range 1-5 that maps to 0-4, then a new
range 6-10 that maps to 5-9 "overlaps". It might look like this:

    range_map.add(range(1, 5), 0);
    range_map.add(range(6, 10), 5); // results in a second range

    incremental_range_map.add(range(1, 5), 0);
    incremental_range_map.add(range(6, 10), 5); // results in a single range

Let me know if you'd like me to say more about this.

    -- Darin