Re: [boost] Re: IncrementalRangeMap

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2001-12-31 21:54:10

On Monday, December 31, 2001, at 03:55  PM, Nathan Myers wrote:

> On Mon, 31 Dec 2001 12:19:39 -0800, "Darin Adler" <darin_at_[hidden]> 
> wrote:
>
>> Darin Adler wrote:
>>>> And we had IncrementalRangeMap that
>>>> mapped half-open numeric ranges to numeric value ranges of the
>>>> same size.
>>
>> Here's a quick explanation.
>> 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
>
> I see; I meant to implement extent_map like incremental_range_map.
> That means that, in its implementation, it would start off with
> an std::map<int,std::pair<int,int>> [sic] instance containing
>   1->pair(0,4), 123->pair(155,1032)
> representing (1-5)->(0-4) etc. and end up with
>   1->pair(0,9), 123->pair(155,1032)
> representing (1-10)->(0-9) etc.
>
> I see how RangeMap could use a similar std::map<> underneath, but
> the pair would identify instead the range length and the tag value.
> A third member of this family might map an unbroken range (0,n) to
> a set of arbitrary (but probably non-overlapping) ranges using just
> std::map<int,int>.
>
> IncrementalRangeMap seems useful for mapping segments of a file (holes
> permitted) to ranges of disk blocks, in order.  RangeMap seems useful
> for mapping ranges of disk blocks to the inode numbers of the files
> they store.  Is that how you were using them?
>
> David Greene mentioned he wanted to be able to suppress range merges,
> although he hasn't reported back yet on why.  I guess that if you were
> to tag the mapped range with additional metadata, then the metadata
> attached to a range might differ from that of an adjacent range.

Just to add to the fray...

I've also implemented and used something similar to IncrementalRangeMap, 
though I called it range_map.  It looks like:

template <class T, class U>
class range_map
{
public:
        U operator[](const T& x) const;
        void insert(const T& x1, const T& x2, const U& y1, const U& y2);
};

It maps multiple domains [x1, x2] into multiple ranges [y1, y2].   It 
holds non-overlapping domain/range pairs which can then be queried with 
the operator[x].  It is essentially an ordered vector of linear 
equations (stored by slope and intercept), ordered by the domain over 
which the equation is valid.  Client code can insert overlapping ranges, 
but the insert method subdivides the existing domains and the newly 
inserted domain such that the result is a set of non-overlapping domains.

This has been used (for example) to create an upper case to lower case 
mapping of wchar_t:

range_map<wchar_t, wchar_t> lower_map;

// map all wchar_t to themselves

wchar_t wmin = numeric_limits<wchar_t>::min();
wchar_t wmax = numeric_limits<wchar_t>::max();
lower_map.insert(wmin, wmax, wmin, wmax);

// Overlay identity map with ['A' - 'Z'] -> ['a' - 'z']

lower_map.insert(L'A', L'Z', L'a', L'z');

// test it

wchar_t c = lower_map[L'C'];  // L'c'

At this point the lower_map contains 3 domain/equation pairs:
      [wmin, 'A') -> [wmin, 'A')
      ['A', 'Z']  -> ['a', 'z']
      ('Z', wmax] -> ('Z', wmax]

The second insert subdivided the original identity map into 3 
domain/ranges.  With integral types, the equation's slope and intercept 
are of course limited to integral values.

Not sure if this would be useful for managing disk blocks.

-Howard