Re: [boost] [Review] ITL review questions

Subject: Re: [boost] [Review] ITL review questions
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-24 14:35:45

2010/2/24 Simonson, Lucanus J <lucanus.j.simonson_at_[hidden]>

> Why is the element iterator type a member of the interval set and map class
> when it isn't even applicable for "continuous" domain types?  Why not just
> provide a utility iterator adaptor for iterators over intervals that lazily
> generates elements as a separate template class and let people use it where
> it is applicable?  There shouldn't be the need to warn the user or depricate
> the element iterators if they aren't class members of the containers and it
> is obvious to the user that they may iterate a large number of time for
> intervals with large extents.

This is a good idea. I'm going change the code accordingly.

> I also don't understand why there is an itl::map and itl::set since they
> don't seem to add anything that can't be easily accomplished with
> interval_set and interval_map plus the element iterator adaptor or with
> std::set and std::map.  It just isn't clear to me what they are for.

(1) Within the ITL, for all sets and maps there are some functions that are
uniformly available and that are not implemented for std::sets/maps. Some of
them are member functions.
add, subtract : implement generalized addition and subtraction of elements
and segments
add_intersection, flip : intersection and symmetric difference
contains, contained_in : superset/subset relation
cardinality : extension of size can be infinite for continuous interval
containers
iterative_size: number of iteratable entities

This is done to give all all itl::containers, interval and element
containers a uniform basic interface that can be used in global functions.

(2) For element containers itl::set itl::map set theoretic functions are
implemented. In an instantiation e.g.
interval_map<int, itl::set<int> >, sets can therefor be aggregated out of
the box, if itl::sets/maps are used.

(3) element_iterators are a pretty recent extension. The idea to substitute
element containers since element_iterators are available is new. One
obstacle may be that element_iterators lack some of the properties of first
class containers, since they only point to transient objects.

(4) element containers namely itl::maps have own applications in other
projects that use aggregate on collision via the generalized add, subtract
functions.

(5) element containers are used to test the behavioral equivalence between
interval_sets/maps and itl::sets/maps that implement identical concepts
itl::Set and itl::Maps. These equivalence laws tests can be represented by
commuting diagrams:
(use typewriter font to beautify)
interval_container a, b, c
element_container a', b', c'
f: interval_container -> element_container; // e.g. atomize
o : a binary operation, like +

 (a,b) ---o---> c
   |            |
   |f     =     |f
   V            V
(a',b')---o---> c'

or as a formula:
f(a o b) == f(a) o f(b)

These tests can be found in
https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/validater/interval_morphic_validater.hpp
and the law template in:
https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/laws/pushouts.hpp

Also, the absorb_neutrons function seems strangely out of place and has no
> documentation.  What does it do?
>
> It removes all value pairs, that have neutral elements as associated values
from the map.
Neutron absorption is a fallout of law based testing ;) In many use cases
value pairs of maps can be deleted, if the associated value is a neutral
element which keeps the map more minimal. This is desired in many cases, but
in some it's not.

Moreover an interval itl::Map of itl::Sets is a model of itl::Set only, if
it absorbs neutrons.

For a map that is not a neutron absorber, absorb_neutrons can be called to
discard those elements explicitly.

See also
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/concepts/map_traits.html
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semantics/concept_induction.html

Best,
Joachim