Re: [boost] Re: IncrementalRangeMap

From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-31 15:55:23

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.

Nathan Myers
ncm at cantrip dot org