Re: [boost] [Review] ITL review questions

Subject: Re: [boost] [Review] ITL review questions
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-24 16:25:52

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

> Joachim Faulhaber wrote:
> >> 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.
>
> Ok, I would suggest that these member functions be made free functions that
> accept std::set and std::map as well as itl::interval_map and
> itl::interval_set.  Wrapping a class to add behaviors defeats generic
> programming and erects barriers to interoperability.
>

... I will consider this, ...

> > (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.
>
> I believe that the same could be accomplished with std::set/map if the set
> theoretic functions were free functions.
>

All the set theoretic operators of the itl are free functions already. What
is missing is an implementation of them for std::set and std::map, which is
not difficult to implement.

>
> > (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.
>
> You can only provide a const iterator.  You can't get non-const access to
> the key type of a map or set anyway.  The codomain value of the map would be
> const with the iterator adaptr and non const with the first class container.
>

.. I still have my doubts if this would be behavioral equivalent to the
corresponding element container. Moreover, if you have an element container
with isolated values represented by an interval container you waste a
considerable amount of memory.

> > 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
>
> I think you should rename this function to remove_null or something less
> misleading.
>

I thought you'd enjoy a little radioactivity ;-)

>
> Also, you should probably implement it with a free function and allow the
> user to specify a value for the neutral element:
>
>
The neutral value is a static property that depends on an itl::Map's
domain_type and it's Combine functor. The user should not be able to set it
to arbitrary values. This would spoil the semantical properties of itl
containers with pretty unknown effects.

> template <MapType>
> void remove_value(MapType& map, typename MapType::codomain_type
> neutral_value = typename MapType::codomain_type());
>
> I'm a little confused about what it means for a map to be a neutron
> absorber.  Does it automatically remove elements with neutral codomain
> values?

yes.

> I'm also confused about what a itl::Map of itl::Sets is and how it can be a
> model of itl::Set.
>

This was the real fun stuff, when I tried to define and validate semantical
properties (laws). While the semantics of itl::Set (I use capital first
letter for concepts here
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/concepts.html#boost_itl.concepts.naming
)
is determined by a "classical" set of laws known from algebras of sets e.g.
http://en.wikipedia.org/wiki/Algebra_of_sets

The semantics of itl::Maps can not be described by a *single* set of laws.
The set of laws that holds for an itl::Map<D,C> is determined by the Concept
that the codomain parameter is model of and some conditions given by the
Map's Trait parameter.

So the semantics of itl::Map is a mapping itself, that maps the Concept C of
a Map's codomain_type to the instantiation of the Map<D,C>.

I think this is beautiful and shows that the definition of the generalized
addition/subtraction on maps is sound.

Also it is the basis of the possibility to implement for instance a set
large_bitset simply as an interval_map of bitsets, and it works
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html

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

Best,
Joachim