Re: [boost] Re: new component, extent_set<>

From: Beman Dawes (bdawes_at_[hidden])
Date: 2002-01-01 15:13:11

At 12:19 AM 1/1/2002, Nathan Myers wrote:>

 > ...
 >
 >A survey...
 >
 >Judging from the postings by Darin, Howard, and Dave, this represents one
 >of a family of very similar interesting structures.  What is common to
 >them all is not so much their range interface, but rather that they
 >interpolate coverage of their domain and/or range.  They store one
 >or both endpoints depending on whether they are continuous, and use
 >a slope of one or zero.  (Dave suggested allowing other slopes; this
 >would allow mapping from, e.g., block number to byte offset.  He also
 >mentioned bidirectional mapping.  That might be hard to shoehorn into
 >a common structure.)
 >
 >Darin's IncrementalRangeMap, my extent_map<>, and Howard's range_map<>
 >are almost the same.
 >
 >Darin's RangeMap differs from the other examples in having a 0 slope; it
 >could tolerate a non-numeric type in its, er, range.  RangeSet, 
extent_set,
 >and range_run have what amounts to a boolean, um, range.  In all four
 >cases arithmetic on the domain type is limited to, at most, incrementing
 >or decrementing.
 >
 >Treatment of argument domains that overlap existing mappings varies from
 >"Precondition: not", with elegantly minimal operator code, to "anything
 >goes".  I see no reason not to have both interfaces; the difference is
 >usually more a matter of preference -- minimalism vs. generality -- than
 >of semantics or performance.
 >
 >(BTW, I find the "range" term difficult to use around mapping primitives, 

 >given the existing domain/range usage in the same context.  That's 
another
 >part of why I have preferred to say "extent".)
 >
 >It's not clear to me whether all these should be unified under a policy
 >parameter, or just presented as a family of components.  Probably the
 >latter, although they might be able to share some implementation code.
 >in the way that std::set<> and std::map<> do.

If you can unify the above with either a policy-based or family-based 
approach, I think you will find it widely regarded as having a useful 
feature set yet still reasonably compact and comprehensible.

 >Dave's cumulative extent tree, a 1D case of Beman's RTree and
 >Reid's 3D structures, is another productive area to explore.

My sense is that at least the 2D, 3D, and n-dimension flavors of these 
represent a somewhat different problem.  Sure, they would be nice to have 
in Boost, but unless you have some blinding flash of insight that abstracts 
away all the messiness, my guess is that n-dimensional search adaptors for 
containers is best left as a separate problem.

--Beman