Subject: Re: [boost] Review Request: Boost.Itl; The Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-10-03 11:07:50
2009/10/1 Jeff Flinn <TriumphSprint2000_at_[hidden]>:
> More importantly, I'd like to be able to
> use std::inserter of std::back_inserter with std::copy or std::transform to
> fill the split_interval_map from my domain data.
Thanks Jeff for raising this issue. The current version did not
work so I fixed the code. If you update the code from the
sandbox, std::copy should work now with std::inserter for
interval_maps.
> I see there is an insert
> method, but I'm not sure just how it differs from add.
(1) For integral domain_types the behavior of 'insert' on interval maps
is identical to 'insert' on maps of elements. You could say it has
std::insert semantics. Or more formalized:
For
M: interval_map or split_interval_map of integral
domain_types
m: itl::map (that implements std::insert semantics)
f: atomize: Transforms interval containers
into containers of elements.
p: interval value pair
p': set of element value pairs
this diagram commutes
insert
(M,p) -------> M
| |
|f = |f
| |
V Insert V
(m,p') ------> m
or as a formula:
For all M y, p r:
f(y.insert(r))==Insert(f(y), f(r))
where capitalized 'Insert' iterates over
the set of element value pairs f(r) and
then applies member function 'm::insert'
on map f(y) for the element level.
(2) Member function 'add' does not
provide 'std::insert' semantics (in general).
It performs an aggregation on associated
values, if intervals overvlap or elements
collide (aggregate on overlap). Addition
(via operator += on codomain_type) is the
default, but you can customize via template
parameter 'Combine'.
(3) Both 'insert' and 'add' can be expressed
by a more general member function
template _add<Combiner> (that has been
suffixed by '_' to make life easier for the
CodeWarrior ;-)
M::insert == M::_add<itl::inplace_identity>
M::add == M::_add<itl::inplace_plus>
'inplace_plus' propagates += to aggregate
associated values on overlap.
'inplace_identity' propagates the identity
function to aggregate values, which leaves
them unchanged.
> I'd like to see the
> public interface paired down and just expose the more std::map like
> interface.
I think that the characteristics of interval containers sets
certain limits to the pervasive and powerful use of iterators
and algorithms that is known from stl::containers.
IMO it makes no sense to try to iterate an
interval_set<double>, interval_set<string>, interval_set<rational<int> >
etc. on the level of *elements*.
Only for interval containers of integral domain_types a completely
std conform element iterator can be implemented. But still this
would be a permanent invitation to produce inefficient code particularly
for cases where the granularity of your intervals is very fine.
HTH
Joachim