Re: [boost] Re: IncrementalRangeMap

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-31 22:25:26

----- Original Message -----
From: "Howard Hinnant" <hinnant_at_[hidden]>
> 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.

Two important special cases of the above are:

* A similar representation of a piecewise linear function. In this case, the
range (in opposite sense from "domain"), i.e. U can be represented as a
single value.
* Same as the above, but the function is monotonic. In that case,
bidirectional mapping domain<->range is possible.

The latter especially has been extremely useful in my work.

-Dave