[boost] Fwd: [Boost-users] [Review] ITL review starts today, February 18th

Subject: [boost] Fwd: [Boost-users] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-25 16:48:02

Hi,
this question of Mathias was posted in both [Boost-users] and [boost] but
the answer was accidentally send to [Boost-users] only.

---------- Forwarded message ----------
From: Joachim Faulhaber <afojgo_at_[hidden]>
Date: 2010/2/23
Subject: Re: [Boost-users] [Review] ITL review starts today, February 18th
To: boost-users_at_[hidden]

2010/2/23 Mathias Gaunard <mathias.gaunard_at_[hidden]>:
> Hartmut Kaiser wrote:
>
>> Interval containers allow to access and manipulate collections of
>> intervals
>> on an abstract level as sets and maps (of elements), but also to exploit
>> segmental information that is given by the interval borders. Interval
>> containers are fairly generic. They can be instantiated with discrete
>> domain
>> (or key) types like integral numeric types or boost::date or time types.
>> But
>> they also work with continuous domain types like double, rational or
>> string.
>> Using the latter allows to represent infinite sets and maps.
>>
>> The interface of the interval containers strives to be very intuitive and
>> in
>> line with the stl and other boost libraries.
>>
>> * The set theoretic operations union, difference, intersection
>>  and symmetric difference are available as operators for all
>>  interval containers and for many useful overloads between them.
>
> I have no knowledge of the problem domain (nor did I actually look at the
> library yet, sorry about that), but I simply have a question: how does
this
> compare to geometry libraries or spatial indexes that provide that kind of
> facilities for arbitrary dimensions?
>
> I certainly wouldn't want to force over-generalization to the authors, but
I
> am wondering how much is gained by limiting things to one dimension.

So can this library survive in a field of power called boost of an ever
abstracting ever generalizing and ever optimizing bunch of thinkers?

A few points:

* Geometry usually is based on a numeric coordinate type
 that comes with a distance measure. Many algorithms in
 geometry libraries rely on that. Intervals and interval containers
 of the ITL, similar to SortedAssociativeContainers, only require a
 strict weak ordering on their key type. So interval containers
 are less restricted and allow for a larger class of instantiations.
 You may for example want to work with interval sets of strings.

* Interval containers implement interval combining styles that
 can be useful in providing and manipulating certain time grids. E.g.
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/time_grids_for_months_and_weeks.html
 I'm not aware of something like that in geometry.

* There are not only interval sets but also interval maps.
 itl::interval_map is the real workhorse in those real world
 applications that already exist. interval_maps provide a
 general idiom of aggregation of associated values. This
 idiom is very useful for computing statistical data through
 aggregation that occur in time.

* Sometimes a more simple and basic class of data structures
 is advantageous. It may be simpler to implement
 optimizations. Like Lukes Manhattan integral polygons
 compared to more general GGL polygons.

* Transfer of geometry knowledge to the more simple models
 of interval sets and maps may be a step users may not
 come up with.

* The basic set and map concepts of the ITL allow for a
 variety of applications that may go beyond the scope of
 geometry. One such example is the self compressing
 large bitset, which not really has the look and feel of
 geometry ...
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html
 ... or the example of a system of authorisations. See
 the example user_groups
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/user_groups.html

* Well known data structures from geometry like interval_tree or
 spatial indices do have different focuses and different applications.
 An interval_tree is more space efficient than an interval_map that
 can computes all overlaps at once. This may be desired if you
 need all of them. If you don't and you have reoccurring arbitrary
 stabbing queries interval_trees are the better choice.

* itl::Maps are defining a generalized addition, which I think
 is a quite powerful feature that accounts for most of the
 goodies in the applications that we have done. This addition
 function is a generalisation of the common insert function on
 SortedAssociativeContainers and it introduces the aggregating
 properties of itl::Maps. The aggregate on overlap idiom is
 independent of the question, if the domain_type of the
 map or interval_map is a scalar or a tuple (has dimensions)
 or something else. There are already interesting applications
 of aggregations using itl::maps of tuples, but this exceeds the
 scope of the core library.

Cheers,
Joachim