Re: [boost] Review Request: Boost.Itl; The Interval Template Library

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'.

see also:
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/concepts/addability__subtractability_and_aggregate_on_overlap.html

(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